Swift Language Algorithms with Swift Sorting

Example

Bubble Sort

This is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed. Although the algorithm is simple, it is too slow and impractical for most problems. It has complexity of O(n2) but it is considered slower than insertion sort.

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
}

}

Insertion sort

Insertion sort is one of the more basic algorithms in computer science. The insertion sort ranks elements by iterating through a collection and positions elements based on their value. The set is divided into sorted and unsorted halves and repeats until all elements are sorted. Insertion sort has complexity of O(n2). You can put it in an extension, like in an example below, or you can create a method for it.

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
}
}

Selection sort

Selection sort is noted for its simplicity. It starts with the first element in the array, saving it's value as a minimum value (or maximum, depending on sorting order). It then itterates through the array, and replaces the min value with any other value lesser then min it finds on the way. That min value is then placed at the leftmost part of the array and the process is repeated, from the next index, until the end of the array. Selection sort has complexity of O(n2) but it is considered slower than it's counterpart - Selection sort.

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) complexity time

Quicksort is one of the advanced algorithms. It features a time complexity of O(n log n) and applies a divide & conquer strategy. This combination results in advanced algorithmic performance. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays.

The steps are:

Pick an element, called a pivot, from the array.

Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.

Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

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
}