Swift Language
スイフトのアルゴリズム
サーチ…
前書き
アルゴリズムはコンピューティングのバックボーンです。どちらの状況でどのアルゴリズムを使用するかを選択することで、良いプログラマーと平均を区別できます。そのことを念頭に置いて、そこにはいくつかの基本的なアルゴリズムの定義とコード例があります。
挿入ソート
挿入ソートは、コンピュータサイエンスのより基本的なアルゴリズムの1つです。挿入ソートは、コレクションを反復処理して要素をランク付けし、その値に基づいて要素を配置します。セットはソートされた半分とソートされていない半分に分割され、すべての要素がソートされるまで繰り返されます。挿入ソートには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
}
}
挿入ソート
挿入ソートは、コンピュータサイエンスのより基本的なアルゴリズムの1つです。挿入ソートは、コレクションを反復処理して要素をランク付けし、その値に基づいて要素を配置します。セットはソートされた半分とソートされていない半分に分割され、すべての要素がソートされるまで繰り返されます。挿入ソートには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）の複雑さを持っていますが、それは対応するものよりも遅いと考えられます - 選択ソート。
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は高度なアルゴリズムの1つです。時間複雑度がO（n log n）であり、除算＆征服戦略が適用されます。この組合せにより、高度なアルゴリズム性能が得られる。クイックソートは、まず大きいアレイを2つの小さなサブアレイ、すなわち低エレメントと高エレメントに分割します。 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
}
選択ソート
選択ソートはその単純さのために示されています。配列の最初の要素から始まり、最小値（またはソート順に応じて最大値）として値が保存されます。その後、配列全体を繰り返し、最小値を他の値よりも小さく置き換えます。その最小値が配列の左端部に配置され、次のインデックスから配列の最後までプロセスが繰り返されます。選択ソートは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
}
漸近分析
私たちにはさまざまなアルゴリズムが用意されているので、配列をソートしたいときは、どちらを行うかを知る必要があります。したがって、アルゴリズムの速度と信頼性を測定する方法が必要です。それは漸近分析が始まるところです。漸近分析は、入力サイズ（n）が増加するにつれアルゴリズムの効率を記述するプロセスです。コンピュータ科学では、asymptoticsは通常Big O Notationと呼ばれる一般的な形式で表現されます。
- 線形時間O（n） ：関数が目的を達成するために配列の各項目を評価する必要がある場合、要素の数が増えるにつれ関数の効率が低下することを意味します。 このような関数は、その速度が入力サイズに依存するため、線形時間で実行されると言われています。
- 多項式時間O（n2） ：関数の複雑さが指数関数的に増加する場合（関数の配列のn要素がn乗の2乗であることを意味する）、その関数は多項式時間で動作します。これらは通常、ネストされたループを持つ関数です。 2つのネストされたループはO（n2）の複雑さをもたらし、3つのネストされたループはO（n3）の複雑さをもたらす。
- 対数時間O（log n）：対数時間関数の複雑さは、入力（n）のサイズが大きくなると最小になります。これらはプログラマーが目指す機能のタイプです。
クイックソート - O（n log n）の複雑さの時間
Quicksortは高度なアルゴリズムの1つです。時間複雑度がO（n log n）であり、除算＆征服戦略が適用されます。この組合せにより、高度なアルゴリズム性能が得られる。クイックソートは、まず大きいアレイを2つの小さなサブアレイ、すなわち低エレメントと高エレメントに分割します。 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}
mutation 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..")
}
}
トライ
コンピュータサイエンスでは、デジタルツリーとも呼ばれ、時には基数ツリーやプレフィックスツリー（接頭辞で検索できるように）と呼ばれるトライは、一種の検索ツリーです。これは、動的な集合や連想を格納するために使用される順序付けられたツリーデータ構造ですキーは通常文字列です。 （ウィキペディア、 ソース ）
//
// 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の2つの主要な操作を持つ、要素のコレクションとして機能する抽象データ型です。要素がスタックから外れる順序は、代替名LIFO（後入れ先出し）を発生させます。さらに、ピーク動作は、スタックを変更することなくトップにアクセスすることができる。 （ウィキペディア、 ソース ）
下記のライセンス情報とオリジナルコードソース（ 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.
本ソフトウェアおよび関連するドキュメンテーションファイル（以下「本ソフトウェア」といいます）のコピーを取得した者は、本ソフトウェアを制限なく使用、複製、改変、マージする権利を含むがこれに限定されるものではなく、本ソフトウェアのコピーを発行、配布、サブライセンス許諾、および/または販売すること、および本ソフトウェアが提供されている人に、以下の条件に従うことを許可すること。
上記の著作権表示およびこの許可通知は、本ソフトウェアのすべてのコピーまたは実質的な部分に含まれるものとします。
本ソフトウェアは、商品性、特定の目的への適合性および非侵害性の保証を含むが、明示的または黙示的ないかなる保証もなく、現状のまま提供されます。作者または著作権者は、いかなる場合も、本ソフトウェアまたはその使用に関連して発生したものであっても、その使用に起因するものであっても、契約違反、その他の損害賠償その他の損害賠償の責任は負わないものとします。ソフトウェア。
