Recursive Quick Sort in Python

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[0]:
            lesser.append(i)
        else:
            greater.append(i)
    return quicksort(lesser)+q[0:1]+quicksort(greater)

Here is the benchmarking result that I've obtained: