Must-Know Sorting Algorithms

• pros & cons + Swift Code Examples

So, why do we need to know sorting algorithms?

Algorithms are the backbone of programming, allowing developers to solve complex problems efficiently. Understanding and mastering fundamental algorithms is crucial for writing high-performance, scalable, and optimized code.

Moreover, it is one of the most popular questions in the job interview, so if you plan to apply for a new job or just want to know more about sorting algorithms, take a look at this article.

Bubble Sort

Bubble Sort is one of the simplest sorting algorithms, but it’s not very efficient for large data sets. It works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order.

Bubble Sort pros:

• Ease of Implementation: it is easy to understand and implement. Its simple logic makes it an accessible sorting algorithm for beginners to use.
• No Additional Memory Space: Bubble Sort operates in-place (it modifies the original array without requiring extra memory space for temporary storage).
• Stability: it is a stable sorting algorithm. When sorting elements with equal keys, their relative order in the original array remains preserved in the sorted output. This property is crucial in certain applications.

Bubble Sort cons:

• Time Complexity of O(N²): Bubble sort has a time complexity of O(N²), where N is the number of elements in the array. As the data set grows, the algorithm’s performance degrades significantly, making it inefficient for large datasets.
• Comparison-Based Algorithm: Being a comparison-based sorting algorithm, Bubble sort relies on a comparison operator to determine the order of elements. This can limit its efficiency, especially when dealing with complex data structures or custom comparison functions

//Bubble Sort Example

func bubbleSort<T: Comparable>(_ array: inout [T]) {
    let n = array.count
    for i in 0..<n {
        for j in 0..<(n-i-1) {
            if array[j] > array[j+1] {
                array.swapAt(j, j+1)
            }
        }
    }
}

var myArray = [10, 46, 24, 7, 8, 1, 120, 5, 15]
bubbleSort(&myArray)
print(myArray) //Output:[1, 5, 7, 8, 10, 15, 24, 46, 120]

Selection Sort

Selection Sort works by repeatedly finding the minimum element from the unsorted portion and swapping it with the first unsorted element. It has a better performance than Bubble Sort but is still not recommended for large data sets.

Selection Sort pros:

• Simplicity: The selection sort algorithm is straightforward and easy to understand, making it accessible to programmers with varying levels of experience.
• Effective for Small Datasets: it performs well with small datasets. When the number of elements is limited, the algorithm can provide acceptable sorting results.

Selection Sort cons:

• Time Complexity: Bubble sort has a time complexity of O(N²), where N is the number of elements in the array. As the data set grows, the algorithm’s performance degrades significantly, making it inefficient for large datasets.
• Inefficiency for Large Datasets: Due to its quadratic time complexity, selection sorting becomes impractical for sorting large datasets. The algorithm’s performance degrades rapidly with increasing input size.

//Selection Sort Example

func selectionSort<T: Comparable>(_ array: inout [T]) {
    let n = array.count
    for i in 0..<n {
        var minIndex = i
        for j in (i+1)..<n {
            if array[j] < array[minIndex] {
                minIndex = j
            }
        }
        array.swapAt(i, minIndex)
    }
}
var newArray = [99, 28, 2, 6, 7, 1, 11, 3, 4]
selectionSort(&newArray)
print(newArray) //Output: [1, 2, 3, 4, 6, 7, 11, 28, 99]

Merge Sort

Merge Sort is a Divide and Conquer algorithm that divides the input array into two halves, recursively sorts them, and then merges the sorted halves back together.

Merge Sort pros:

• Stability: Merge sort is a stable sorting algorithm, ensuring that the relative order of equal elements in the input array is preserved in the sorted output.
• Guaranteed Worst-Case Performance: Merge sort exhibits a worst-case time complexity of O(N logN), making it highly efficient even for large datasets. It offers consistent and predictable performance regardless of the input distribution.
• Parallelizable: Merge sort is naturally parallelizable, allowing it to take advantage of multiple processors or threads in modern multi-core systems. This feature can significantly speed up the sorting process for large datasets in parallel computing environments.

Merge Sort cons:

