Quicksort

I always find certain algorithms extremely simple yet sophisticated.  And I would have to say that Quicksort is one of those algorithms.  I was working on a bit of JavaScript for my web development and I kind of ended up on a tangent that had me wanting to be able to search through a bunch of numbers to see if it is included in the data.  So I figured I would use Binary Search to find it, but then I remembered that I would need sorted data for that to work.  Because I knew I wasn’t going to get pre-sorted data I would have to take the information as an array and sort it on my own.

Anyone who has studied algorithms knows that the other options that come to mind are usually selection sort, insertion sort, bubble sort and mergesort (from a basic algorithms class.)  The first three all share the same worst case performance of O(n²) and both insertion and bubble have a best case performance of O(n).  Merge sort and Quicksort are both O(n log n) in the average case, and I wasn’t to worried about a stable sort so I went with Quicksort.  I looked it up online to make sure that I still remembered the concept, but I have never written a Quicksort algorithm.  I will first post some pseudo code for a Quicksort and then I will talk about it and follow it up with my JavaScript implementation of the algorithm!  Lets get started:

 

Pseudo Code

function quicksort (Array A)

    if length of A <= 1:

        return A

    get pivot value.

    remove pivot value from array.

    create empty arrays less and greater.

    for x in length A:

        if x <= pivot:

            append x to less
 
       else:

            append x to greater

    return concatenation(quicksort(less), pivot, quicksort(greater))

The Explination

The idea is that you take the unsorted array (or list) and pick a random index to use as the pivot value.  Then once you get the pivot value, you remove that value from the array so you don’t compare the value to itself.  Then for all other values in the array you compare them to the pivot value.  If the value in the array is less than or equal to the pivot value it is to be stored into the new array called less.  Otherwise, it is stored into the new array called greater.  Pretty straight forward.  The interesting bit comes in with the use of recursion.  The return calls the quicksort function, this time on each separate array.  It concatenates the answer to have the new sorted less array, followed by the pivot value (which is now in its final spot), and then the sorted greater array.

Pretty cool right?  This is called a Divide and Conquer algorithm because it is splitting the data that needs to be sorted into smaller and smaller subgroups until the problem is solved! This can be adapted for any language you are working with, and as promised here is my code that I wrote using JavaScript to implement this algorithm.

 

The JavaScript

//The quicksort function that allows the binary search to work properly.
function quicksort(numData)
{
    //returns the array if only one element or none at all
    if(numData.length <= 1)
        return numData;

    //creating the two new empty arrays and an index var
    var less = new Array();
    var greater = new Array();
    var i;

    //picking a random pivot point
    var pivotIndex = Math.floor(Math.random() * numData.length);
    var pivotValue = numData[pivotIndex];

    //remove the pivotValue from the array
    numData.splice(pivotIndex, 1);

    //now for the rest of the array, put the data in the correct subarray
    for (i = 0; i < numData.length; i++)
    {
        if (numData[i] <= pivotValue)
            less.push(numData[i]);
       else
            greater.push(numData[i]);
    }

    //recursivly calls quicksort as well as concatenates the answers
    return quicksort(less).concat(pivotValue,quicksort(greater));

}

Conclusion

I hope that this helped you understand a little bit more about the Quicksort algorithm, and hopefully you can now implement this as well for any of your sorting needs!  If you have any questions, or need some clarification, let me know!