Program of quicksort in python
Quicksort is based on divide and conquer approach In which list is divided into two parts element less than pivot in left side and element greater than pivot in right side.In this program first or lb is assume as pivot element .
For example
a=[8,2,34,7,90]
In this example assume pivot as 8.
When quick sort is apply list is
a=[7,2,8,34,90]
Element which is less than pivot are left side and which is greater than pivot are right side.
Repeatly apply quicksort on sublist.Finally list is sorted. Complexity of quick sort in O (logn). In worst case that is O(n^2).
Python code of quick sort
def qs(a,lb,ub):
if(lb<ub):
i=lb
p=lb
j=ub
while(i<j):
while(a[i]<a[p]):
i=i+1
while(a[j]>a[p]):
j=j-1
if(i<j):
a[i],a[j]=a[j],a[i]
else:
break
a[j],a[p]=a[p],a[j]
qs(a,lb,j-1)
qs(a,j+1,ub)
return(a)
a=[8,2,34,7,90]
print(qs(a,0,4))
Output
2,7,8,34,90
0 Comments