Recursive Quick Sort in Python

Fri 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:


def quicksort(q):
    if len(q) <= 1:
        return q
    for i in q[1:]:
        if i < q[0]:
    return quicksort(lesser)+q[0:1]+quicksort(greater)

Here is the benchmarking result that I've obtained:

Results of Quicksort

  Number of Elements
in seconds 10 50 100 200 500 1000 5000
Quicksort 0.086 0.373 0.781 2.196 5.393 9.855 95.567

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.