Which is better code for implementing quicksort?

Question

This is how I used to implement quicksort:

def quickSort(alist):
   quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
   if first<last:

       splitpoint = partition(alist,first,last)

       quickSortHelper(alist,first,splitpoint-1)
       quickSortHelper(alist,splitpoint+1,last)


def partition(alist,first,last):
   pivotvalue = alist[first]

   leftmark = first+1
   rightmark = last

   done = False
   while not done:

       while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
           leftmark = leftmark + 1

       while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
           rightmark = rightmark -1

       if rightmark < leftmark:
           done = True
       else:
           temp = alist[leftmark]
           alist[leftmark] = alist[rightmark]
           alist[rightmark] = temp

   temp = alist[first]
   alist[first] = alist[rightmark]
   alist[rightmark] = temp


   return rightmark

alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)

But recently I have come across this way of implementing quicksort:

def quickSort(L):  
    if L == []: return []  
    return     quickSort([x for x in L[1:] if x< L[0]]) + L[0:1] + quickSort([x for x in L[1:] if x>=L[0]])

a = [54,26,93,17,77,31,44,55,20]

a = quickSort(a)
print(a)

Which implementation is better in terms of memory usage and time complexity?

Answer 1

Looks like the first piece is ported from C and second - from Haskell.

2 main differences are:

Temporary lists

The first solution works in-place. It is nice because there are no temporary lists to create and then garbage collect.

This is the difference here.

Cached pivotvalue

The first solution stores pivotvalue in a temporary variable, whereas second uses L[0], which would generate a tiny overhead because of array access. (or maybe not if it gets cached somewhere down the road)

A little difference in how algo works stems from using/not using temporary lists. "pick elements less than pivotvalue, then pivotvalue itself, then elements greater or equal" is easy to comprehend, but requires enough memory to store a whole copy of the list. If you try to implement that in-place instead, you'll end up with what there's at first solution. This piece has O(1) memory complexity in the first case and O(n) in the second.

Speaking of time complexity, leaving housekeeping for temporary lists aside, both algos are similar: in each partitioning, each element gets visited once (in the first case) and twice (in the second case), no matter how big our array is.

However, maintaining temporary lists must have some overhead.

It is said that appending a list is O(1) but also that lists sometimes grow out of allocated size and everything has to be moved then. I'm not sure yet how that works in case of many appends to an array, or if it applies to creating lists through comprehension. I'll check this moment and elaborate on it.

Upd: looks like under the hood list comprehensions do append to an array.

If we take a look at list's source, we can see a comment that says:

This over-allocates proportional to the list size, making room for additional growth. The over-allocation is mild, but is enough to give linear-time amortized behavior over a long sequence of appends()

So, I suppose, we should assume that appending a list is O(1).

That being said, the final judge will be timeit on actual data, but the first solution is closer to hardware and should be faster. I don't see algorithmic reasons for the second code to be faster, besides it being more high-level and eligible to some optimisations by the interpreter (dubious). The second code should also consume more memory.

Both suffer from typical qsort problems like bad performance on already sorted-ish arrays (because sub-arrays are getting partitioned like [] and sub_array[1:])

---

You were interested in time complexity and memory usage, so rant about code style goes to this separate section.

Neither of those pieces look pythonic. The second one was way easier to understand than the first one, but it has its performance problems.

The first one uses 3 lines and one temp variable to swap values, whereas it's a one-liner in Python.

Also there's naming (snake_case is recommended). It's also not expressive enough: quickSortHelper does something related to quickSort - that's obvious, but what exactly?

As it handles recursion it should say so on the label.

Both quickSortHelper and partition could be defined inside quickSort, or in some namespace so that you won't have name collision and also won't have to prepend names with quickSort. That better be consistent, too - so you have recursive_traverse and partition or quickSortHelper and quickSortPartition, but not one of each.

And, of course, you should probably use sorted instead of either of those

Answer 2

Both are very similar - list of 100000 random int elements (from 0 to 100000) was sorted in (average time taken from 10 tries):

#1st implementation
Average time:
Random: 0.4825087092408925

#2nd implementation
Average time:
Random: 0.48071902671725464

That being said, both implementations aren't good. A lot of people forget to include shuffling at the beginning of quicksort and it has really long call stack. When I added some data sets:

data_sets = {'Sorted': [x for x in range(how_many)],
             'Reverse': list(reversed([x for x in range(how_many)])),
             'Random': [random.randint(0, how_many) for x in range(how_many)],
             'A lot of equal keys': [x if x % 2 else 0 for x in range(how_many)],
             'Same keys': [1] * how_many}

I managed to sort data which was 900 elements in length (more than that gave me recursion error) and performance took a big hit in case of sorted / reversed / lot of equal keys data:

Average time:
Same keys: 0.061130084848424526
Sorted: 0.060439534806328445
A lot of equal keys: 0.032078340092241295
Reverse: 0.06125047935425505
Random: 0.0030011541824106593

EDIT: As per suggestion in comment, I ran quicksort (with shuffling) and compared it with list.sort(). quicksort was first, then I ran list.sort(), waited for a bit and re-run with reversed order - times were very close in both cases.

100000 items, 10 tries. Tests were ran on my laptop, so hardware is different than in original post.

#QUICKSORT
Average time:
A lot of equal keys: 0.9257455763466982
Sorted: 1.605769951669822
Reverse: 1.5616443986206265
Random: 1.471783668415066
Same keys: 0.28260723572820756

#SORT
Average time:
A lot of equal keys: 0.025862182302070193
Sorted: 0.004639602319800995
Reverse: 0.004855047960047393
Random: 0.10296205183842413
Same keys: 0.0034818929132122674