Sorting

Sorting is an essential task when managing data. As we saw with Big O Notation, sorted data allows us to implement efficient algorithms. Our goal with sorting is to move from disarray to order. This is done by arranging data in a logical sequence so we’ll know where to find information. Sequences can be easily implemented with integers, but can also be achieved with characters (e.g., alphabets), and other sets like binary and hexadecimal numbers. To start, we'll use various techniques to sort the following array:

//a simple array of unsorted integers
var numberList : Array<Int> = [8, 2, 10, 9, 11, 1, 7, 3, 4]

With a small list, it's easy to visualize the problem and how things should be organized. To arrange our set into an ordered sequence, we can implement an invariant). In computer science, invariants represent assumptions that remain unchanged throughout execution. To see how this works, consider the algorithm, insertion sort.

Insertion Sort

One of the more basic algorithms in computer science, insertion sort works by evaluating a constant set of numbers with a secondary set of changing numbers. The outer loop acts as the invariant, assuring all array values are checked. The inner loop acts as an secondary engine, reviewing which numbers get compared. Completed enough times, this process eventually sorts all items in the list.

//insertion sort - rank items by comparing each key in the list.
func insertionSort() {
    var x, y, key : Int
    for (x = 0; x < numberList.count; x++) {
        //obtain a key to be evaluated
        key = numberList[x]

        //iterate backwards through the sorted portion
        for (y = x; y > -1; y--) {
            if (key < numberList[y]) {
                //remove item from original position
                numberList.removeAtIndex(y + 1)

                //insert the number at the key position
                numberList.insert(key, atIndex: y)
            }
        } //end for
    } //end for
} //end function

Bubble Sort

Another common sorting technique is the bubble sort. Like insertion sort, this algorithm combines a series of steps with an invariant. The function works by evaluating pairs of values. Once compared, the position of the largest value is swapped with the smaller value. Completed enough times, this "bubbling" effect eventually sorts all items in the list.

/* bubble sort algorithm - rank items from the lowest to highest by swapping groups of two items from left to right. */
func bubbleSort() {
    var x, y, z, passes, key : Int
    //track collection iterations
    for x in 0..<numberList.count {
        passes = (numberList.count - 1) - x;

        //use shorthand "half-open" range operator
        for y in 0..<passes {
            key = numberList[y]

            //compare and rank values
            if (key > numberList[y + 1]) {
                z = numberList[y + 1]
                numberList[y + 1] = key
                numberList[y] = z
            }
        } //end for
    } //end for
} //end function

Efficiency

Besides insertion sort and bubble sort, there are many other sorting algorithms. Popular techniques include quicksort, mergesort and selection sort. Because both insertion and bubble sort algorithms combine a variant and invariant, their average performance is n x n or O(n²). Other techniques (like mergesort) apply different methods and can improve average performance to O(n log n).