Python Quicksort - List Comprehension Vs Recursion (partition Routine)

I watched the talk Three Beautiful Quicksorts and was messing around with quicksort. My implementation in python was very similar to c (select pivot, partition around it and recurs

Solution 1:

1. Why is list comprehension so much faster?

   Because list comprehension implies C loop which is much faster than slow general way of using Python's for block.

2. Some enlightenment on the limit on recursion in python. I first set it to 100000 in what cases should I be careful?

   In case you run out of memory.

3. Trying to sort 1000000 elements hogged memory of my laptop (with the recursion method). What should I do if I want to sort so many elements? What kind of optimizations are possible?

   Python's recursion gives such an overhead because every function call allocates a lot of stack memory space on each call.

   In general, iteration is the answer (will give better performance in statistically 99% of use cases).

   Talking about memory structures, if you have simple data structures, like chars, integers, floats: use built-in array.array which is much more memory efficient than a list.

Solution 2:

Have you tried writing a non-recursive implementation of partition? I suspect that the performance difference is purely the partition implementation. You are recursing for each element in your implementation.

Update

Here's a quick implementation. It is still not super fast or even efficient, but it is much better than your original recursive one.

>>>defpartition(data):... pivot = data[0]... less, equal, greater = [], [], []...for elm in data:...if elm < pivot:...   less.append(elm)...elif elm > pivot:...   greater.append(elm)...else:...   equal.append(elm)...return less, equal, greater...>>>defqsort2(data):...if data:...  less, equal, greater = partition(data)...return qsort2(less) + equal + qsort2(greater)...return data...

I also think that there are a larger number of temporary lists generated in the "traditional" version.

Solution 3:

Try to compare the list comprehension to an in-place algorithm when the memory goes really big. The code below get a near execution time when sorting 100K integers numbers, but you will probably get stucked in the list comprehension solution when sorting 1M integers. I've made the tests using a 4Gb machine. The full code: http://snipt.org/Aaaje2

classQSort:
def__init__(self, lst):
    self.lst = lst

defsorted(self):
    self.qsort_swap(0, len(self.lst))
    return self.lst

defqsort_swap(self, begin, end):
    if (end - begin) > 1:
       pivot = self.lst[begin]
       l = begin + 1
       r = end
       while l < r:
           if self.lst[l] <= pivot:
               l += 1else:
               r -= 1
               self.lst[l], self.lst[r] = self.lst[r], self.lst[l]

       l -= 1
       self.lst[begin], self.lst[l] = self.lst[l], self.lst[begin]    
       # print begin, end, self.lst
       self.qsort_swap(begin, l)
       self.qsort_swap(r, end)