5
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! This question is "on the fence", since we review code that you own or maintain, not code found online or code that isn't understood. Please take a moment to read how to get the best value out of Code Review on our meta site. \$\endgroup\$ – Mathieu Guindon Aug 17 '16 at 13:15
  • 3
    \$\begingroup\$ As a side point - you should not be using your own QuickSort implementaiton ever. Python has TIM Sort built in which should be faster - and it does much better pivot selection. \$\endgroup\$ – Benjamin Gruenbaum Aug 17 '16 at 14:21
  • \$\begingroup\$ Use better pivot selection! Your current choice will perform the worst on sorted input. \$\endgroup\$ – Thorbjørn Ravn Andersen Aug 17 '16 at 21:29
7
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ @PeterTaylor, source says (newsize >> 3) + (newsize < 9 ? 3 : 6) and that it results in amortised linear for long sequence of appends, so I went with O(1) \$\endgroup\$ – Daerdemandt Aug 17 '16 at 14:00
  • \$\begingroup\$ yes, re-allocation amortizes itself, because when you expand the list by n, it takes o(n), but that time is shared by the n next appending. \$\endgroup\$ – njzk2 Aug 17 '16 at 15:58
  • \$\begingroup\$ You can't get "closer to hardware" in interpreted code -- the way to get closer to hardware is to write code that leverages natively implemented routines. \$\endgroup\$ – Hurkyl Aug 18 '16 at 1:04
  • \$\begingroup\$ @Hurkyl, There's a minimal sequence of operations that needs to be executed to get what you need, and in case of software, that sequence is limited by hardware. You can get closer to that limit - sometimes by using natively implemented stuff and sometimes by removing some redundant abstractions on a higher level. E.g. , if some language has builtins for sort and for access to first element, then to get minimal element one could just get first element of sorted array - 2 builtins, but may be slower than iterating through the whole array and getting the lowest element manually. \$\endgroup\$ – Daerdemandt Aug 18 '16 at 13:02
7
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ I know it's not part of the question, but it would be interesting to see sort in the mix. \$\endgroup\$ – Oscar Smith Aug 17 '16 at 15:26
  • \$\begingroup\$ @OscarSmith I ran tests on my laptop, so here they are (I used quicksort with shuffling of input, to not have RecursionError. I honestly didn't thought it would be such collosal difference... \$\endgroup\$ – pierscin Aug 17 '16 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.