Swift Language
Algoritmer med Swift
Sök…
Introduktion
Algoritmer är en ryggraden i datoranvändning. Att välja vilken algoritm som ska användas i vilken situation som skiljer ett medelvärde från bra programmerare. Med det i åtanke, här är definitioner och kodexempel på några av de grundläggande algoritmerna där ute.
Insättningssortering
Insertion sort är en av de mer grundläggande algoritmerna inom datavetenskap. Insättningen sorterar element genom att iterera igenom en samling och placerar element baserat på deras värde. Uppsättningen är indelad i sorterade och osorterade halvor och upprepas tills alla element är sorterade. Insättningssort har komplexitet O (n2). Du kan lägga den i ett tillägg, som i ett exempel nedan, eller så kan du skapa en metod för det.
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
}
}
Sortering
Bubble Sort
Detta är en enkel sorteringsalgoritm som flera gånger går igenom listan som ska sorteras, jämför varje par intilliggande objekt och byter dem om de är i fel ordning. Passet genom listan upprepas tills inga swappar behövs. Även om algoritmen är enkel är den för långsam och opraktisk för de flesta problem. Det har komplexitet O (n2) men det anses vara långsammare än insättningssortering.
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
}
}
Insättningssortering
Insertion sort är en av de mer grundläggande algoritmerna inom datavetenskap. Insättningen sorterar element genom att iterera igenom en samling och placerar element baserat på deras värde. Uppsättningen är indelad i sorterade och osorterade halvor och upprepas tills alla element är sorterade. Insättningssort har komplexitet O (n2). Du kan lägga den i ett tillägg, som i ett exempel nedan, eller så kan du skapa en metod för det.
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
}
}
Urvalssortering
Urvalssortering är känd för sin enkelhet. Det börjar med det första elementet i arrayen, vilket sparar sitt värde som ett minimivärde (eller maximalt, beroende på sorteringsordning). Den itterererar sedan genom matrisen och ersätter minvärdet med något annat värde som är mindre än min det hittar på vägen. Det minvärdet placeras sedan längst till vänster i matrisen och processen upprepas från nästa index till slutet av matrisen. Urvalssortering har komplexitet O (n2) men det anses vara långsammare än motsvarigheten - Urvalssortering.
func choiceSort () -> Array {// kolla efter triviala fallvakt self.count> 1 annat {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
}
Snabb sortering - O (n log n) komplexitetstid
Quicksort är en av de avancerade algoritmerna. Den har en tidskomplexitet för O (n log n) och tillämpar en divide & conquer-strategi. Denna kombination resulterar i avancerad algoritmisk prestanda. Quicksort delar först en stor matris i två mindre undergrupper: de låga elementen och de höga elementen. Quicksort kan sedan rekursivt sortera delmatriserna.
Stegen är:
Välj ett element, kallad en pivot, från matrisen.
Ordna om arrayen så att alla element med värden mindre än pivot kommer före pivot, medan alla element med värden större än pivot kommer efter den (lika värden kan gå åt båda hållen). Efter denna partitionering är pivoten i sin slutliga position. Detta kallas partitionsoperationen.
Använd rekursivt ovanstående steg på deluppsättningen av element med mindre värden och separat på undergruppen för element med större värden.
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
}
Urvalssortering
Urvalssortering är känd för sin enkelhet. Det börjar med det första elementet i arrayen, vilket sparar sitt värde som ett minimivärde (eller maximalt, beroende på sorteringsordning). Den itterererar sedan genom matrisen och ersätter minvärdet med något annat värde som är mindre än min det hittar på vägen. Det minvärdet placeras sedan längst till vänster i matrisen och processen upprepas från nästa index till slutet av matrisen. Urvalssortering har komplexitet O (n2) men det anses vara långsammare än motsvarigheten - Urvalssortering.
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
}
Asymptotisk analys
Eftersom vi har många olika algoritmer att välja mellan, och när vi vill sortera en matris, måste vi veta vilken som gör sitt jobb. Så vi behöver någon metod för att mäta algoritmens hastighet och tillförlitlighet. Det är där asymptotisk analys startar. Asymptotisk analys är processen för att beskriva effektiviteten hos algoritmer när deras input-storlek (n) växer. Inom datavetenskap uttrycks asymptotik vanligtvis i ett vanligt format som kallas Big O Notation.
- Linjär tid O (n) : När varje objekt i matrisen måste utvärderas för att en funktion ska uppnå sitt mål, betyder det att funktionen blir mindre effektiv när antalet element ökar. En funktion som denna sägs gå i linjär tid eftersom dess hastighet är beroende av dess ingångsstorlek.
- Polynominal tid O (n2) : Om komplexiteten hos en funktion växer exponentiell (vilket innebär att för n element i en matris är komplexiteten hos en funktion n kvadrat) fungerar den funktionen i polynominal tid. Dessa är vanligtvis funktioner med kapslade slingor. Två kapslade slingor resulterar i O (n2) komplexitet, tre kapslade slingor resulterar i O (n3) komplexitet, och så vidare ...
- Logaritmisk tid O (log n): Logaritmiska tidfunktioners komplexitet minimeras när storleken på dess ingångar (n) växer. Det här är den typ av funktioner som alla programmerare strävar efter.
Snabb sortering - O (n log n) komplexitetstid
Quicksort är en av de avancerade algoritmerna. Den har en tidskomplexitet för O (n log n) och tillämpar en divide & conquer-strategi. Denna kombination resulterar i avancerad algoritmisk prestanda. Quicksort delar först en stor matris i två mindre undergrupper: de låga elementen och de höga elementen. Quicksort kan sedan rekursivt sortera delmatriserna.
Stegen är:
Välj ett element, kallad en pivot, från matrisen.
Ordna om arrayen så att alla element med värden mindre än pivot kommer före pivot, medan alla element med värden större än pivot kommer efter den (lika värden kan gå åt båda hållen). Efter denna partitionering är pivoten i sin slutliga position. Detta kallas partitionsoperationen.
Använd rekursivt ovanstående steg på deluppsättningen av element med mindre värden och separat på undergruppen för element med större värden.
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}
mutera 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
}
Graf, Trie, Stack
Graf
Inom datavetenskap är en graf en abstrakt datatyp som är tänkt att implementera den riktade grafen och riktade grafkoncept från matematik. En grafdatastruktur består av en begränsad (och eventuellt muterbar) uppsättning av hörn eller noder eller punkter, tillsammans med en uppsättning av oordnade par av dessa hörn för en riktad kurva eller en uppsättning ordnade par för en riktad graf. Dessa par är kända som kanter, bågar eller linjer för en inriktad graf och som pilar, riktade kanter, riktade bågar eller riktade linjer för en riktad graf. Hörnpunkterna kan vara en del av grafstrukturen, eller kan vara externa enheter representerade av heltalindex eller referenser. En grafdatastruktur kan också associera till varje kant något kantvärde, såsom en symbolisk etikett eller ett numeriskt attribut (kostnad, kapacitet, längd, etc.). (Wikipedia, källa )
//
// 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
Inom datavetenskap är en trie, även kallad digital tree och ibland radix tree eller prefix tree (eftersom de kan sökas med prefix), ett slags sökträd - en ordnad träddatastruktur som används för att lagra en dynamisk uppsättning eller associativ array där nycklarna vanligtvis är strängar. (Wikipedia, källa )
//
// 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, källa )
Stack
Inom datavetenskap är en stack en abstrakt datatyp som fungerar som en samling av element, med två huvudoperationer: push, som lägger till ett element till samlingen, och pop, som tar bort det senast tillagda elementet som ännu inte togs bort. Ordningen i vilken element kommer från en bunt ger upphov till dess alternativa namn, LIFO (för sist in, först ut). En peekoperation kan dessutom ge åtkomst till toppen utan att ändra stacken. (Wikipedia, källa )
Se licensinformation nedan och originalkodkälla på ( 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-licensen (MIT)
Copyright (c) 2015, Wayne Bishop & Arbutus Software Inc.
Behörighet beviljas härmed kostnadsfritt till alla personer som skaffar en kopia av denna programvara och tillhörande dokumentationsfiler ("Programvaran"), för att handla i programvaran utan begränsning, inklusive utan begränsning rättigheterna att använda, kopiera, ändra, sammanfoga , publicera, distribuera, underlicensiera och / eller sälja kopior av programvaran och tillåta personer till vilka programvaran är inrättad att göra det, på följande villkor:
Ovanstående upphovsrättsmeddelande och meddelandet om tillstånd ska inkluderas i alla kopior eller väsentliga delar av programvaran.
PROGRAMVARAN LEVERAS "SOM ÄR", UTAN GARANTI AV NÅGON SIN, UTTRYCKLIGT ELLER IMPLICERAD, INKLUDERA MEN INTE BEGRÄNSAD TILL GARANTIERNA FÖR SÄLJBARHET, GODKOMST FÖR EN SÄRSKILT SYFTE OCH INNINFRING. Under inga händelser ska författarna eller upphovsrättsinnehavarna vara ansvariga för något krav, skador eller annan skyldighet, oavsett om det handlar om avtal, tort eller på annat sätt, uppstå från, i eller i anslutning till programvaran eller användningen eller andra handlingar i den PROGRAMVARA.