Recursive Quick Sort in PythonFri 23 March 2007 by Thejaswi Puthraya
Recursive Quick Sort Algorithm in Python
Well it has been a long time since I blogged about algorithms (my last post on alogrithms here). As promised I am back with the quicksort algorithm. The quicksort alogrithm that I've written is recursive in nature against the iterative implementation.
Though the iterative implementation is efficient because there is a lower memory overhead as compared to its recursive implelementation, it is very complex to code (though not impossible).
The recursive alogorithm on the other hand consumes a lot of stack space and has a considerable overhead for the subsequent recursive calls. I would recommend Wikipedia as a great resource on algorithms. You can check out this link to know more about algorithms.
Here is the code I've written:
q= def quicksort(q): lesser= greater= if len(q) <= 1: return q for i in q[1:]: if i < q: lesser.append(i) else: greater.append(i) return quicksort(lesser)+q[0:1]+quicksort(greater)
Here is the benchmarking result that I've obtained:
Results of Quicksort
|Number of Elements|
Compare with Bubble Sort and Straight Insertion Sort benchmark results.
The mere fact that the quicksort algorithm executes in micro seconds shows its speed. Thanks to C.A.R.Hoare for developing such a fast algorithm.