In-place QuickSort in Python
Here is another implementation:
def quicksort(alist):
if len(alist) <= 1:
return alist
return part(alist,0,len(alist)-1)
def part(alist,start,end):
pivot = alist[end]
border = start
if start < end:
for i in range(start,end+1):
if alist[i] <= pivot:
alist[border], alist[i] = alist[i], alist[border]
if i != end:
border += 1
part(alist,start,border-1)
part(alist,border+1,end)
return alist
I have started learning python lately and the following is my attempt at implementing quicksort using python. Hope it is helpful. Feedback is welcomed :)
#!/usr/bin/python
Array = [ 3,7,2,8,1,6,8,9,6,9]
def partition(a, left, right):
pivot = left + (right - left)/2
a[left],a[pivot] = a[pivot], a[left] # swap
pivot = left
left += 1
while right >= left :
while left <= right and a[left] <= a[pivot] :
left += 1
while left <= right and a[right] > a[pivot] :
right -= 1
if left <= right:
a[left] , a[right] = a[right], a[left] # swap
left += 1
right -= 1
else:
break
a[pivot], a[right] = a[right] , a[pivot]
return right
def quicksort(array , left,right):
if left >= right:
return
if right - left == 1:
if array[right] < array[left]:
array[right], array[left] = array[left] , array[right]
return
pivot = partition(array, left, right)
quicksort(array, left, pivot -1)
quicksort(array, pivot+1,right)
def main():
quicksort(Array, 0 , len(Array) -1)
print Array
main()
Sure not the best way, plus this famous algorithm will have dozens of perfect implementations.. this is mine, quite easy to understand
def sub_partition(array, start, end, idx_pivot):
'returns the position where the pivot winds up'
if not (start <= idx_pivot <= end):
raise ValueError('idx pivot must be between start and end')
array[start], array[idx_pivot] = array[idx_pivot], array[start]
pivot = array[start]
i = start + 1
j = start + 1
while j <= end:
if array[j] <= pivot:
array[j], array[i] = array[i], array[j]
i += 1
j += 1
array[start], array[i - 1] = array[i - 1], array[start]
return i - 1
def quicksort(array, start=0, end=None):
if end is None:
end = len(array) - 1
if end - start < 1:
return
idx_pivot = random.randint(start, end)
i = sub_partition(array, start, end, idx_pivot)
#print array, i, idx_pivot
quicksort(array, start, i - 1)
quicksort(array, i + 1, end)
Ok first a seperate function for the partition subroutine. It takes the array, the start and end point of interest, and the index of pivot. This functions should be clear
Quicksort then call the partition subroutine for the first time on the whole array; then call recursevely itself to sort everything up to the pivot and everything after.
ask if you dont understand something