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)
Another implementation:
def quicksort(l):
"""Sort list using quick sort.
Complexity: O(n log n). Worst: O(n2)
@param l list to sort.
@returns sorted list.
"""
if len(l) <= 1:
return l
pivot = l[0]
less = []
equal = []
greater = []
for e in l:
if e < pivot:
less.append(e)
elif e == pivot:
equal.append(e)
else:
greater.append(e)
return quicksort(less) + equal + quicksort(greater)