Sorting Algorithms in Swift
As developers, we work with a lot of data, and I mean a lot. Whether pulling from an API or data made by local models, every single one of us has a list of data sitting around somewhere.
When working with large sets of data, it’s important to keep organized. Unless you like messy data, you will likely need some sort of sorting algorithm, but how do you pick which sorting algorithm?
In this article, we will look at a few options and see which ones are good and which ones are lame.
Different sorting algorithms
- Bubble Sort
- Insertion Sort
- Selection Sort
- Merge Sort
- Quick Sort
Bubble Sort
One of the first algorithms you’ll learn is the Bubble Sort Algorithm. It’s simple and easy to learn.
Bubble Sort basically works by looking at the first pair in a list and compare them. If they are sorted, move on to the next pair. If they are not sorted, swap them and continue to the next pair. This will continue until the entire list is sorted.
There’s just one problem with this sorting algorithm … it stinks. Bubble Sort has a Big-O Notation of O(n²). While fine with small data sets, this is far less than ideal, especially if you’re working with large data sets.
While not the best sorting algorithm out there, still worth knowing. Here's what the code for that will look like.
var myArray = [4, 7, 2, 9, 10, 5]
myArray.bubbleSort()
> [2, 4, 5, 7, 9, 10]extension Array where Element: Comparable {
func bubbleSort() -> Array<Element> {
var data: Array<Element> = self for i in 0..<data.count {
for j in 0..<data.count-1 {
if dada[j] > data[j+1] {
data.swatAt(j, j+1)
}
}
}
return data
}
}
This code is very simple
Insertion Sort
After learning about Bubble Sort, it’s time to quickly look for a better sorting algorithm. Let’s think about how people usually sort items. We take our first item and count it as sorted. Then we take the next item and compare it to the items before it, inserting it where it belongs. Repeat until the entire list is sorted. Here’s a quick video explaining it.
Already, we can see that this is a much cleaner and more human-friendly way of sorting a list. This is probably how you have always done it. This method just seems obvious.
As nice and neat as this sorting algorithm is, it still isn’t quite the best. On average, this method has a time complexity of O(n²) (same Big-O Notation as Bubble Sort, but typically a little faster).
Maybe not the best algorithm for massive data sets, but still a good one to have under your belt. Here’s a code sample:
var myArray = [4, 7, 2, 9, 10, 5]
myArray.insertionSort()
> [2, 4, 5, 7, 9, 10]extension Array where Element: Comparable {
func insertionSort() -> Array<Element> {
var data: Array<Element> = self
for i in 1..<data.count {
let value = data[i]
var position = i while position > 0 && data[position-1] > value {
data[position] = data[position-1]
position -= 1
} data[position] = value
}
return data
}
}
Selection Sort
This is another common way of sorting data. This one is very similar to the Insertion Sort algorithm and the logic comes naturally to many.
Selection Sort works by selecting the smallest item from the unsorted array and sorts it. To do this, we need to keep track of two things: the current index and the current minimum. Here’s a video that explains it.
Yet another stair forward sorting algorithm.
Unfortunately, while definitely a nicer algorithm, it still has a Big-O Notation of O(n²). A great algorithm to know and easy one to understand, it can still be slow when working with large data sets.
Here’s a code sample:
var myArray = [4, 7, 2, 9, 10, 5]
myArray.selectionSort()
> [2, 4, 5, 7, 9, 10]extension Array where Element: Comparable {
func selectionSort() -> Array<Element> {
var data: Array<Element> = self for i in 0 ..< data.count {
var min = i
for currentIndex in i + 1 ..< data.count {
if data[currentIndex] < data[min] {
min = currentIndex
}
} if i != min {
data.swapAt(i, min)
}
} return data
}
}
Merge Sort
As you continue on your quest to encounter more optimum sorting algorithms, you will eventually find yourself looking at a Merge Sort. This method of sorting a set of data is most definitely a more complex way compared to the previously listed algorithms, but as you take a closer look, you begin to see why this algorithm shines.
One thing that sets Merge Sort apart from the other algorithms shown previously is its “divide and conquer” methodology. Rather than going through the list of data iteratively, we do so recursively. Basically what that means is we divide the problem into smaller (similar) components by calling itself.
In the case of Merge Sort, we split the list in two, then those segmented lists get split in two again, and so on until we reach a base case(this lets the function know when to stop breaking up the problem). Once this is complete, each sub-list is sorted.
Another excellent advantage of Merge Sort is its time complexity, which has a worst-case scenario of O(nlogn), much better than O(n²).
Here’s a code sample:
var myArray = [4, 7, 2, 9, 10, 5]
myArray.mergeSort()
> [2, 4, 5, 7, 9, 10]extension Array where Element: Comparable { func mergeSort() -> Array<Element> {
let result = mergeSort(self)
return result
} private func mergeSort(_ data: Array<Element>) -> Array<Element> {
if data.count < 2 { return data } let midpoint = Int(data.count / 2)
var arrayOne = Array(data[..<midpoint])
var arrayTwo = Array(data[midpoint..<data.count]) arrayOne = mergeSort(arrayOne)
arrayTwo = mergeSort(arrayTwo) return merge(arrayOne, arrayTwo)
} private func merge(_ arr1: ArrayElement>,
_ arr2: Array<Element>) -> Array<Element> {
var output = Array<Element>()
var left = arr1
var right = arr2 while left.count > 0 && right.count > 0 {
if left[0] > right[0] {
output.append(right[0])
right.removeFirst()
} else {
output.append(left[0])
left.removeFirst()
}
} // at this point either left or right is empty
output.append(contentsOf: left)
output.append(contentsOf: right) return output
}
}
As you can see, this sorting algorithm isn’t written in just one function but two. The first, mergeSort(), is responsible for separating a list of data into two segments. The second, merge(), is responsible for properly sorting and merging the two.
Quick Sort
Quick Sort is another divide and conquer, recursive method. Just like Merge Sort, it segments a given list into smaller lists.
Awesome, another super fast method! Not so fast. Yes, Quick sort is very quick, with an average time complexity of O(n log n), it has a worst-case of O(n²), a similar performance to Bubble, Insertion, and Selection Sort.
Then why use Quick Sort?
Yes, it’s true, Quick Sort can be as slow as Bubble Sort, but it’s important to realize that that’s the worst-case scenario. On average, it performs a lot more like Merge Sort. However, one advantage Quick Sort has over Merge sort is space complexity.
Merge Sort has a space complexity of O(n) for all cases. Quick Sort has a worst-case space complexity of O(n) but an average-case space complexity of O(log n).
Here’s a code snippet. It looks a little different from the pseudo-code provided in the video, but that’s mainly due to the use of the swift built-in method .filter to separate the greater and lesser values for us. This change was made to enhance readability and ease of understanding (but also slightly slows the operation)
var myArray = [4, 7, 2, 9, 10, 5]
myArray.quickSort()
> [2, 4, 5, 7, 9, 10]extension Array where Element: Comparable { func quickSort() -> Array<Element> {
let result = quickSort(self)
return result
} private func quickSort(_ data: Array<Element>) -> Array<Element> {
if data.count < 2 { return data } let pivot = data[data.count/2] let less = data.filter { $0 < pivot }
let equal = data.filter { $0 == pivot }
let greater = data.filter { $0 > pivot } return quickSort(less) + equal + quickSort(greater)
}
}
This implementation, while still operating as a Quick Sort, isn’t the most optimum way to write it. Here’s a more efficient way:
var myArray = [4, 7, 2, 9, 10, 5]
myArray.quickSort()
> [2, 4, 5, 7, 9, 10]extension Array where Element: Comparable {
func quickSort() -> Array <Element> {
var data = self
quickSort(&data, low: 0, high: data.count-1)
return data
} private func quickSort(_ data: inout Array<Element>, low: Int, high: Int) {
if low < high {
let p = partition(&data, low: low, high: high)
quickSort(&data, low: low, high: p-1)
quickSort(&data, low: p+1, high: high)
}
} private func partition(_ data: inout Array<Element>, low: Int, high: Int) -> Int {
let pivot = data[high]
var leftWall = low for i in low..<high {
if data[i] < pivot {
data.swapAt(leftWall, i)
leftWall += 1
}
}
data.swapAt(leftWall, high)
return leftWall
}
}
Resources:
- https://droxey.com/docs/#/compsci/algorithms/intro-algorithms?id=introduction-to-algorithms
- https://medium.com/@EnnioMa/back-to-the-fundamentals-sorting-algorithms-in-swift-from-scratch-fccf8a3daea3
- Algorithms: Bubble Sort — HackerRank Youtube
- Bubble Sort in 2 minutes — Michael Sambol Youtube
- Insertion Sort in 2 minutes — Michael Sambol Youtube
- https://learnappmaking.com/insertion-sort-swift-how-to/
- Selection Sort in 3 minutes — Michael Sambol Youtube
- https://github.com/raywenderlich/swift-algorithm-club/tree/master/Selection%20Sort
- Merge Sort in 3 minutes — Michael Sambol Youtube
- Quick Sort in 4 minutes — Michael Sambol Youtube
- https://github.com/raywenderlich/swift-algorithm-club/blob/master/Quicksort/Quicksort.swift
