Quick Sort

Quick Sort

Description: Quick sort is a highly efficient sorting algorithm that follows the divide-and-conquer principle. It works by selecting a "pivot" element from the array and partitioning the other elements into two subarrays: those less than the pivot and those greater than the pivot. The subarrays are then sorted recursively.

How It Works

1. Choose a Pivot: Select an element from the array as the pivot (commonly the last element).
2. Partitioning: Rearrange the array so that elements less than the pivot come before it and elements greater than the pivot come after it. After partitioning, the pivot is in its final position.
3. Recursion: Recursively apply the above steps to the subarrays on the left and right of the pivot.

Time Complexity

• Worst Case: $O(n^2)$ — occurs when the smallest or largest element is consistently chosen as the pivot (e.g., for an already sorted array).
• Average Case: $O(n \log n)$ — typical case when the pivot is chosen randomly or is the median.
• Best Case: $O(n \log n)$ — when the pivot divides the array into nearly equal halves.

Space Complexity

• Space Complexity: $O(\log n)$ — due to the recursive stack space; however, it can go up to $O(n)$ in the worst case if not implemented with tail recursion.

Stability

• Stability: Quick sort is not a stable sort. Equal elements may not maintain their relative order after sorting.

Example Code

Here's a C++ implementation of quick sort:

#include <iostream>
using namespace std;

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

    for (int j = low; j < high; 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 elements
        }
    }
    swap(arr[i + 1], arr[high]); // Place pivot in the correct position
    return i + 1; // Return the partitioning index
}

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

        // Recursively sort elements before and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Explanation of the Code

1. Function Definitions:

   • partition: Partitions the array around the pivot, placing elements less than the pivot to its left and those greater to its right.
   • quickSort: Recursively sorts the array using the partitioning method.

2. Choosing the Pivot: The last element of the array is chosen as the pivot.

3. Partitioning Process:

   • The partition function iterates through the array, comparing each element with the pivot.
   • Elements smaller than or equal to the pivot are swapped to the front.
   • Finally, the pivot is placed in its correct position, and the function returns its index.

4. Recursive Sort: The quickSort function recursively sorts the subarrays defined by the pivot's position.

5. Output: The sorted array is printed after the sorting is complete.

Conclusion

Quick sort is a powerful and widely used sorting algorithm due to its average-case efficiency and the ability to sort in-place. Its $O(n \log n)$ average time complexity makes it faster than many other algorithms for larger datasets. However, care must be taken in choosing the pivot to avoid worst-case scenarios, especially for already sorted arrays. Despite its lack of stability, quick sort remains a popular choice for sorting in various applications.