Swift Language
Algoritmen met Swift
Zoeken…
Invoering
Algoritmen vormen een ruggengraat voor computers. Een keuze maken welk algoritme te gebruiken in welke situatie een gemiddelde van een goede programmeur onderscheidt. Met dat in gedachten, zijn hier definities en codevoorbeelden van enkele van de basisalgoritmen die er zijn.
Invoegsortering
Invoegsortering is een van de meer basale algoritmen in de informatica. De invoegsortering rangschikt elementen door een verzameling te doorlopen en plaatst elementen op basis van hun waarde. De set is verdeeld in gesorteerde en ongesorteerde helften en herhaalt zich totdat alle elementen zijn gesorteerd. Invoegsortering heeft complexiteit van O (n2). Je kunt het in een extensie plaatsen, zoals in een voorbeeld hieronder, of je kunt er een methode voor maken.
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
}
}
sorteer-
Bubble Sort
Dit is een eenvoudig sorteeralgoritme dat herhaaldelijk de te sorteren lijst doorloopt, elk paar aangrenzende items vergelijkt en ze verwisselt als ze in de verkeerde volgorde staan. De doorloop door de lijst wordt herhaald totdat er geen swaps nodig zijn. Hoewel het algoritme eenvoudig is, is het voor de meeste problemen te traag en onpraktisch. Het heeft de complexiteit van O (n2), maar het wordt als langzamer beschouwd dan het invoegtype.
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
}
}
Soort invoeging
Invoegsortering is een van de meer basale algoritmen in de informatica. De invoegsortering rangschikt elementen door een verzameling te doorlopen en plaatst elementen op basis van hun waarde. De set is verdeeld in gesorteerde en ongesorteerde helften en herhaalt zich totdat alle elementen zijn gesorteerd. Invoegsortering heeft complexiteit van O (n2). Je kunt het in een extensie plaatsen, zoals in een voorbeeld hieronder, of je kunt er een methode voor maken.
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
}
}
Selectie sorteren
Selectie sorteren staat bekend om zijn eenvoud. Het begint met het eerste element in de array, waarbij de waarde wordt opgeslagen als een minimumwaarde (of maximum, afhankelijk van de sorteervolgorde). Het doorloopt dan de array en vervangt de min-waarde door een andere waarde kleiner dan min die het onderweg aantreft. Die minimumwaarde wordt vervolgens aan het meest linkse deel van de array geplaatst en het proces wordt vanaf de volgende index herhaald tot het einde van de array. Selectie sorteren heeft complexiteit van O (n2), maar het wordt langzamer beschouwd dan zijn tegenhanger - Selectie sorteren.
func selectionSort () -> Array {// 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
}
Quick Sort - O (n log n) complexiteitstijd
Quicksort is een van de geavanceerde algoritmen. Het heeft een tijdcomplexiteit van O (n log n) en past een verdeel- en heersstrategie toe. Deze combinatie resulteert in geavanceerde algoritmische prestaties. Quicksort verdeelt eerst een grote array in twee kleinere subarrays: de lage elementen en de hoge elementen. Quicksort kan vervolgens de subarrays recursief sorteren.
De stappen zijn:
Kies een element, een pivot genoemd, uit de array.
Rangschik de array zodanig dat alle elementen met waarden kleiner dan de pivot vóór de pivot komen, terwijl alle elementen met waarden groter dan de pivot erna komen (gelijke waarden kunnen alle kanten op). Na deze verdeling bevindt de spil zich in zijn definitieve positie. Dit wordt de partitie-bewerking genoemd.
Pas de bovenstaande stappen recursief toe op de subarray van elementen met kleinere waarden en afzonderlijk op de subarray van elementen met grotere waarden.
muting 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
}
Selectie sorteren
Selectie sorteren staat bekend om zijn eenvoud. Het begint met het eerste element in de array, waarbij de waarde wordt opgeslagen als een minimumwaarde (of maximum, afhankelijk van de sorteervolgorde). Het doorloopt dan de array en vervangt de min-waarde door een andere waarde kleiner dan min die het onderweg aantreft. Die minimumwaarde wordt vervolgens aan het meest linkse deel van de array geplaatst en het proces wordt vanaf de volgende index herhaald tot het einde van de array. Selectie sorteren heeft complexiteit van O (n2), maar het wordt langzamer beschouwd dan zijn tegenhanger - Selectie sorteren.
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
}
Asymptotische analyse
Omdat we uit veel verschillende algoritmen kunnen kiezen, moeten we, wanneer we een array willen sorteren, weten welke het doet. We hebben dus een methode nodig om de snelheid en betrouwbaarheid van algoritmen te meten. Dat is waar Asymptotische analyse van start gaat. Asymptotische analyse is het proces van het beschrijven van de efficiëntie van algoritmen naarmate hun inputgrootte (n) groeit. In de informatica worden asymptotiek meestal uitgedrukt in een algemeen formaat dat Big O Notation wordt genoemd.
- Lineaire tijd O (n) : wanneer elk item in de array moet worden geëvalueerd om een functie het doel te laten bereiken, betekent dit dat de functie minder efficiënt wordt naarmate het aantal elementen toeneemt. Van een dergelijke functie wordt gezegd dat deze in lineaire tijd werkt, omdat de snelheid ervan afhankelijk is van de invoergrootte.
- Polynominale tijd O (n2) : als de complexiteit van een functie exponentieel groeit (wat betekent dat voor n elementen van een array de complexiteit van een functie n kwadraat is), functioneert die functie in polynominale tijd. Dit zijn meestal functies met geneste lussen. Twee geneste lussen resulteren in O (n2) complexiteit, drie geneste lussen resulteren in O (n3) complexiteit, enzovoort ...
- Logaritmische tijd O (log n): de complexiteit van logaritmische tijdfuncties wordt geminimaliseerd wanneer de grootte van de invoer (n) groeit. Dit zijn het soort functies waar elke programmeur naar streeft.
Quick Sort - O (n log n) complexiteitstijd
Quicksort is een van de geavanceerde algoritmen. Het heeft een tijdcomplexiteit van O (n log n) en past een verdeel- en heersstrategie toe. Deze combinatie resulteert in geavanceerde algoritmische prestaties. Quicksort verdeelt eerst een grote array in twee kleinere subarrays: de lage elementen en de hoge elementen. Quicksort kan vervolgens de subarrays recursief sorteren.
De stappen zijn:
Kies een element, een pivot genoemd, uit de array.
Rangschik de array zodanig dat alle elementen met waarden kleiner dan de pivot vóór de pivot komen, terwijl alle elementen met waarden groter dan de pivot erna komen (gelijke waarden kunnen alle kanten op). Na deze verdeling bevindt de spil zich in zijn definitieve positie. Dit wordt de partitie-bewerking genoemd.
Pas de bovenstaande stappen recursief toe op de subarray van elementen met kleinere waarden en afzonderlijk op de subarray van elementen met grotere waarden.
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}
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
}
Grafiek, Trie, Stapel
diagram
In de informatica is een grafiek een abstract gegevenstype dat bedoeld is om de niet-gerichte grafiek en gerichte grafiekconcepten uit de wiskunde te implementeren. Een grafiekgegevensstructuur bestaat uit een eindige (en mogelijk muteerbare) set hoekpunten of knooppunten of punten, samen met een set niet-geordende paren van deze hoekpunten voor een niet-gerichte grafiek of een set geordende paren voor een gerichte grafiek. Deze paren staan bekend als randen, bogen of lijnen voor een niet-gerichte grafiek en als pijlen, gerichte randen, gerichte bogen of gerichte lijnen voor een gerichte grafiek. De hoekpunten kunnen deel uitmaken van de grafiekstructuur of kunnen externe entiteiten zijn die worden voorgesteld door gehele indexen of verwijzingen. Een grafische gegevensstructuur kan ook aan elke rand een randwaarde koppelen, zoals een symbolisch label of een numeriek attribuut (kosten, capaciteit, lengte, enz.). (Wikipedia, bron )
//
// 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..")
}
}
proberen
In de informatica is een trie, ook wel digitale boom en soms radixboom of prefixboom genoemd (omdat ze door prefixen kunnen worden doorzocht), een soort zoekboom - een geordende boomgegevensstructuur die wordt gebruikt om een dynamische set of associatieve op te slaan array waarin de toetsen meestal tekenreeksen zijn. (Wikipedia, bron )
//
// 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, bron )
stack
In de informatica is een stapel een abstract gegevenstype dat dient als een verzameling elementen, met twee hoofdbewerkingen: push, waarmee een element aan de verzameling wordt toegevoegd, en pop, waarmee het meest recent toegevoegde element wordt verwijderd dat nog niet is verwijderd. De volgorde waarin elementen van een stapel komen, geeft aanleiding tot zijn alternatieve naam, LIFO (voor last in, first out). Bovendien kan een gluurbewerking toegang geven tot de top zonder de stapel te wijzigen. (Wikipedia, bron )
Zie licentie-informatie hieronder en originele codebron op ( 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
}
}
}
De MIT-licentie (MIT)
Copyright (c) 2015, Wayne Bishop & Arbutus Software Inc.
Hierbij wordt kosteloos toestemming verleend aan elke persoon die een kopie van deze software en bijbehorende documentatiebestanden (de "Software") verkrijgt, om zonder beperkingen in de Software te handelen, inclusief zonder beperking de rechten op gebruik, kopiëren, wijzigen, samenvoegen , kopieën van de Software publiceren, distribueren, in sublicentie geven en / of verkopen, en om personen aan wie de Software is verstrekt dit toe te staan, onder de volgende voorwaarden:
De bovenstaande copyrightkennisgeving en deze toestemmingskennisgeving zijn opgenomen in alle kopieën of substantiële delen van de Software.
DE SOFTWARE WORDT GELEVERD "ZOALS ZE ZIJN", ZONDER ENIGE VORM VAN GARANTIE, EXPLICIET OF IMPLICIET, INCLUSIEF MAAR NIET BEPERKT TOT DE GARANTIES VAN VERKOOPBAARHEID, GESCHIKTHEID VOOR EEN BEPAALD DOEL EN NIET-INBREUK. IN GEEN GEVAL ZIJN DE AUTEURS OF AUTEURSRECHTHOUDERS AANSPRAKELIJK VOOR ENIGE VORDERING, SCHADE OF ANDERE AANSPRAKELIJKHEID, OOK IN EEN HANDELING VAN OVEREENKOMST, SCHORT OF ANDERSZINS DIE VOORTVLOEIT UIT, IN OF IN VERBAND MET DE SOFTWARE OF HET GEBRUIK OF ANDERE HANDELINGEN IN DE SOFTWARE.