

In [1]:

    
%load_ext watermark
%watermark -a 'Sebastian Raschka' -u -d -v









    



Sebastian Raschka 
last updated: 2017-08-04 

CPython 3.6.1
IPython 6.1.0

QuickSort

Quicksort is one of the fastest sorting algorithms with a time complexity of O(n log n) on average. Quicksort is also a typical example of a Divide & Conquer algorithm that can be implemented using recursion. Quicksort works as follows:

First, we define a base case. Here, our base case is an array of one or zero elements. In other words, if a given array reached the size < 2, we return it. Now, given an array, we pick a value and assign it as the so-called pivot. Then, we look at all the remaining elements in an array and divide them into 2 new arrays:

an array with values smaller than or equal to the pivot
an array with values greater than the pivot

Then, in recursive fashion, we apply the quicksort algorithm to those 2 subarrays. This procedure is repeated until it hits the base case, so that the function will return a sorted array from the call stack.

Below is a simple implementation in Python:



In [2]:

    
def quicksort(ary):
    if len(ary) < 2:
        return ary
    else:
        pivot = ary[0]
        smaller, bigger = [], []
        for ele in ary[1:]:
            if ele <= pivot:
                smaller.append(ele)
            else:
                bigger.append(ele)
        return quicksort(smaller) + [pivot] + quicksort(bigger)



In [3]:

    
quicksort([])









    Out[3]:





[]



In [4]:

    
quicksort([1])









    Out[4]:





[1]



In [5]:

    
quicksort([12, 5, 1, 2])









    Out[5]:





[1, 2, 5, 12]

Note that the performance of quicksort is only O(n log n) if the values in the array occur in completely random order. If an array is already sorted, quicksort has time complexity O(n^2) if we would always pick the first value of the array as the pivot like in the implementation above. Why? Because, depending on whether the array is sorted in ascending or descending order, the left or the right subarray in the recursive function will always be empty. Thus, if we have n elements in an array, our call stack will have a depth of n, thus O(n*n) = O(n^2). However, if we always divide the array in half, the call stack will only have depth log n, thus O(n log n).

If we know that our arrays are not always in random order, it is recommended to implement quicksort so that it picks a random element as the pivot and not always strictly the first number in that array.



In [ ]: