Learn about Quick Sort in Python

Introduction

Quick sort, the name suggests that the algorithm works first, right? Yes, that's true but there are a few conditions. We'll come to this later. Quick sort algorithm works based on divide and conquer algorithm like merge sort. In this case, an element is considered as a pivot element and it can be taken in different ways.

☛The first element as pivot element, or

☛The last element, or

☛The middle element, or

☛A random element.

In our case, we'll use the last element as the pivot.

Illustration of the Quick Sort

arr = [15,85,35,95,45,55,75,77]

low = 0, high = 7, pivot = arr[high] = 77

index of smaller element = -1

Traverse : (j = low to high - 1)

Step 1

j = 0; arr[j] <= pivot, do index++ and swap(arr[index], arr[j])

index = 0

arr[] = [15,85,35,95,45,55,75,77]; No changed

Step 2

j = 1 ; arr[j] > pivot , No change in anyway

j = 2 ; arr[j] <= pivot , do index++ and swap(arr[index], arr[j])

index = 1

arr[] = [15,35,85,95,45,55,75,77] ; Swapping 85 and 35

Step 3

j = 3 ; arr[j] > pivot , No change in anyway

j = 4 ; arr[j] <= pivot , do index++ and swap(arr[index], arr[j])

index = 2

arr[] = [15,35,45,95,85,55,75,77] ; Swapping 85 and 45

Step 4

j = 5 ; arr[j] <= pivot , do index++ and swap(arr[index], arr[j])

index = 3

arr[] = [15,35,45,55,85,95,75,77] ; Swapping 95 and 55

Step 5

j = 6 ; arr[j] <= pivot , do index++ and swap(arr[index], arr[j])

index = 4

arr[] = [15,35,45,55,75,95,85,77] ; Swapping 85 and 75

Step 6

Now, (j==high - 1) , so swap(arr[index + 1] , arr[high])

arr[] = [15,35,45,55,75,77,85,95] ; Swapping 95 and 77

Code

'''Quick Sort in Python'''
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("The sorted array is: ")
    for i in array:
        print(i,end=' ')
    print("\n")

Output

The sorted array is:
2 4 7 8 9 10 

Complexity Analysis

Time Complexity of Quick Sort

The time complexity of Quick Sort depends on two things, the input array and the partitioning process.

Worst Case: O(n^2), occurs when the given array is already arranged either in ascending or descending order.

Best Case: O(nlogn), occurs when we take the middle element as the pivot.

Space Complexity of Quick Sort

Worst Case: O(n)

Average or Best Case: O(logn)