• Space Complexity: Merge sort requires additional memory to store the merged sub-arrays during the sorting process. This auxiliary space consumption can be a drawback when working with very large datasets.
• Not In-Place: Merge sort is not an in-place sorting algorithm, meaning it needs extra memory to store the sorted data temporarily. The lack of in-place sorting can be a disadvantage in situations where memory usage is critical.
• Not for Small Datasets: For small datasets, Merge sort may have a higher time complexity compared to certain other sorting algorithms like insertion sort. Consequently, for very small datasets, Merge sort might exhibit slightly slower performance compared to more suitable algorithms optimized for such cases.

//Merge Sort Example

func mergeSort<T: Comparable>(_ array: [T]) -> [T] {
    guard array.count > 1 else { return array }
    
    let middle = array.count / 2
    let leftArray = mergeSort(Array(array[..<middle]))
    let rightArray = mergeSort(Array(array[middle...]))
    
    return merge(leftArray, rightArray)
}

private func merge<T: Comparable>(_ leftArray: [T], _ rightArray: [T]) -> [T] {
    var mergedArray = [T]()
    var leftIndex = 0
    var rightIndex = 0
    
    while leftIndex < leftArray.count && rightIndex < rightArray.count {
        if leftArray[leftIndex] < rightArray[rightIndex] {
            mergedArray.append(leftArray[leftIndex])
            leftIndex += 1
        } else {
            mergedArray.append(rightArray[rightIndex])
            rightIndex += 1
        }
    }
    mergedArray.append(contentsOf: leftArray[leftIndex...])
    mergedArray.append(contentsOf: rightArray[rightIndex...])
    
    return mergedArray
}

let testArray = [5, 6, 17, 1, 88, 2, 21, 3, 18]
let sortedArray = mergeSort(testArray)
print(sortedArray) //Output: [1, 2, 3, 5, 6, 17, 18, 21, 88]

Quick Sort

Quick Sort is also a Divide and Conquer algorithm that selects a pivot element and partitions the other elements into two sub-arrays according to whether they are less than or greater than the pivot. It then recursively sorts the sub-arrays.

Quick Sort pros:

• Fast Average Case: Quick sort has an average time complexity of O(n log n), which is considered very efficient for large datasets.
• In-place sorting: Quick sort can be implemented to sort the elements in-place, meaning it requires no additional memory other than the array being sorted.
• Cache efficiency: The algorithm exhibits good cache locality, making it faster than other sorting algorithms when working with large arrays.
• Widely used: Quick sort is one of the most commonly used sorting algorithms due to its efficiency and simplicity.

Quick Sort cons:

• Unstable Sorting: Quick sort is an unstable sorting algorithm. This means it does not preserve the relative order of elements with equal keys.
• Worst-case time complexity: In the worst-case scenario, where the pivot choice is unfortunate, quick sort can have a time complexity of O(N²), making it less efficient than other sorting algorithms.
• Recursive implementation: Quick sort is typically implemented using recursion, which can sometimes incur a high overhead due to function call stack size.

//Quick Sort Example

extension Array where Element: Comparable {
    mutating func quickSort() {
        quickSortHelper(low: 0, high: self.count - 1)
    }
    
    private mutating func quickSortHelper(low: Int, high: Int) {
        guard low < high else { return }
        
        let pivotIndex = partition(low: low, high: high)
        quickSortHelper(low: low, high: pivotIndex - 1)
        quickSortHelper(low: pivotIndex + 1, high: high)
    }
    
    private mutating func partition(low: Int, high: Int) -> Int {
        let pivot = self[high]
        var i = low
        
        for j in low..<high {
            if self[j] <= pivot {
                self.swapAt(i, j)
                i += 1
            }
        }
        
        self.swapAt(i, high)
        return i
    }
}

var array = [9, 4, 2, 7, 5, 1, 8, 3, 6]
array.quickSort()
print(array) //Output: [1,2,3,4,5,6,7,8,9]

Conclusion

Sorting algorithms are fundamental tools in a programmer’s toolkit, and having a solid understanding of how they work is essential. Remember that each algorithm has its strengths and weaknesses, so it’s crucial to choose the appropriate one based on the specific requirements and characteristics of your data set. By mastering these sorting algorithms, you’ll be better equipped to write efficient and optimized code in your Swift projects.