Sorting Algorithms Compared

Ever wondered how sorting algorithms looked in Swift? I did too — so I implemented some. Below you can find the following:

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quicksort

As a preface: some of the algorithms use a self-implemented swap function — it is as follows:

extension Array {
    mutating func swap(i: Int, _ j: Int) {
        (self[i], self[j]) = (self[j], self[i])
    }
}

Bubble Sort

func bubbleSort(var unsorted: Array<Int>) -> Array<Int> {
    for i in 0..<unsorted.count - 1 {
        for j in 0..<unsorted.count - i - 1 {
            if unsorted[j] > unsorted[j + 1] {
                unsorted.swap(j, j + 1)
            }
        }
    }
    
    return unsorted
}

Selection Sort

func selectionSort(var unsorted: Array<Int>) -> Array<Int> {
    for i in 0..<unsorted.count - 1 {
        var minimumIndex = i
        for j in i + 1 ..< unsorted.count {
            if unsorted[j] < unsorted[minimumIndex] {
                minimumIndex = j
            }
            unsorted.swap(minimumIndex, i)
        }
    }
    
    return unsorted
}

Insertion Sort

func insertionSort(var unsorted: Array<Int>) -> Array<Int> {
    for j in 1...unsorted.count - 1 {
        let key = unsorted[j];
        var i = j - 1
        
        while i >= 0 && unsorted[i] > key {
            unsorted[i + 1] = unsorted[i]
            i--
        }
        
        unsorted[i + 1] = key
    }
    
    return unsorted
}

Merge Sort

func merge(leftArray left: Array<Int>, rightArray right: Array<Int>) -> Array<Int> {
    var result = [Int]()
    var leftIndex = 0, rightIndex = 0
    
    // Calculated variable to determine if the indexes have reached end of their respective arrays
    var indexesHaveReachedEndOfArrays: Bool { return leftIndex < left.count && rightIndex < right.count }
    
    while indexesHaveReachedEndOfArrays {
        if left[leftIndex] < right[rightIndex] {
            result.append(left[leftIndex])
            leftIndex++
        }
        else if left[leftIndex] > right[rightIndex] {
            result.append(right[rightIndex])
            rightIndex++
        }
        else {
            result.append(left[leftIndex])
            result.append(right[rightIndex])
            
            leftIndex++
            rightIndex++
        }
    }
    
    result += Array(left[leftIndex..<left.count])
    result += Array(right[rightIndex..<right.count])
    
    return result
}

func mergesort(unsorted: Array<Int>) -> Array<Int> {
    let size = unsorted.count
    if size < 2 { return unsorted }
    
    let split = Int(size / 2)
    
    let left = Array(unsorted[0 ..< split])
    let right = Array(unsorted[split ..< size])
    
    let sorted = merge(leftArray: mergesort(left), rightArray: mergesort(right))
    return sorted
}

Quick Sort

func quicksort(var unsorted: Array<Int>) -> Array<Int> {
    quicksort(&unsorted, firstIndex: 0, lastIndex: unsorted.count - 1)
    return unsorted
}

private func quicksort(inout unsorted: Array<Int>, firstIndex: Int, lastIndex: Int) -> Array<Int> {
    if firstIndex < lastIndex {
        let split = partition(&unsorted, firstIndex: firstIndex, lastIndex: lastIndex)
        
        quicksort(&unsorted, firstIndex: firstIndex, lastIndex: split - 1)
        quicksort(&unsorted, firstIndex: split + 1, lastIndex: lastIndex)
    }
    
    return unsorted
}

private func partition(inout unsorted: Array<Int>, firstIndex: Int, lastIndex: Int) -> Int {
    let pivot = unsorted[lastIndex]
    var wall = firstIndex
    
    for i in firstIndex ... lastIndex - 1 {
        if unsorted[i] <= pivot {
            unsorted.swap(wall, i)
            wall++
        }
    }
    
    unsorted.swap(wall, lastIndex)
    return wall
}