patternpythonMinor
Which is better code for implementing quicksort?
Viewed 0 times
betterquicksortcodeforwhichimplementing
Problem
This is how I used to implement quicksort:
But recently I have come across this way of implementing quicksort:
Which implementation is better in terms of memory usage and time complexity?
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 -
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:
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
EDIT:
As per suggestion in comment, I ran
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.48071902671725464That 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.0030011541824106593EDIT:
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.0034818929132122674Code Snippets
#1st implementation
Average time:
Random: 0.4825087092408925
#2nd implementation
Average time:
Random: 0.48071902671725464data_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.0034818929132122674Context
StackExchange Code Review Q#138932, answer score: 7
Revisions (0)
No revisions yet.