Quick Sort Algorithm

We will discuss the Quick Sort Algorithm, pseudo code, Code implementation of Quick Sort in C, C++, Java, JavaScript, Python, advantages & disadvantages, and time & space complexity of Quick Sort.

1. What is Quick Sort Algorithm?

Quick Sort is also the divide-and-conquer strategy of sorting a list of elements like merge sort.

Quick Sort is a highly efficient sorting algorithm and is based on partitioning an array into smaller sub-arrays.

It works by selecting a ‘pivot‘ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

The worst case of quick sort occurs when the given elements are already sorted or almost sorted.

1.1 Explanation of Quick Sort

1. Choose a pivot: This can be any element from the array.
2. Partitioning: Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it.
3. Recursively apply the above steps to the sub-arrays of elements with smaller and greater values.

2. Pseudocode for Quick Sort

QUICKSORT(S, P, r) 
1. If p < r 
2. then q <- PARTITION(S, p, r) 
3. QUICKSORT(S, p, q-1) 
4. QUICKSORT(S, q+1, r)

2.1 Pseudocode for Partition

PARTITION(S, p, r) 
1. x <- S[r] 
2. i <- p-1 
3. for j <- p to r-1 
4. do if S[j] <= x
5. then i <- i+1 
6. swap S[i] <-> S[j] 
7. swap S[i+1] <-> S[r] 
8. return i+1

3. Recurrence Relation of Quick Sort

3.1 Recurrence Relation in Worst Case

The worst case of quick sort occurs when the pivot we picked turns out to be the least element of the array to be sorted, in every step (i.e. in every recursive call).

A similar situation will also occur if the pivot happens to be the largest element of the array to be sorted.

Then Recurrence Relation of Quick Sort in the worst case is

3.2 Recurrence Relation in Best Case

The best case of quick sort occurs when the pivot we picked happens to divide the array into two almost equal parts, in every step.

Thus, we have k = n/2 and n − k = n/2 for the original array of size n.

Then Recurrence Relation of Quick Sort in the best case is

4. Code Implementation of Quick Sort

4.1 Quick Sort in C

#include <stdio.h>

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

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);

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

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

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

4.1.1 Line-by-Line Explanation of Quick Sort

1. Partition Function:
   • pivot = arr[high]: Choose the last element as the pivot.
   • i = low – 1: Initialize the index of the smaller element.
   • Loop through the array, comparing each element with the pivot.
   • If an element is smaller than the pivot, increment the index of the smaller element and swap the current element with the element at the smaller index.
   • After the loop, swap the pivot element with the element at the index i + 1 to place the pivot in the correct sorted position.
2. Quick Sort Function:
   • Recursively call the quick sort on the sub-arrays formed by partitioning the array around the pivot.

This method ensures that the array is sorted in-place with an average time complexity of O(n log n)

4.2 Quick Sort in C++

#include <iostream>
using namespace std;

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

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);

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

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

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    cout << "Sorted array: \n";
    printArray(arr, n);
    return 0;
}

4.3 Quick Sort in Java

public class QuickSort {
    int partition(int arr[], int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }

    void sort(int arr[], int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            sort(arr, low, pi - 1);
            sort(arr, pi + 1, high);
        }
    }

    static void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    public static void main(String args[]) {
        int arr[] = {38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72};
        int n = arr.length;

        QuickSort ob = new QuickSort();
        ob.sort(arr, 0, n - 1);

        System.out.println("Sorted array:");
        printArray(arr);
    }
}

4.4 Quick Sort in JavaScript

function swap(arr, i, j) {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

function partition(arr, low, high) {
    const pivot = arr[high];
    let i = low - 1;

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

function quickSort(arr, low, high) {
    if (low < high) {
        const pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

const arr = [38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72];
quickSort(arr, 0, arr.length - 1);
console.log("Sorted array:", arr);

4.5 Quick Sort in Python

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1

    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

arr = [38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72]
quick_sort(arr, 0, len(arr) - 1)
print("Sorted array:", arr)

5. Advantages of Quick Sort

1. Efficiency: Quick Sort is very efficient for large datasets. It has an average time complexity of O(n log n)
2. In-place Sorting: It requires only a small, constant amount of additional storage space.
3. Cache Performance: It has excellent cache performance due to its in-place partitioning.

6. Disadvantages of Quick Sort

1. Worst-case Complexity: The worst-case time complexity is O(n²), which can occur if the pivot selection is poor.
2. Stability: Quick sort is not a stable sort. Equal elements might not preserve their relative order.

7. Time and Space Complexity of Quick Sort

8. Applications of Quick Sort

Quick Sort is implemented when

• the programming language is good for recursion
• time complexity matters
• space complexity matters

FAQs