Quick Sort

Quick Sort

Quick Sort is a highly efficient sorting algorithm and is based on the principle of divide and conquer. 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 recursively sorted.

Here’s how the Quick Sort algorithm works:

1. Choose a pivot: Select a pivot element from the array. There are various strategies for choosing a pivot element, such as selecting the first, last, middle, or a random element.
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. After this partitioning, the pivot is in its final sorted position.
3. Recursively sort sub-arrays: Apply the Quick Sort algorithm recursively to the sub-arrays of elements with smaller values and separately to the sub-array of elements with greater values.
4. Combine: The sub-arrays become sorted, and when all the recursive calls finish, the entire array is sorted.

Here’s a simple implementation of the Quick Sort algorithm in c:

#include <stdio.h>

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

int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // Pivot (last element)
    int i = (low - 1); // Index of smaller element

    for (int j = low; j <= high - 1; j++) {
        // If current element is smaller than or equal to pivot
        if (arr[j] <= pivot) {
            i++; // Increment index of smaller element
            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) {
        // pi is partitioning index, arr[pi] is now at right place
        int pi = partition(arr, low, high);

        // Separately sort elements before partition and after partition
        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[] = {11, 71, 1, 56, 34, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: \n");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

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

Output:

Original array: 
11 71 1 56 34 5 
Sorted array: 
1 5 11 34 56 71 

Time Complexity

The time complexity of the Quick Sort algorithm depends on the choice of the pivot and the partitioning strategy. However, on average, Quick Sort has a time complexity of O(nlogn) for the average and best-case scenarios and O(n2) for the worst-case scenario.

Here’s a breakdown of the time complexity:

1. Best-case scenario: In the best-case scenario, the pivot divides the array into two equal parts, and each partition is roughly half the size of the original array. In this case, the partitioning process occurs O(logn) times, and each partitioning step takes O(n) time. Therefore, the time complexity is O(nlogn).
2. Average-case scenario: In the average-case scenario, the array is partitioned in a way that the pivot divides it into two nearly equal parts. The partitioning process occurs O(logn) times, and each partitioning step takes O(n) time. Therefore, the time complexity is O(nlogn).
3. Worst-case scenario: The worst-case scenario happens when the chosen pivot is always the smallest or largest element in the array, resulting in highly unbalanced partitions. In this case, each partitioning step only reduces the size of the partition by one element. If this happens n times, the time complexity becomes O(n2).