Swift Language
신속한 알고리즘
수색…
소개
알고리즘은 컴퓨팅의 중추입니다. 어느 상황에서 어느 알고리즘을 사용할 것인지 선택하여 좋은 프로그래머와 평균을 구별합니다. 이를 염두에두고 여기에 정의 된 기본 알고리즘의 정의와 코드 예가 있습니다.
삽입 정렬
삽입 정렬은 컴퓨터 과학에서 가장 기본적인 알고리즘 중 하나입니다. 삽입 정렬은 컬렉션을 반복하여 요소를 순위 지정하고 해당 값을 기반으로 요소를 배치합니다. 집합은 정렬 된 반 및 반 정렬되지 않은 반으로 나뉘며 모든 요소가 정렬 될 때까지 반복됩니다. 삽입 정렬에는 O (n2)의 복잡성이 있습니다. 아래 예제처럼 확장 기능에 넣거나 메소드를 만들 수 있습니다.
extension Array where Element: Comparable {
func insertionSort() -> Array<Element> {
//check for trivial case
guard self.count > 1 else {
return self
}
//mutated copy
var output: Array<Element> = self
for primaryindex in 0..<output.count {
let key = output[primaryindex]
var secondaryindex = primaryindex
while secondaryindex > -1 {
if key < output[secondaryindex] {
//move to correct position
output.remove(at: secondaryindex + 1)
output.insert(key, at: secondaryindex)
}
secondaryindex -= 1
}
}
return output
}
}
정렬
버블 정렬
이것은 정렬 될 목록을 반복적으로 거치며, 인접한 항목의 각 쌍을 비교하고 잘못된 순서로 바뀌면이를 바꿔주는 단순한 정렬 알고리즘입니다. 목록을 통과하면 스왑이 필요 없을 때까지 반복됩니다. 알고리즘은 간단하지만 대부분의 문제에서는 너무 느리고 비실용적입니다. 그것은 O (n2)의 복잡성을 가지고 있지만 삽입 정렬보다 느린 것으로 간주됩니다.
extension Array where Element: Comparable {
func bubbleSort() -> Array<Element> {
//check for trivial case
guard self.count > 1 else {
return self
}
//mutated copy
var output: Array<Element> = self
for primaryIndex in 0..<self.count {
let passes = (output.count - 1) - primaryIndex
//"half-open" range operator
for secondaryIndex in 0..<passes {
let key = output[secondaryIndex]
//compare / swap positions
if (key > output[secondaryIndex + 1]) {
swap(&output[secondaryIndex], &output[secondaryIndex + 1])
}
}
}
return output
}
}
삽입 정렬
삽입 정렬은 컴퓨터 과학에서 가장 기본적인 알고리즘 중 하나입니다. 삽입 정렬은 컬렉션을 반복하여 요소를 순위 지정하고 해당 값을 기반으로 요소를 배치합니다. 집합은 정렬 된 반 및 반 정렬되지 않은 반으로 나뉘며 모든 요소가 정렬 될 때까지 반복됩니다. 삽입 정렬에는 O (n2)의 복잡성이 있습니다. 아래 예제처럼 확장 기능에 넣거나 메소드를 만들 수 있습니다.
extension Array where Element: Comparable {
func insertionSort() -> Array<Element> {
//check for trivial case
guard self.count > 1 else {
return self
}
//mutated copy
var output: Array<Element> = self
for primaryindex in 0..<output.count {
let key = output[primaryindex]
var secondaryindex = primaryindex
while secondaryindex > -1 {
if key < output[secondaryindex] {
//move to correct position
output.remove(at: secondaryindex + 1)
output.insert(key, at: secondaryindex)
}
secondaryindex -= 1
}
}
return output
}
}
선택 정렬
선택 정렬은 단순성으로 유명합니다. 배열의 첫 번째 요소부터 시작하여 값을 최소값 (또는 정렬 순서에 따라 최대 값)으로 저장합니다. 그런 다음 배열을 반복하고 min 값을 다른 값보다 작은 값으로 바꿉니다. 그런 다음 min 값을 배열의 가장 왼쪽 부분에 놓고 다음 색인에서부터 배열 끝까지 반복합니다. 선택 정렬은 O (n2)의 복잡성을가집니다. 그러나 선택 정렬은 선택 항목 정렬보다 느립니다.
func selectionSort () -> Array {// 사소한 경우 가드를 확인 self.count> 1 else {return self}
//mutated copy
var output: Array<Element> = self
for primaryindex in 0..<output.count {
var minimum = primaryindex
var secondaryindex = primaryindex + 1
while secondaryindex < output.count {
//store lowest value as minimum
if output[minimum] > output[secondaryindex] {
minimum = secondaryindex
}
secondaryindex += 1
}
//swap minimum value with array iteration
if primaryindex != minimum {
swap(&output[primaryindex], &output[minimum])
}
}
return output
}
빠른 정렬 - O (n log n)의 복잡성 시간
Quicksort는 고급 알고리즘 중 하나입니다. 그것은 O (n log n)의 시간 복잡성을 특징으로하고 나누기 & 정복 전략을 적용합니다. 이 조합은 알고리즘 성능을 향상시킵니다. Quicksort는 먼저 큰 배열을 두 개의 작은 하위 배열 인 낮은 요소와 높은 요소로 나눕니다. 그런 다음 Quicksort는 하위 배열을 반복적으로 정렬 할 수 있습니다.
단계는 다음과 같습니다.
배열에서 피벗이라고하는 요소를 선택합니다.
피벗보다 값이 작은 모든 요소가 피벗 앞에 오도록 배열의 순서를 바꾸고 피벗보다 큰 값을 가진 모든 요소가 그 뒤에옵니다 (같은 값은 어느 방향 으로든 갈 수 있습니다). 이 분할 후에는 피벗이 최종 위치에 있습니다. 이를 파티션 작업이라고합니다.
위의 단계를 값이 작은 요소의 하위 배열에, 큰 값의 요소의 하위 배열에 개별적으로 반복적으로 적용합니다.
mutating func quickSort () -> Array {
func qSort(start startIndex: Int, _ pivot: Int) {
if (startIndex < pivot) {
let iPivot = qPartition(start: startIndex, pivot)
qSort(start: startIndex, iPivot - 1)
qSort(start: iPivot + 1, pivot)
}
}
qSort(start: 0, self.endIndex - 1)
return self
}
mutating func qPartition(start startIndex: Int, _ pivot: Int) -> Int {
var wallIndex: Int = startIndex
//compare range with pivot
for currentIndex in wallIndex..<pivot {
if self[currentIndex] <= self[pivot] {
if wallIndex != currentIndex {
swap(&self[currentIndex], &self[wallIndex])
}
//advance wall
wallIndex += 1
}
}
//move pivot to final position
if wallIndex != pivot {
swap(&self[wallIndex], &self[pivot])
}
return wallIndex
}
선택 정렬
선택 정렬은 단순성으로 유명합니다. 배열의 첫 번째 요소부터 시작하여 값을 최소값 (또는 정렬 순서에 따라 최대 값)으로 저장합니다. 그런 다음 배열을 반복하고 min 값을 다른 값보다 작은 값으로 바꿉니다. 그런 다음 min 값을 배열의 가장 왼쪽 부분에 놓고 다음 색인에서부터 배열 끝까지 반복합니다. 선택 정렬은 O (n2)의 복잡성을가집니다. 그러나 선택 정렬은 선택 항목 정렬보다 느립니다.
func selectionSort() -> Array<Element> {
//check for trivial case
guard self.count > 1 else {
return self
}
//mutated copy
var output: Array<Element> = self
for primaryindex in 0..<output.count {
var minimum = primaryindex
var secondaryindex = primaryindex + 1
while secondaryindex < output.count {
//store lowest value as minimum
if output[minimum] > output[secondaryindex] {
minimum = secondaryindex
}
secondaryindex += 1
}
//swap minimum value with array iteration
if primaryindex != minimum {
swap(&output[primaryindex], &output[minimum])
}
}
return output
}
점근선 분석
선택할 알고리즘이 많으므로 배열을 정렬하려면 어떤 배열인지를 알아야합니다. 따라서 우리는 알고리즘의 속도와 신뢰성을 측정 할 수있는 방법이 필요합니다. Asymptotic analysis가 시작됩니다. Asymptotic analysis는 입력 크기가 커짐에 따라 알고리즘의 효율성을 설명하는 프로세스입니다. 컴퓨터 과학에서, asymptotics는 일반적으로 큰 O 표기법으로 알려진 일반적인 형식으로 표현됩니다.
- 선형 시간 O (n) : 함수의 목표 달성을 위해 배열의 각 항목을 평가해야하는 경우 요소 수가 증가함에 따라 함수의 효율성이 떨어집니다. 이와 같은 함수는 속도가 입력 크기에 의존하기 때문에 선형 시간으로 실행된다고합니다.
- Polynominal time O (n2) : 함수의 복잡도가 기하 급수적으로 커지는 경우 (함수의 배열 요소 중 n 개의 요소가 n 제곱 인 경우) 함수는 다항식 시간에 연산을 수행합니다. 이들은 일반적으로 중첩 루프가있는 함수입니다. 두 개의 중첩 루프는 O (n2) 복잡성을 초래하고 세 개의 중첩 루프는 O (n3) 복잡성을 초래합니다.
- 로그 시간 O (log n) : 로그 시간 함수의 복잡도는 입력 (n)의 크기가 커질 때 최소화됩니다. 이것들은 모든 프로그래머가 노력하는 유형의 함수입니다.
빠른 정렬 - O (n log n)의 복잡성 시간
Quicksort는 고급 알고리즘 중 하나입니다. 그것은 O (n log n)의 시간 복잡성을 특징으로하고 나누기 & 정복 전략을 적용합니다. 이 조합은 알고리즘 성능을 향상시킵니다. Quicksort는 먼저 큰 배열을 두 개의 작은 하위 배열 인 낮은 요소와 높은 요소로 나눕니다. 그런 다음 Quicksort는 하위 배열을 반복적으로 정렬 할 수 있습니다.
단계는 다음과 같습니다.
배열에서 피벗이라고하는 요소를 선택합니다.
피벗보다 값이 작은 모든 요소가 피벗 앞에 오도록 배열의 순서를 바꾸고 피벗보다 큰 값을 가진 모든 요소가 그 뒤에옵니다 (같은 값은 어느 방향 으로든 갈 수 있습니다). 이 분할 후에는 피벗이 최종 위치에 있습니다. 이를 파티션 작업이라고합니다.
위의 단계를 값이 작은 요소의 하위 배열에, 큰 값의 요소의 하위 배열에 개별적으로 반복적으로 적용합니다.
mutating func quickSort() -> Array<Element> { func qSort(start startIndex: Int, _ pivot: Int) { if (startIndex < pivot) { let iPivot = qPartition(start: startIndex, pivot) qSort(start: startIndex, iPivot - 1) qSort(start: iPivot + 1, pivot) } } qSort(start: 0, self.endIndex - 1) return self}
돌연변이 func qPartition (start startIndex : Int, _ pivot : Int) -> Int {
var wallIndex: Int = startIndex //compare range with pivot for currentIndex in wallIndex..<pivot { if self[currentIndex] <= self[pivot] { if wallIndex != currentIndex { swap(&self[currentIndex], &self[wallIndex]) } //advance wall wallIndex += 1 } }
//move pivot to final position
if wallIndex != pivot {
swap(&self[wallIndex], &self[pivot])
}
return wallIndex
}
그래프, 스택, 스택
그래프
컴퓨터 과학에서 그래프는 무향 그래프와 수학에서 유도 된 그래프 개념을 구현하기위한 추상 데이터 유형입니다. 그래프 데이터 구조는 유한 그래프 (또는 변경 가능) 집합의 정점 또는 노드 또는 점과 함께 무 방향성 그래프에 대한 이러한 정점의 집합과 유향 그래프에 대한 정렬 된 쌍의 집합으로 구성됩니다. 이러한 쌍은 방향이없는 그래프의 경우 가장자리, 호 또는 선으로, 방향 그래프의 경우 화살표, 지시선, 지시 된 호 또는 지시선으로 알려져 있습니다. 정점은 그래프 구조의 일부이거나 정수 인덱스 또는 참조로 표현 된 외부 엔티티 일 수 있습니다. 그래프 데이터 구조는 기호 레이블 또는 숫자 속성 (비용, 용량, 길이 등)과 같은 일부 가장자리 값을 각 에지에 연결할 수도 있습니다. (위키 백과, 출처 )
//
// GraphFactory.swift
// SwiftStructures
//
// Created by Wayne Bishop on 6/7/14.
// Copyright (c) 2014 Arbutus Software Inc. All rights reserved.
//
import Foundation
public class SwiftGraph {
//declare a default directed graph canvas
private var canvas: Array<Vertex>
public var isDirected: Bool
init() {
canvas = Array<Vertex>()
isDirected = true
}
//create a new vertex
func addVertex(key: String) -> Vertex {
//set the key
let childVertex: Vertex = Vertex()
childVertex.key = key
//add the vertex to the graph canvas
canvas.append(childVertex)
return childVertex
}
//add edge to source vertex
func addEdge(source: Vertex, neighbor: Vertex, weight: Int) {
//create a new edge
let newEdge = Edge()
//establish the default properties
newEdge.neighbor = neighbor
newEdge.weight = weight
source.neighbors.append(newEdge)
print("The neighbor of vertex: \(source.key as String!) is \(neighbor.key as String!)..")
//check condition for an undirected graph
if isDirected == false {
//create a new reversed edge
let reverseEdge = Edge()
//establish the reversed properties
reverseEdge.neighbor = source
reverseEdge.weight = weight
neighbor.neighbors.append(reverseEdge)
print("The neighbor of vertex: \(neighbor.key as String!) is \(source.key as String!)..")
}
}
/* reverse the sequence of paths given the shortest path.
process analagous to reversing a linked list. */
func reversePath(_ head: Path!, source: Vertex) -> Path! {
guard head != nil else {
return head
}
//mutated copy
var output = head
var current: Path! = output
var prev: Path!
var next: Path!
while(current != nil) {
next = current.previous
current.previous = prev
prev = current
current = next
}
//append the source path to the sequence
let sourcePath: Path = Path()
sourcePath.destination = source
sourcePath.previous = prev
sourcePath.total = nil
output = sourcePath
return output
}
//process Dijkstra's shortest path algorthim
func processDijkstra(_ source: Vertex, destination: Vertex) -> Path? {
var frontier: Array<Path> = Array<Path>()
var finalPaths: Array<Path> = Array<Path>()
//use source edges to create the frontier
for e in source.neighbors {
let newPath: Path = Path()
newPath.destination = e.neighbor
newPath.previous = nil
newPath.total = e.weight
//add the new path to the frontier
frontier.append(newPath)
}
//construct the best path
var bestPath: Path = Path()
while frontier.count != 0 {
//support path changes using the greedy approach
bestPath = Path()
var pathIndex: Int = 0
for x in 0..<frontier.count {
let itemPath: Path = frontier[x]
if (bestPath.total == nil) || (itemPath.total < bestPath.total) {
bestPath = itemPath
pathIndex = x
}
}
//enumerate the bestPath edges
for e in bestPath.destination.neighbors {
let newPath: Path = Path()
newPath.destination = e.neighbor
newPath.previous = bestPath
newPath.total = bestPath.total + e.weight
//add the new path to the frontier
frontier.append(newPath)
}
//preserve the bestPath
finalPaths.append(bestPath)
//remove the bestPath from the frontier
//frontier.removeAtIndex(pathIndex) - Swift2
frontier.remove(at: pathIndex)
} //end while
//establish the shortest path as an optional
var shortestPath: Path! = Path()
for itemPath in finalPaths {
if (itemPath.destination.key == destination.key) {
if (shortestPath.total == nil) || (itemPath.total < shortestPath.total) {
shortestPath = itemPath
}
}
}
return shortestPath
}
///an optimized version of Dijkstra's shortest path algorthim
func processDijkstraWithHeap(_ source: Vertex, destination: Vertex) -> Path! {
let frontier: PathHeap = PathHeap()
let finalPaths: PathHeap = PathHeap()
//use source edges to create the frontier
for e in source.neighbors {
let newPath: Path = Path()
newPath.destination = e.neighbor
newPath.previous = nil
newPath.total = e.weight
//add the new path to the frontier
frontier.enQueue(newPath)
}
//construct the best path
var bestPath: Path = Path()
while frontier.count != 0 {
//use the greedy approach to obtain the best path
bestPath = Path()
bestPath = frontier.peek()
//enumerate the bestPath edges
for e in bestPath.destination.neighbors {
let newPath: Path = Path()
newPath.destination = e.neighbor
newPath.previous = bestPath
newPath.total = bestPath.total + e.weight
//add the new path to the frontier
frontier.enQueue(newPath)
}
//preserve the bestPaths that match destination
if (bestPath.destination.key == destination.key) {
finalPaths.enQueue(bestPath)
}
//remove the bestPath from the frontier
frontier.deQueue()
} //end while
//obtain the shortest path from the heap
var shortestPath: Path! = Path()
shortestPath = finalPaths.peek()
return shortestPath
}
//MARK: traversal algorithms
//bfs traversal with inout closure function
func traverse(_ startingv: Vertex, formula: (_ node: inout Vertex) -> ()) {
//establish a new queue
let graphQueue: Queue<Vertex> = Queue<Vertex>()
//queue a starting vertex
graphQueue.enQueue(startingv)
while !graphQueue.isEmpty() {
//traverse the next queued vertex
var vitem: Vertex = graphQueue.deQueue() as Vertex!
//add unvisited vertices to the queue
for e in vitem.neighbors {
if e.neighbor.visited == false {
print("adding vertex: \(e.neighbor.key!) to queue..")
graphQueue.enQueue(e.neighbor)
}
}
/*
notes: this demonstrates how to invoke a closure with an inout parameter.
By passing by reference no return value is required.
*/
//invoke formula
formula(&vitem)
} //end while
print("graph traversal complete..")
}
//breadth first search
func traverse(_ startingv: Vertex) {
//establish a new queue
let graphQueue: Queue<Vertex> = Queue<Vertex>()
//queue a starting vertex
graphQueue.enQueue(startingv)
while !graphQueue.isEmpty() {
//traverse the next queued vertex
let vitem = graphQueue.deQueue() as Vertex!
guard vitem != nil else {
return
}
//add unvisited vertices to the queue
for e in vitem!.neighbors {
if e.neighbor.visited == false {
print("adding vertex: \(e.neighbor.key!) to queue..")
graphQueue.enQueue(e.neighbor)
}
}
vitem!.visited = true
print("traversed vertex: \(vitem!.key!)..")
} //end while
print("graph traversal complete..")
} //end function
//use bfs with trailing closure to update all values
func update(startingv: Vertex, formula:((Vertex) -> Bool)) {
//establish a new queue
let graphQueue: Queue<Vertex> = Queue<Vertex>()
//queue a starting vertex
graphQueue.enQueue(startingv)
while !graphQueue.isEmpty() {
//traverse the next queued vertex
let vitem = graphQueue.deQueue() as Vertex!
guard vitem != nil else {
return
}
//add unvisited vertices to the queue
for e in vitem!.neighbors {
if e.neighbor.visited == false {
print("adding vertex: \(e.neighbor.key!) to queue..")
graphQueue.enQueue(e.neighbor)
}
}
//apply formula..
if formula(vitem!) == false {
print("formula unable to update: \(vitem!.key)")
}
else {
print("traversed vertex: \(vitem!.key!)..")
}
vitem!.visited = true
} //end while
print("graph traversal complete..")
}
}
트라이
컴퓨터 과학에서 디지털 트리 및 때로는 기수 (radix) 트리 또는 접두사 트리 (접두어로 검색 할 수 있음)라고도 부르는 트리는 일종의 검색 트리입니다.이 트리는 동적 집합이나 연관을 저장하는 데 사용되는 트리 구조의 데이터 구조입니다 배열 어디 키가 일반적으로 문자열입니다. (위키 백과, 출처 )
//
// Trie.swift
// SwiftStructures
//
// Created by Wayne Bishop on 10/14/14.
// Copyright (c) 2014 Arbutus Software Inc. All rights reserved.
//
import Foundation
public class Trie {
private var root: TrieNode!
init(){
root = TrieNode()
}
//builds a tree hierarchy of dictionary content
func append(word keyword: String) {
//trivial case
guard keyword.length > 0 else {
return
}
var current: TrieNode = root
while keyword.length != current.level {
var childToUse: TrieNode!
let searchKey = keyword.substring(to: current.level + 1)
//print("current has \(current.children.count) children..")
//iterate through child nodes
for child in current.children {
if (child.key == searchKey) {
childToUse = child
break
}
}
//new node
if childToUse == nil {
childToUse = TrieNode()
childToUse.key = searchKey
childToUse.level = current.level + 1
current.children.append(childToUse)
}
current = childToUse
} //end while
//final end of word check
if (keyword.length == current.level) {
current.isFinal = true
print("end of word reached!")
return
}
} //end function
//find words based on the prefix
func search(forWord keyword: String) -> Array<String>! {
//trivial case
guard keyword.length > 0 else {
return nil
}
var current: TrieNode = root
var wordList = Array<String>()
while keyword.length != current.level {
var childToUse: TrieNode!
let searchKey = keyword.substring(to: current.level + 1)
//print("looking for prefix: \(searchKey)..")
//iterate through any child nodes
for child in current.children {
if (child.key == searchKey) {
childToUse = child
current = childToUse
break
}
}
if childToUse == nil {
return nil
}
} //end while
//retrieve the keyword and any descendants
if ((current.key == keyword) && (current.isFinal)) {
wordList.append(current.key)
}
//include only children that are words
for child in current.children {
if (child.isFinal == true) {
wordList.append(child.key)
}
}
return wordList
} //end function
}
(GitHub, 출처 )
스택
컴퓨터 과학에서 스택은 요소를 컬렉션에 추가하는 push와 아직 제거되지 않은 가장 최근에 추가 된 요소를 제거하는 pop의 두 가지 기본 연산으로 요소 컬렉션으로 사용되는 추상 데이터 유형입니다. 요소가 스택에서 벗어나는 순서는 대체 이름 인 LIFO (last in, first out)를 발생시킵니다. 또한 peek 조작은 스택을 수정하지 않고 상단에 액세스 할 수 있습니다. (위키 백과, 출처 )
아래 라이센스 정보 및 원본 코드 소스 ( github )를 참조하십시오.
//
// Stack.swift
// SwiftStructures
//
// Created by Wayne Bishop on 8/1/14.
// Copyright (c) 2014 Arbutus Software Inc. All rights reserved.
//
import Foundation
class Stack<T> {
private var top: Node<T>
init() {
top = Node<T>()
}
//the number of items - O(n)
var count: Int {
//return trivial case
guard top.key != nil else {
return 0
}
var current = top
var x: Int = 1
//cycle through list
while current.next != nil {
current = current.next!
x += 1
}
return x
}
//add item to the stack
func push(withKey key: T) {
//return trivial case
guard top.key != nil else {
top.key = key
return
}
//create new item
let childToUse = Node<T>()
childToUse.key = key
//set new created item at top
childToUse.next = top
top = childToUse
}
//remove item from the stack
func pop() {
if self.count > 1 {
top = top.next
}
else {
top.key = nil
}
}
//retrieve the top most item
func peek() -> T! {
//determine instance
if let topitem = top.key {
return topitem
}
else {
return nil
}
}
//check for value
func isEmpty() -> Bool {
if self.count == 0 {
return true
}
else {
return false
}
}
}
MIT 라이센스 (MIT)
Copyright (c) 2015, Wayne Bishop & Arbutus Software Inc.
사용, 복사, 수정, 병합 할 수있는 권한을 포함하되 이에 국한되지 않고 소프트웨어를 취급하기 위해이 소프트웨어 및 관련 문서 파일 (이하 "소프트웨어")의 사본을 얻는 모든 사람에게 사용 권한이 무료로 부여됩니다 다음 조건에 따라 소프트웨어의 사본을 게시, 배포, 재 라이센스 및 / 또는 판매 할 수 있고 소프트웨어를 제공받는 사람에게 허용 할 수 있습니다.
위의 저작권 고지 및이 허가 고지는 소프트웨어의 모든 사본 또는 상당 부분에 포함되어야합니다.
소프트웨어는 상품성, 특정 목적에의 적합성 및 비 침해에 대한 보증을 포함하여 (단, 이에 한하지 않음) 묵시적이든 명시 적이든 어떠한 종류의 보증없이 "있는 그대로"제공됩니다. 저자 또는 저작권 보유자는 어떠한 경우에도 소프트웨어 또는 사용과 관련하여 발생했거나 발생했거나 발생했거나 계약 위반, 기타로 인해 발생하는 청구 또는 기타 책임에 대해 책임을지지 않습니다. 소프트웨어.
