Quick Sort | Python

 

Illustration:

array[] = [15, 85, 35, 95, 45, 55, 75, 77]
low = 0, high =  7, pivot = arr[high] = 77
index of smaller element, index = -1
Traverse: j = low to high-1
j = 0 : array[j] <= pivot, do i++ and swap(array[index], array[j])
index = 0 
array[] = [15, 85, 35, 95, 45, 55, 75, 77] # as index and j are same
#so no change                                           
j = 1 : Since array[j] > pivot # No Change in anywhere
j = 2 : Since array[j] <= pivot, do index++ and swap(array[index], array[j])
index = 1
array[] = [15, 35, 85, 95, 45, 55, 75, 77] # swapping 85 and 35 
j = 3 : array[j] > pivot, So no change in anywhere
j = 4 : Since array[j] <= pivot, do i++ and swap(array[index], array[j])
index = 2
array[] = [15, 35, 45, 95, 85, 55, 75, 77] #Swapping 85 and 45
j = 5 : array[j] <= pivot, do index++ and swap(array[index], array[j]) 
index = 3 
array[] = [15, 35, 45, 55, 85, 95, 75, 77] # Swapping 95 and 55
j = 6 : arr[j] <= pivot, do index++ and swap(array[index], array[j])
index = 4
array[] = [15, 35, 45, 55, 75, 95, 85, 77] 
Now Swap(array[i+1], array[high]) because j == high-1
array[] = [15, 35, 45, 55, 75, 77, 85, 95] # swapping 95 and 77 

Code:

def partition(array, low, high):

pivot = array[high]

index = low - 1

for j in range(low, high):

if array[j] < pivot:

index += 1

array[index], array[j] = array[j], array[index]

array[index + 1], array[high] = array[high], array[index + 1]

return index + 1

def quickSort(array, low, high):

if low < high:

mid = partition(array,low,high)

quickSort(array, low, mid - 1)

quickSort(array, mid+1, high)

if __name__ == "__main__":

array = [10,8,7,9,2,4]

quickSort(array,0,len(array)-1)

print("Sorted array is: ")

for i in array:

print(i,end=' ')

print("\n")