Getting Started with Sorting Algorithms in Swift

As any computer scientist would tell you, algorithm is king, and whether you are going for a Google interview, or looking to work on a project that optimizes large data, algorithms are the key differentiators that separate mediocracy from greatness.

So, ive decided to write a new article on algorithms, firstly as a refresher for my mind, secondly to apply the knowledge with Swift, and thirdly, to promote an excellent book, from which the code comes from, Swift Algorithms & Data Structures, by Wayne Bishop, whom I highly regard, of course.

So the first concept you learn when you pick up an algorithm book is, Big O Notation. Its a standard that is used to measure and compare algorithm techniques, which start all the way from linear to logarithmic comparisons.

In the textbook Swift Algorithms & Data Structures, the author starts off by running through a linear time technique, a simple loop through an array:

func linearSearch(key: Int) {
    //check all possible values
    for number in numberlist {
            if number == key {
                println(“value at \(key) found..”)    
                break
            }

    }

}

As the speed is dependent on input size, the algorithm is less efficient as input size (n) grows, and is therefore considered to be O(n).

Binary search has the advantage of reducing search criteria based on the fact the array is already sorted:

func binarySearch(key: Int, imin: Int, imax: Int) {

    var midIndex : Double = round(Double((imin + imax) / 2))
    var midNumber = numberList[Int(midIndex)]

    //reduce the range
    if    midNumber > key

    {
        binarySearch(key, imin, Int(midIndex) - 1)

        //increase the range

        else if (midNumber < key ) {

        binarySearch(key, Int(midIndex) + 1, imax)

    }

    else {
        println(“value \(key) found..”)

    }

}

As the array is sorted, we can more easily work out whether to search before or after the pointer at each turn, so the performance of this is said to be logarithmic, represented as O(log n). That is, complexity is minimized when size of input grows.

Big O Complexity Graph

OK, so a brief introduction of the Big-O, we take a look at sorting next, and sorting arrays makes it easier for algorithms to search more efficiently.

Sorting

To illustrate visually the different types of sorts, I would recommend this awesome animation site, VisualGo, which explains each of the types step-by-step, supplemented with pseudocode and annotations.

image

Insertion Sort
The first sort we will look at is Insertion Sort:

  • Evaluates a constant set of numbers with a secondary set of changing numbers.
  • Outer loop is invariant, assures all values are checked.
  • Inner loop secondary engine reviewing what numbers get compared.

Sorting is typically done in-place, by iterating up the array, growing the sorted list behind it. At each array-position, it checks the value there against the largest value in the sorted list (which happens to be next to it, in the previous array-position checked). If larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted list, shifts all the larger values up to make a space, and inserts into that correct position. (source: wikipedia)

File:Insertion-sort-example-300px.gif

Swift Code
var arrayOfNumbers = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]

func sortInsertion<T:Comparable>( inout array:Array<T>) -> Array<T>{

    var key: T

    for x in 0..<array.count{
        //mark first element as sorted
        key = array[x]

        //iterate backwards through the sorted portion
        for y in x.stride(to: 0, by: -1){
            if (key < array[y]){
                //remove from original position and add to new position
                swap(&array[y+1], &array[y])
            }
        }

    }
    return array
}

print(sortInsertion(&arrayOfNumbers))

Note, I created this function as a generic, so that you can pluck in letters as well.

Explanation
Go to VisualGo and check out insertion sort.

Bubble Sort
Next we look at is the Insertion Sort:

  • Evaluates a constant set of numbers with a secondary set of changing numbers.
  • Outer loop is invariant, assures all values are checked.
  • Inner loop secondary engine reviewing what numbers get compared.

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller elements "bubble" to the top of the list. Although the algorithm is simple, it is too slow and impractical for most problems even when compared to insertion sort. It can be practical if the input is usually in sort order but may occasionally have some out-of-order elements nearly in position.. (source: wikipedia)

File:Insertion-sort-example-300px.gif

Swift Code
func sortBubble( inout array:Array) -> Array{

var passes: Int
    var key: T

    //The invariant
    for x in 0..<array.count{
        passes = (array.count-1) - x //inclusive of current position

        for y in 0..<passes{
            key = array[y]

            //compare and re-pos values
            guard key < array[y+1] else{
                swap(&array[y+1], &array[y])
                break
            }
        }

    }
    return array
}

Explanation
Go to VisualGo and check out insertion sort.

Conclusion

So I've shown you two quick examples on sorting in Swift, thanks to the amazing book that I consult, Swift Algorithms & Data Structures. In the next article, I will go through working with Linked Lists.