Swift Language
Algorithmes avec Swift
Recherche…
Introduction
Les algorithmes sont l'épine dorsale de l'informatique. Faire un choix de l'algorithme à utiliser dans quelle situation distingue une moyenne d'un bon programmeur. Dans cet esprit, voici des définitions et des exemples de code de certains des algorithmes de base disponibles.
Tri par insertion
Le tri par insertion est l'un des algorithmes les plus élémentaires en informatique. Le tri par insertion classe les éléments en effectuant une itération dans une collection et positionne les éléments en fonction de leur valeur. L'ensemble est divisé en deux parties triées et non triées et se répète jusqu'à ce que tous les éléments soient triés. Le tri par insertion a une complexité de O (n2). Vous pouvez le mettre dans une extension, comme dans un exemple ci-dessous, ou vous pouvez créer une méthode pour cela.
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
}
}
Tri
Tri à bulles
Il s'agit d'un algorithme de tri simple qui passe en revue de manière répétée la liste à trier, compare chaque paire d'éléments adjacents et les échange s'ils sont dans le mauvais ordre. Le passage dans la liste est répété jusqu'à ce qu'aucun échange ne soit nécessaire. Bien que l'algorithme soit simple, il est trop lent et peu pratique pour la plupart des problèmes. Il a la complexité de O (n2) mais il est considéré comme plus lent que le tri par insertion.
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
}
}
Tri par insertion
Le tri par insertion est l'un des algorithmes les plus élémentaires en informatique. Le tri par insertion classe les éléments en effectuant une itération dans une collection et positionne les éléments en fonction de leur valeur. L'ensemble est divisé en deux parties triées et non triées et se répète jusqu'à ce que tous les éléments soient triés. Le tri par insertion a une complexité de O (n2). Vous pouvez le mettre dans une extension, comme dans un exemple ci-dessous, ou vous pouvez créer une méthode pour cela.
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
}
}
Tri de sélection
Le tri de sélection est noté pour sa simplicité. Il commence par le premier élément du tableau, en sauvegardant sa valeur en tant que valeur minimale (ou maximale, en fonction de l'ordre de tri). Il itère ensuite à travers le tableau et remplace la valeur min par toute autre valeur inférieure à min qu'elle trouve sur le chemin. Cette valeur min est alors placée à l'extrême gauche du tableau et le processus est répété, à partir de l'index suivant, jusqu'à la fin du tableau. Le tri par sélection a une complexité de O (n2) mais il est considéré comme plus lent que son homologue - Tri par sélection.
func selectionSort () -> Array {// vérifie la casse triviale 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
}
Tri rapide - O (n log n) temps de complexité
Quicksort est l'un des algorithmes avancés. Il présente une complexité temporelle de O (n log n) et applique une stratégie de division et de conquête. Cette combinaison se traduit par des performances algorithmiques avancées. Quicksort commence par diviser un grand tableau en deux sous-tableaux plus petits: les éléments bas et les éléments hauts. Quicksort peut ensuite trier récursivement les sous-tableaux.
Les étapes sont les suivantes:
Choisissez un élément, appelé pivot, dans le tableau.
Réorganisez le tableau de manière à ce que tous les éléments dont les valeurs sont inférieures au pivot arrivent avant le pivot, alors que tous les éléments dont les valeurs sont supérieures au pivot le suivent (les valeurs égales peuvent aller dans les deux sens). Après ce partitionnement, le pivot est dans sa position finale. Cela s'appelle l'opération de partition.
Appliquez récursivement les étapes ci-dessus au sous-tableau d'éléments avec des valeurs plus petites et séparément au sous-tableau d'éléments avec des valeurs supérieures.
func mutant 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
}
Tri de sélection
Le tri de sélection est noté pour sa simplicité. Il commence par le premier élément du tableau, en sauvegardant sa valeur en tant que valeur minimale (ou maximale, en fonction de l'ordre de tri). Il itère ensuite à travers le tableau et remplace la valeur min par toute autre valeur inférieure à min qu'elle trouve sur le chemin. Cette valeur min est alors placée à l'extrême gauche du tableau et le processus est répété, à partir de l'index suivant, jusqu'à la fin du tableau. Le tri par sélection a une complexité de O (n2) mais il est considéré comme plus lent que son homologue - Tri par sélection.
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
}
Analyse asymptotique
Comme nous avons le choix entre de nombreux algorithmes, lorsque nous voulons trier un tableau, nous devons savoir lequel fera son travail. Nous avons donc besoin d'une méthode pour mesurer la vitesse et la fiabilité de l'algoritm. C'est là qu'intervient l'analyse asymptotique. L'analyse asymptotique consiste à décrire l'efficacité des algorithmes au fur et à mesure que leur taille d'entrée (n) augmente. En informatique, les asymptotiques sont généralement exprimés dans un format commun appelé Big O Notation.
- Temps linéaire O (n) : Lorsque chaque élément du tableau doit être évalué pour qu'une fonction atteigne son objectif, cela signifie que la fonction devient moins efficace à mesure que le nombre d'éléments augmente. Une fonction comme celle-ci est dite fonctionner en temps linéaire car sa vitesse dépend de sa taille d'entrée.
- Temps polynominal O (n2) : si la complexité d'une fonction augmente de manière exponentielle (c'est-à-dire que pour n éléments d'une complexité de tableau d'une fonction est n au carré), cette fonction opère en temps polynominal. Ce sont généralement des fonctions avec des boucles imbriquées. Deux boucles imbriquées entraînent une complexité O (n2), trois boucles imbriquées entraînent une complexité O (n3), etc.
- Temps logarithmique O (log n): la complexité des fonctions de temps logarithmiques est minimisée lorsque la taille de ses entrées (n) augmente. Ce sont les types de fonctions que tout programmeur recherche.
Tri rapide - O (n log n) temps de complexité
Quicksort est l'un des algorithmes avancés. Il présente une complexité temporelle de O (n log n) et applique une stratégie de division et de conquête. Cette combinaison se traduit par des performances algorithmiques avancées. Quicksort commence par diviser un grand tableau en deux sous-tableaux plus petits: les éléments bas et les éléments hauts. Quicksort peut ensuite trier récursivement les sous-tableaux.
Les étapes sont les suivantes:
Choisissez un élément, appelé pivot, dans le tableau.
Réorganisez le tableau de manière à ce que tous les éléments dont les valeurs sont inférieures au pivot arrivent avant le pivot, alors que tous les éléments dont les valeurs sont supérieures au pivot le suivent (les valeurs égales peuvent aller dans les deux sens). Après ce partitionnement, le pivot est dans sa position finale. Cela s'appelle l'opération de partition.
Appliquez récursivement les étapes ci-dessus au sous-tableau d'éléments avec des valeurs plus petites et séparément au sous-tableau d'éléments avec des valeurs supérieures.
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}
funcation mutante 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
}
Graph, Trie, Stack
Graphique
En informatique, un graphe est un type de données abstrait destiné à implémenter le graphe non orienté et les concepts de graphe orienté des mathématiques. Une structure de données de graphe consiste en un ensemble fini (et éventuellement mutable) de sommets ou de nœuds ou de points, ainsi qu’un ensemble de paires non ordonnées de ces sommets pour un graphe non orienté ou un ensemble de paires ordonnées pour un graphe orienté. Ces paires sont appelées arêtes, arcs ou lignes pour un graphe non orienté et comme flèches, arêtes dirigées, arcs orientés ou lignes dirigées pour un graphe orienté. Les sommets peuvent faire partie de la structure du graphe ou peuvent être des entités externes représentées par des index ou des références entiers. Une structure de données de graphique peut également associer à chaque arête une valeur de bord, telle qu'une étiquette symbolique ou un attribut numérique (coût, capacité, longueur, etc.). (Wikipedia, source )
//
// 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
En informatique, un trie, également appelé arborescence numérique et parfois arborescence radix ou préfixe (comme on peut le rechercher par préfixes), est une sorte d’arbre de recherche - une structure de données d’arbre ordonnée utilisée pour stocker un ensemble dynamique ou associatif. tableau où les clés sont généralement des chaînes. (Wikipedia, source )
//
// 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, source )
Empiler
En informatique, une pile est un type de données abstrait qui sert de collection d'éléments, avec deux opérations principales: push, qui ajoute un élément à la collection, et pop, qui supprime l'élément le plus récemment ajouté qui n'a pas encore été supprimé. L'ordre dans lequel les éléments sortent d'une pile donne son autre nom, LIFO (pour last in, first out). De plus, une opération de coup d’œil peut donner accès au sommet sans modifier la pile. (Wikipedia, source )
Voir les informations de licence ci-dessous et le code source d'origine à ( 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
}
}
}
La licence MIT (MIT)
Copyright (c) 2015, Wayne Bishop & Arbutus Software Inc.
Par la présente, toute personne obtenant une copie de ce logiciel et des fichiers de documentation associés (le «Logiciel»), sans restriction, y compris, sans limitation, les droits d’utilisation, de copie, de modification, de fusion, est autorisée. , publier, distribuer, concéder en sous-licence et / ou vendre des copies du logiciel, et autoriser les personnes à qui le logiciel est fourni à le faire, sous réserve des conditions suivantes:
L'avis de copyright ci-dessus et cet avis de permission doivent être inclus dans toutes les copies ou parties substantielles du logiciel.
LE LOGICIEL EST FOURNI "EN L'ÉTAT", SANS GARANTIE D'AUCUNE SORTE, EXPRESSE OU IMPLICITE, Y COMPRIS, MAIS SANS S'Y LIMITER, LES GARANTIES DE QUALITÉ MARCHANDE, D'ADÉQUATION À UN USAGE PARTICULIER ET DE NON-CONTREFAÇON. EN AUCUN CAS, LES AUTEURS OU LES TITULAIRES DE DROITS D'AUTEUR NE POURRONT ÊTRE TENUS RESPONSABLES D'UNE RÉCLAMATION, DOMMAGES OU AUTRE RESPONSABILITÉ, QUE CE SOIT PAR UN CONTRAT, UN TORT OU AUTRE, DÉCOULANT, HORS OU EN RELATION AVEC LE LOGICIEL OU LOGICIEL.
