Data Structures and Algorithms - Quick Sort - Day 6

Quick Sort

Up to now, all the sorting algorithms we have tried are O(n^2) time complexity in average case. But quicksort comes in with an average case time complexity of O(n.log(n)) which is faster than O(n^2). But the complexity of the algorithm depends on the way we are selecting the pivot.

Algorithm

In quicksort, we select an element as pivot, for our case we will select the last element of the array as pivot.

Then we go through all the elements of the array, making sure the elements smaller than the pivot are on the left hand side of the pivot and the elements larger are on the right.

Then we take the left and right side of the array and perform the same task i.e. select a pivot, put items smaller than the pivot to the left of the pivot and items greater to the right of the pivot.

We repeat this process until we have a 1 element array.

Example

Starting array -

9 7 2 1 3 10 11 5

We take 5 (index 7) as out pivot. We start at i=0 (index 0) and go up to index 6. We also have j = 0

Now we compare array element at index i with the pivot i.e. 5 and we swap index i value with index j value. Here 9>5 so no swap and i increases by 1 so now

i = 1
j = 0
pivot = 5
9 7 2 1 3 10 11 5

now the same thing happens for i = 1 so we increment i

For i=2 we are seeing the element 2 which is less than 5 so we swap index j (0) with index i (2)

And in the end increment both i and j.

Now the situation is -

i = 3
j = 1
pivot = 5
2 7 9 1 3 10 11 5

For i=3 we are seeing the element 1 which is less than 5 so we swap index j (1) with index i (3)

And in the end increment both i and j.

Now the situation is -

i = 4
j = 2
pivot = 5
2 1 9 7 3 10 11 5

For i=4 we are seeing the element 3 which is less than 5 so we swap index j (2) with index i (4)

And in the end increment both i and j.

Now the situation is -

i = 5
j = 3
pivot = 5
2 1 3 7 9 10 11 5

Now for i=5 and i=6 there are no swaps. In the end we swap index j (3) with pivot -

2 1 3 5 7 9 10 11

Now we need to apply quicksort on the arrays 2 1 3 and 7 9 10 11

That part is up to you for trying.

Code in C

#include <stdio.h>

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = arr[high];
        int i = low;

        for (int j = low; j <= high - 1; j++) {
            if (arr[j] < pivot) {
                swap(&arr[i], &arr[j]);
                i++;
            }
        }

        swap(&arr[i], &arr[high]);
        quickSort(arr, low, i - 1);
        quickSort(arr, i + 1, high);
    }
}


int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = 6;

    quickSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}

Time and space complexity

Best and average case time complexity - O(n log(n))

Worst case time complexity - O(n^2) - Worst case happens when all the pivots we select have all the elements to the left or the right. If we consider the algorithm we have used for selecting pivot we get the worst case if the array is already sorted.

The space complexity of this algorithm is on the recursive calls

Best and average case space complexity - O(log(n))

Worst case space complexity - O(n^2)