Swift Sorts I
Before we can understand which sort is the fastest, we need to cover and really learn the basics. These sorts are worth memorizing in Swift. I want to be able to write them quickly from rote memory.
To use the system’s sorting method, you really need to understand how it works. And to understand this, you really need to understand all the basic sorting methods. Swift, for example, uses an algorithm called Introsort, which itself uses a combination of Quicksort, Heapsort and Insertion sort.
Insertion sort is used if the number of elements to be sorted is fewer than 20.
But to really understand Insertion sort we need to understand Simple sort and Selection sort. So let’s start with those two, and do it all in Swift from here on out.
Simple sort is probably the way you would intuitively sort a pack of cards. Imagine that the different suits — hearts, diamonds, clubs and spades — are to be in that order. And ace is low.
You scan through the deck of cards and find the lowest one, the ace of hearts, and place that on the table face up. Then you look for the two of hearts in the remaining cards and place that on top of the ace. Then you look for the three of hearts and place that on top of the two. And continue. Always searching through the remaining cards for the next lowest card.
In Swift, if we were sorting an array of Double instead of cards, we could write this as:
public func simpleSort(a: [Double]) -> [Double] {
var b = a
var c = [Double]()
var counter = b.count
for _ in 0..<counter {
var min = 0
for j in 0..<counter {
if b[j] < b[min] {
min = j
}
}
c.append(b[min])
b.remove(at: min)
counter -= 1
}
return c
}
But simple sort is never used. Even for basic sorts. For several reasons, including that as written it is just slow. And has at least one other major mistake. But presenting it here makes it a little bit easier to explain Selection Sort.
Selection Sort is an improvement. Though even that is not often used. We’ll consider it here, so that we can say we have a comprehensive knowledge of sorting. And also because this is our first sort using exchanges. The principle — explained with playing cards — is this: Take the top card in the deck and exchange it with the lowest card in the unsorted remainder of the deck. So if the top card is 7 of spades, exchange it with the ace of hearts. Then repeat with the second card: Exchange it with the two of hearts. And so on, until the deck is sorted. In code, the top card is always represented with the index i. As sorting proceeds, everything lower than i is sorted. Everything at i and higher is still to be sorted. It is not complicated to visualize and not complicated to code. We make it even simpler by factoring out the exchange method.
In Swift you can see the outer loop goes through all the cards; The inner loop goes through all the unsorted cards to find the next lowest card. Then they are exchanged.
Also note that it’s valuable to factor out the exchange func:
public func selectionSort(a: [Double]) -> [Double] {
var b = a
for i in 0..<a.count {
var min = i
for j in (i+1)..<b.count {
if b[j] < b[min] {
min = j
}
}
b = exchange(a: b, i: i, j: min)
}
return b
}
public func exchange(a: [Double], i: Int, j: Int) -> [Double] {
var b = a
let temp = b[i]
b[i] = b[j]
b[j] = temp
return b
}
These are simple functions and easy to practice and memorize. Next time we’ll continue with slightly better sorting.