Sorting Algorithms: Implementing Selection Sort Using Swift
In the previous article, we dove into Insertion Sort and got a feel for how it operated and what its pros and cons were. Today we’re looking at how Selection Sort operates, and how we can implement it using Swift.
XCode Playground Files with implementations are available on this link.
What Is Selection Sort?
Selection Sort, much like Bubble Sort, is an algorithm that many of us may have implemented before, without even knowing it. The idea is simple:
- Find the smallest element in the entire array and swap it into the first place.
- Find the second smallest element and swap it into second place.
- Keep going like this until you’ve swapped all elements into place.
Take a look at the sketch below to get a visual feel ( the “?” marks the index that is currently being sorted, the arrow marks the spot where we’ve located the smallest available element):
How Does It Perform?
Selection Sort is an easy-to-understand algorithm. For every spot in our array, we search the entire domain and look for the smallest element. When we’ve found it, we repeat the process for every other index.
This leaves us with a run time complexity of O(n²). Unfortunately, there are no more optimizations to be done for this, so this is both the best and worst case complexity.
Selection Sort does however happen in-place, giving it a space complexity of O(1). It also performs relatively few swaps, and has pretty much no overhead costs related to getting started. While this is not an algorithm that you would use for large data sets, it’s still perfectly viable for smaller ones (say less than 100–150 elements). Since the faster algorithms (say Merge Sort) take a bit of time to set up all they need to perform the sort, the actual processing time may not differ that much for such small sets.
Let’s Dig Into The Code
Take a look at the following piece of code:
extension Array where Element: Comparable {
public mutating func selectionSort() {
for iterationIndex in 0 ..< self.count - 1 {
var minIndex = iterationIndex
for compareIndex in iterationIndex + 1 ..< self.count {
if self[compareIndex] < self[minIndex] {
minIndex = compareIndex
}
}
swapAt(iterationIndex, minIndex)
}
}
}Let’s walk through what happens here.
We start off by creating a loop that will use iterationIndex to keep track of the index in our array that we are currently sorting. We then create a minIndex variable to keep track of the index of the smallest, currently known element. Note that we initialize minIndex to the same value as iterationIndex, making the assumption that the current element is the smallest until we’ve been proven wrong.
We then start another loop, using compareIndex to walk our way up the array.
We compare each element to the one that is currently known to be the smallest. If the element at compareIndex is smaller, we set minIndex = compareIndex.
At the end of each iteration, after we’ve looked through the entire array, we finish up by swapping the element at iterationIndex for the element at minIndex, and we’re done!
That’s it for this time! Feel free to comment if you have questions, and follow to get notifications about future articles.
To learn more about iOS Development, check out my previous articles:
Follow us on social media platforms:
Facebook: facebook.com/AppCodamobile/
Twitter: twitter.com/AppCodaMobile
Instagram: instagram.com/AppCodadotcom
