Quicksort, aka partition-exchange sort, is a divide and conquer algorithm. It’s an efficient algorithm that takes O(nlogn) time to sort n items (on average). In the worst case, it might take O(n2) time.
Quicksort first divides a large list/array into two smaller sub-arrays using a pivot value – one with elements smaller than the pivot element and other with elements larger than the pivot element. Unlike merge sort, it doesn’t wait for the list size to be 1 before starting the sorting process. Sorting is done during partition that makes the combining of the sub-lists easier.
The steps are:
1. Pick an element, called a pivot, from the list/array.
2. Reorder the list/array so that all elements smaller than the pivot element come before the pivot, while all elements greater than the pivot element come after it (equal values can go either way. In my implementation, I have kept the pivot element on the lower side).
3. The above process is applied recursively with a list of size zero or one as the base case.
The python code for the quicksort is as follows…
def quicksort(a,low,high): if (low < high): p = partition(a,low,high) # get pivot quicksort(a,low,p) # apply quick sort on smaller elements quicksort(a,p+1,high) # apply quick sort on larger elements return a def partition(a,lo,hi): pivot = a[hi-1] i = lo for j in xrange(lo, hi-1): if (a[j] <= pivot): x = a[i] a[i] = a[j] a[j] =x i = i+1 y = a[i] a[i] = pivot a[hi-1] = y return i l = [13,18,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1] final = quicksort(l,0,len(l)) print "sorted list is ", final
The output of the above code looks like this..
sorted list is [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 13, 14, 15, 16, 18]