There are many different versions of quickSort that pick pivot in different ways.
- Always pick the first element or the last element as the pivot
- Pick a random element as a pivot.
- Pick median as the pivot.
I have implemented using the last element as the pivot
everything worked fine but when I tried to implement the same logic to the middle element, it's no working fine.
Here's my code in python:
import random
import time
start = time.time()
def quickSort(a,l,r):
if(l<r):
p = partition(a,l,r)
quickSort(a,l,p-1)
quickSort(a,p+1,r)
def partition(a,l,r):
i = l-1
p = a[(l+(r-l))//2]
for j in range(l,r):
if a[j] <= p:
i += 1
a[i],a[j] = a[j],a[i]
a[i+1],a[r] = a[r],a[i+1]
return (i+1)
N = 10
a = [random.randint(1,100) for i in range(N)]
print(a)
quickSort(a,0,N-1)
print(a)
print("It took %s milli seconds"%((time.time()-start)*100))
This is the output
[88, 35, 55, 68, 96, 23, 44, 77, 78, 71]
[35, 55, 23, 68, 44, 77, 88, 96, 78, 71]
It took 1.5625953674316406 milli seconds