snippetpythonMinor
Python implementation of quicksort
Viewed 0 times
implementationpythonquicksort
Problem
My teacher often tells me that I don't take full advantage of Python capabilities, I would like to know if my implementation of Quicksort is good enough and how could I improve it, aside from doing it in-place
def quickSort(l):
if len(l) > 1:
l,iPiv = partition(l)
return quickSort(l[:iPiv]) + [l[iPiv]] + quickSort(l[iPiv+1:])
else:
return l
def partition(l):
i = 1
iPiv = 0
for j in range(1,len(l)):
if l[j] <= l[iPiv]:
l[i],l[j] = l[j],l[i]
i += 1
l[i-1],l[iPiv] = l[iPiv],l[i-1]
return l,i-1Solution
My teacher often tells me that I don't take full advantage of Python capabilities
Try partitioning with list comprehensions.
This is Pythonic, compact and faster than your
Furthermore, notice the pivot is random. Your original code always uses zero for the pivot. This results in worst-case O(n^2) complexity for sorted inputs. A random pivot mitigates this risk.
As for style, the answer from @janos offers solid guidance also.
Try partitioning with list comprehensions.
import random
def quicksort(s):
len_s = len(s)
if len_s pivot]
return quicksort(L) + E + quicksort(G)This is Pythonic, compact and faster than your
partition function. Furthermore, notice the pivot is random. Your original code always uses zero for the pivot. This results in worst-case O(n^2) complexity for sorted inputs. A random pivot mitigates this risk.
As for style, the answer from @janos offers solid guidance also.
Code Snippets
import random
def quicksort(s):
len_s = len(s)
if len_s < 2:
return s
pivot = s[random.randrange(0, len_s)]
L = [x for x in s if x < pivot]
E = [x for x in s if x == pivot]
G = [x for x in s if x > pivot]
return quicksort(L) + E + quicksort(G)Context
StackExchange Code Review Q#69133, answer score: 8
Revisions (0)
No revisions yet.