A Matter of Sorts

So, in a previous post — in fact, it was my last one where I pontificated on Tech Interviews — I said I’d discuss the very popular sorting algorithm. Namely, two very efficient and common ones. Merge Sort and Quick Sort.

I am going to break these down as best I can, in a way that anyone, even people who have never coded before can understand.

So, let’s start off with the question I am sure might be asked. What is a sort? Well, it’s a way of organizing data in an ascending or descending order (generally, it’s ascending, but there are times when going highest to lowest is important).

I will also be using a term here a lot, called an array. This is a fundamental data structure in computer science, in which data is stored. Think of it is either as a sorted or unsorted deck of cards. An unsorted deck of cards might appear to have a random placement of suits and numbers, while a sorted deck will go from Ace to King, Clubs, Ace to King, Diamonds, Ace to King, Hearts, Ace to King, Spades.

Yes, I know Aces are stronger than Kings in most games, but I’m using it here as a placeholder for 0 or 1 depending on your fancy. There is no official suit strength in cards except for specific games and I organized them alphabetically. The array is used in almost every computer programming application when data needs to be organized*. When you organize your books on a shelf or put your clothing in a certain order or walk up and down the aisles of a grocery store, almost everything is sorted in an array like fashion.

We use sorting algorithms in our daily lives without even knowing it. When we organize anything, we’re using a sorting algorithm, which makes their sister algorithms, the search algorithm, much easier to implement in the future.

I actually found myself using a sorting algorithm — albeit a very primitive and subjective one — when I was organizing my closet the other day. My dear wife is always on me to keep my clothes organized and in some semblance of order, so I originally had sections — suits, dress coats, general coats, dress shirts, t-shirts, polo shirts, button down shirts, sweaters, sweatshirts, and finally slacks. Most of my pants (trousers for our friends in the UK and Commonwealth), however, are kept in my dresser. I sorted that as well. It is a bit less organized than my closet, but that’s beside the point.

Let’s use this example of a sort — in fact, I subconsciously used a form of a quicksort to organize my clothes in each of their categories by color or pattern. Lighter clothing is basically the lesser valued (0, this is completely flipped from how its done on computers, but bear with me) on the left to darker colors and blacks on the right.  In fact, it is a modification of the quick sort algorithm due to the fact it is based on hue, more than the highest index value. My pivot is in the middle, rather than the end of the ‘array’ of clothing.

Here is the pseudocode for this sort:

The Nerdographers's clothingSort(clothing set, lighter, darker)
    if(lighter than darker):
        if(clothing color is solid): 
          partition clothing by color / hue  // it should be noted middle red is my 50/50, 
                                             // cooler colors generally end up considered darker
          partition(clothing, lightest color, darkest color)
        if(clothing "color" is patterend): 
          examine prominent/primary color, organize by equivalent solid
          partition(clothing, lightest color, darkest color)       
     clothingSort(clothing set, light, partition)
     clothingSort(clothing set, partition + 1 shade darker, darker)

The Partition(clothing set, lightest, darkest):
    middle hue = average of lightest and darkest / warmest to coolest
    pivot := clothing set's middle hue
    tracker := lightest, one shade lighter

    while lightest <= darkest: 
        if clothing_set[lightest] <= pivot
            tracker + 1
            switch the hues appropriately (darkest to lightest)
    switch one hue darker with the middle hue, continue process
     until completed.

Compare this to the true quicksort:

/* low --> starting index, high --> ending index */
quickSort(array, low, high):
    if(low < high): 
        partition := (low + high) / 2
        // low and high will shift based on the portion 
        // of the array you are working on.
    quicksort(array, low, partition)
    quicksort(array, partitition + 1, high)

partition algorithm (array, low, high): 
    pivot := highest value of the array
    tracker := lowest value - 1 // this is important, as the highest and lowest values change.

    indexer := lowest
    while indexer <= highest value less 1
        indexer + 1
        switch the data at the indexer tracker indices of the array
     
     switch the data at the tracker and highest value of the array
     set the partition index to the tracker + 1

The quicksort is fundamentally a Divide and Conquer algorithm. It breaks down various parts of the data set, in this case, the array into smaller, more manageable portions and exchanges data placements if they are in the improper value order. Unlike its cousin algorithm, mergesort, quicksort does not necessarily break down the array into component pieces. It does everything in place — meaning no new arrays or any extra space is taken up in the computer’s memory, everything that is changed is based on what exists already.

Imagine you are sorting coins by their value. You don’t break them into separate groups, whether by value or because you want smaller manageable groups to work with, you simply move them around based on what their value is relative to their neighbors.  Eventually, you’ll get the right order of coins. Sometimes you will have multiple coins of the same value, sometimes you will sets of coins that all have a separate and discrete value. All the coins will end up in their proper order, regardless.

The critical piece of it is the partitioning behavior.  One thing to keep in mind, that quicksorts consider the value of its pivot, which is declared in the partition, generally based on the highest value given at the time, and use that to sort, rather than going left to right or right to left.

MergeSort:

MergeSort is actually a bit more complex but ultimately just another divide and conquer algorithm. It compares from left to right, rather than highest to lowest internally.

MergeSort(array, left, right):
    middle = (right + left) / 2
    mergeSort(array, left, middle)
    mergeSort(array, middle + 1, right)
    merge(array, left, middle, right)

merge(array, left, middle, right):
    i, j, k // these are tracker variables.
    n1 := middle - left + 1;
    n2 := right - middle;

    Left[N1], Right[N2] // new sub arrays with size equivalent. They may or may not be 
                        // totally equal depending on the size of the initial array.
    while i < size of Left(n1), place next element index into current slot.
    while i < size of Right(n2), place index of m + 1 + j into current slot.

As stated before, these are divide and conquer algorithms. These are especially popular in classical computing because it breaks down data into roughly equal halves and it is much easier for the computer to handle as computers think in a language of ones and zeroes called binary.  3-way, 4-way, even 10-way sorting algorithms exist out there but they are not sufficiently or substantially more efficient as than two-way sorting arrays, therefore are not explored as much more than curiosities and toy problems.

Mergesort breaks down large data sets into smaller composite arrays to increase the speed of the sort. Returning to the coin analogy,  first, you separate coins out into smaller discrete groups, let’s say in this case 4, and you organize them by size. Then you merge two coin groups into one another, and within that group, you sort them again, this should be easier because at least one large coin will be at the end of the sub-array. Keep sorting and merging until everything is in its proper order.

Special Guest – Bubble Sort!

Bubble sort is an often maligned and inefficient algorithm. It is actually quite effective for small data sets (I’d say, 20 or less on modern machines) where the performance of sorts like Quick and Merge might either be overkill or actually less efficient. Bubble sort is something of a walking joke and seen as the ‘young programmer’s first sort’ — and it’s a bad rap to have, but it is a naive solution to a very complicated problem set and it does have its uses.

A bubble sort generally looks like this:

bubbleSort(array, size):

i, j <- 0; // declaring i and j's index starting point

while i < size - 1:
   while j < size - i - 1:
   if array at j is larger than array at j + 1
       switch array at j with array at j + 1

It does not divide and conquer, it simply goes over everything in the array,

You know what would be fun? Maybe I will go and create a kind of anti-sort… a chaos sort, that will take a sorted array and jumble it up. Might be a fun exercise. I’ll try creating this and post it for my next computer science related post, time permitting.

 

*This is actually not always true, there is something called a linked list which often fulfills a similar purpose or an associate array (also frequently called the hash map) that is beyond the scope of this post. Arrays are best for smaller data sets, where time is not of paramount concern.