Sorting and Order Statistics - Quick Sort - The Logic Tutorial

Sorting and Order Statistics: Quick Sort

Quick Sort is a highly efficient sorting algorithm that divides the array into smaller sub-arrays based on a pivot element, and then recursively sorts the sub-arrays.

Algorithm:

The steps involved in Quick Sort are:

1. Choose a pivot element from the array.
2. Partition the array into two sub-arrays - elements less than the pivot and elements greater than the pivot.
3. Recursively apply Quick Sort to the sub-arrays.

Implementation (in pseudocode):

QuickSort(arr[], low, high)
    if low < high
        pivotIndex = Partition(arr, low, high)
        QuickSort(arr, low, pivotIndex - 1)
        QuickSort(arr, pivotIndex + 1, high)

Partition(arr[], low, high)
    pivot = arr[high]
    i = low - 1
    for j = low to high - 1
        if arr[j] <= pivot
            i++
            swap arr[i] and arr[j]
    swap arr[i + 1] and arr[high]
    return i + 1
            

Quick Sort has an average-case time complexity of O(n log n) and a worst-case time complexity of O(n^2). However, in practice, it is often faster than other O(n log n) algorithms like Merge Sort because of its low overhead and good cache locality.

By efficiently sorting elements, Quick Sort is not only used for sorting but also finds applications in order statistics, where finding the kth smallest or largest element in an array is required.