HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Which is better code for implementing quicksort?

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
betterquicksortcodeforwhichimplementing

Problem

This is how I used to implement quicksort:

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

def quickSortHelper(alist,first,last):
   if first= 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]])

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?

Solution

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

Code Snippets

#1st implementation
Average time:
Random: 0.4825087092408925

#2nd implementation
Average time:
Random: 0.48071902671725464
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}
Average time:
Same keys: 0.061130084848424526
Sorted: 0.060439534806328445
A lot of equal keys: 0.032078340092241295
Reverse: 0.06125047935425505
Random: 0.0030011541824106593
#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

Context

StackExchange Code Review Q#138932, answer score: 7

Revisions (0)

No revisions yet.