Swift Language
Algoritmos con Swift
Buscar..
Introducción
Los algoritmos son una columna vertebral de la computación. Al elegir qué algoritmo usar en qué situación se distingue un promedio de un buen programador. Con eso en mente, aquí hay definiciones y ejemplos de código de algunos de los algoritmos básicos que hay.
Tipo de inserción
El tipo de inserción es uno de los algoritmos más básicos en informática. La ordenación por inserción clasifica los elementos mediante la iteración a través de una colección y coloca los elementos en función de su valor. El conjunto se divide en mitades ordenadas y no clasificadas y se repite hasta que se ordenan todos los elementos. La ordenación por inserción tiene una complejidad de O (n2). Puede ponerlo en una extensión, como en un ejemplo a continuación, o puede crear un método para ello.
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
}
}
Clasificación
Ordenamiento de burbuja
Este es un algoritmo de clasificación simple que recorre repetidamente la lista para ser ordenado, compara cada par de elementos adyacentes y los intercambia si están en el orden incorrecto. El paso por la lista se repite hasta que no se necesiten swaps. Aunque el algoritmo es simple, es demasiado lento y poco práctico para la mayoría de los problemas. Tiene una complejidad de O (n2) pero se considera más lenta que la ordenación por inserción.
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
}
}
Tipo de inserción
El tipo de inserción es uno de los algoritmos más básicos en informática. La ordenación por inserción clasifica los elementos mediante la iteración a través de una colección y coloca los elementos en función de su valor. El conjunto se divide en mitades ordenadas y no clasificadas y se repite hasta que se ordenan todos los elementos. La ordenación por inserción tiene una complejidad de O (n2). Puede ponerlo en una extensión, como en un ejemplo a continuación, o puede crear un método para ello.
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
}
}
Selección de selección
La selección por selección se caracteriza por su simplicidad. Comienza con el primer elemento de la matriz, guardando su valor como un valor mínimo (o máximo, dependiendo del orden de clasificación). Luego se itera a través de la matriz y reemplaza el valor mínimo por cualquier otro valor menor que el mínimo que encuentre en el camino. Ese valor mínimo se coloca en la parte más a la izquierda de la matriz y el proceso se repite, desde el siguiente índice, hasta el final de la matriz. La clasificación de selección tiene una complejidad de O (n2) pero se considera más lenta que su contraparte: la clasificación de selección.
func selectionSort () -> Array {// verifica si hay un caso de guardia de caso trivial> 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
}
Ordenación rápida: tiempo de complejidad O (n log n)
Quicksort es uno de los algoritmos avanzados. Cuenta con una complejidad de tiempo de O (n log n) y aplica una estrategia de dividir y conquistar. Esta combinación da como resultado un rendimiento algorítmico avanzado. Quicksort primero divide una gran matriz en dos sub-matrices más pequeñas: los elementos bajos y los elementos altos. Quicksort luego puede ordenar recursivamente los subarreglos.
Los pasos son:
Elija un elemento, llamado pivote, de la matriz.
Reordene la matriz para que todos los elementos con valores menores que el pivote aparezcan antes que el pivote, mientras que todos los elementos con valores mayores que el pivote aparezcan después (los valores iguales pueden ir en cualquier dirección). Después de esta partición, el pivote está en su posición final. Esto se llama la operación de partición.
Aplique recursivamente los pasos anteriores a la sub-matriz de elementos con valores más pequeños y por separado a la sub-matriz de elementos con valores mayores.
función mutante 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
}
Selección de selección
La selección por selección se caracteriza por su simplicidad. Comienza con el primer elemento de la matriz, guardando su valor como un valor mínimo (o máximo, dependiendo del orden de clasificación). Luego se itera a través de la matriz y reemplaza el valor mínimo por cualquier otro valor menor que el mínimo que encuentre en el camino. Ese valor mínimo se coloca en la parte más a la izquierda de la matriz y el proceso se repite, desde el siguiente índice, hasta el final de la matriz. La clasificación de selección tiene una complejidad de O (n2) pero se considera más lenta que su contraparte: la clasificación de selección.
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
}
Análisis asintótico
Dado que tenemos muchos algoritmos diferentes para elegir, cuando queremos ordenar una matriz, necesitamos saber cuál hará su trabajo. Así que necesitamos algún método para medir la velocidad y confiabilidad de algoritm. Ahí es donde comienza el análisis asintótico. El análisis asintótico es el proceso de describir la eficiencia de los algoritmos a medida que crece el tamaño de entrada (n). En ciencias de la computación, los asintóticos generalmente se expresan en un formato común conocido como Big O Notation.
- Tiempo lineal O (n) : cuando cada elemento de la matriz debe evaluarse para que una función alcance su objetivo, eso significa que la función se vuelve menos eficiente a medida que aumenta la cantidad de elementos. Se dice que una función como esta se ejecuta en tiempo lineal porque su velocidad depende de su tamaño de entrada.
- Tiempo polinominal O (n2) : si la complejidad de una función crece exponencialmente (lo que significa que para n elementos de una matriz la complejidad de una función es n al cuadrado), esa función opera en tiempo polinominal. Estas suelen ser funciones con bucles anidados. Dos bucles anidados dan como resultado una complejidad O (n2), tres bucles anidados dan como resultado una complejidad O (n3), y así sucesivamente ...
- Tiempo logarítmico O (log n): la complejidad de las funciones de tiempo logarítmico se minimiza cuando el tamaño de sus entradas (n) aumenta. Estos son el tipo de funciones por las que se esfuerza todo programador.
Ordenación rápida: tiempo de complejidad O (n log n)
Quicksort es uno de los algoritmos avanzados. Cuenta con una complejidad de tiempo de O (n log n) y aplica una estrategia de dividir y conquistar. Esta combinación da como resultado un rendimiento algorítmico avanzado. Quicksort primero divide una gran matriz en dos sub-matrices más pequeñas: los elementos bajos y los elementos altos. Quicksort luego puede ordenar recursivamente los subarreglos.
Los pasos son:
Elija un elemento, llamado pivote, de la matriz.
Reordene la matriz para que todos los elementos con valores menores que el pivote aparezcan antes que el pivote, mientras que todos los elementos con valores mayores que el pivote aparezcan después (los valores iguales pueden ir en cualquier dirección). Después de esta partición, el pivote está en su posición final. Esto se llama la operación de partición.
Aplique recursivamente los pasos anteriores a la sub-matriz de elementos con valores más pequeños y por separado a la sub-matriz de elementos con valores mayores.
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}
función de mutación qPartición (iniciar índice de inicio: Int, _ pivote: 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
}
Gráfico, trie, pila
Grafico
En ciencias de la computación, un gráfico es un tipo de datos abstractos destinado a implementar el gráfico no dirigido y los conceptos de gráficos dirigidos de las matemáticas. Una estructura de datos de gráfico consta de un conjunto finito (y posiblemente mutable) de vértices o nodos o puntos, junto con un conjunto de pares desordenados de estos vértices para un gráfico no dirigido o un conjunto de pares ordenados para un gráfico dirigido. Estos pares se conocen como bordes, arcos o líneas para un gráfico no dirigido y como flechas, bordes dirigidos, arcos dirigidos o líneas dirigidas para un gráfico dirigido. Los vértices pueden formar parte de la estructura del gráfico o pueden ser entidades externas representadas por índices o referencias de números enteros. Una estructura de datos de gráfico también puede asociar a cada borde algún valor de borde, como una etiqueta simbólica o un atributo numérico (costo, capacidad, longitud, etc.). (Wikipedia, fuente )
//
// 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 informática, un trie, también denominado árbol digital y, a veces, árbol de prefijo o árbol de prefijo (ya que pueden buscarse por prefijos), es un tipo de árbol de búsqueda: una estructura de datos de árbol ordenado que se utiliza para almacenar un conjunto dinámico o asociativo. Matriz donde las claves suelen ser cadenas. (Wikipedia, fuente )
//
// 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, fuente )
Apilar
En informática, una pila es un tipo de datos abstracto que sirve como una colección de elementos, con dos operaciones principales: push, que agrega un elemento a la colección, y pop, que elimina el elemento agregado más reciente que aún no se eliminó. El orden en que los elementos salen de una pila da origen a su nombre alternativo, LIFO (para el último en entrar, el primero en salir). Además, una operación de inspección puede dar acceso a la parte superior sin modificar la pila. (Wikipedia, fuente )
Consulte la información de la licencia a continuación y la fuente del código original en ( 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 licencia MIT (MIT)
Copyright (c) 2015, Wayne Bishop & Arbutus Software Inc.
Por la presente, se otorga el permiso, sin cargo, a cualquier persona que obtenga una copia de este software y los archivos de documentación asociados (el "Software"), para operar el Software sin restricciones, incluidos, entre otros, los derechos de uso, copia, modificación, fusión. , publicar, distribuir, sublicenciar y / o vender copias del Software, y para permitir que las personas a quienes se suministra el Software lo hagan, sujeto a las siguientes condiciones:
El aviso de copyright anterior y este aviso de permiso se incluirán en todas las copias o partes sustanciales del Software.
EL SOFTWARE SE PROPORCIONA "TAL CUAL", SIN GARANTÍA DE NINGÚN TIPO, EXPRESO O IMPLÍCITO, INCLUYENDO PERO NO LIMITADO A LAS GARANTÍAS DE COMERCIABILIDAD, IDONEIDAD PARA UN PROPÓSITO PARTICULAR Y NO INCUMPLIMIENTO. EN NINGÚN CASO, LOS AUTORES O TITULARES DE DERECHOS DE AUTOR SERÁN RESPONSABLES POR CUALQUIER RECLAMACIÓN, DAÑOS U OTRAS RESPONSABILIDADES, YA QUE SEA RESPONSABLE DE UN CONTRATO, CORTE U OTRA MANERA, DERIVADOS DE, FUERA O EN CONEXIÓN CON EL SOFTWARE O EL USO U OTRAS REPARACIONES EN EL SOFTWARE.
