I Am Running A Test Script to do Quicksort On List Since there are so many ways for partitioning in quicksort and selection of pivot element
i am using here selecting the first index of list as pivot
pivot=list[0]
and then do sorting pivot_pos=quicksort(list,l,h)
l:Lower Bound & h:Higher/Upper Bound
after returning appropriate index of pivot the list is break into two parts such that:
LEFT PART:quicksort(list,l,pivot_pos-1)&
RIGHT PART:quicksort(list,pivot_pos+1,h)
Since the location of pivot is returned we not include him in next recursion call
The quicksortfunction do partitioning in quick while partition function return index that belong to pivot element.
The Full Code Is Below:
#!/usr/bin/env python3
# quicksort by selecting first element as pivot
def partition(list,l,h):
pivot=list[l]
i=l
j=h
while(i<=j):
if list[i]<pivot:
i+=1
if list[j]>pivot:
j-=1
if (list[i]> pivot and list[j]<pivot):
list[i],list[j]=list[j],list[i]
list[j],pivot=pivot,list[j]
return j
def quicksort(list,l,h):
if l<h:
pivot_pos=partition(list,l,h)
quicksort(list,l,pivot_pos-1)
quicksort(list,pivot_pos+1,h)
def main():
list=[] # empty list
# creating a user defined list
n=int(input('Define length of array:'))
for a in range(0,n):
x=int(input('list{}='.format(a)))
list.append(x)
l=0
h=int(len(list)-1)
print("l:",l)
print("h:",h)
print('Before Sorting:',list)
quicksort(list,l,h)
print('After Sorting:',list)
main()
this is good approach of writing quicksort as this not involve too many loop bringing the time complexity to as low as could with this setup
but the code is not working ahead its just stuck you can see o/p hereo/p_of_code
For Those Who Are Unfamiliar With Quicksort Read-It here
Replace your parition with the following:
def partition(lst,l,h):
pivot=lst[l]
i=h
for j in range(h, l, -1):
if lst[j] > pivot:
lst[i],lst[j]=lst[j],lst[i]
i-=1
lst[i],lst[l]=lst[l],lst[i]
return i
Note: I completely rewrote this answer. The original answer I posted wasn't right. This is a more standard solution, and I've tested it and it handles all my test cases. This version uses the first element as the pivot.