What is Quick Sort?

Quick Sort is an efficient sorting algorithm based on partitioning of an array of data into smaller arrays.

Quick Sort Steps

1. Pick an element as pivot.
2. Partition the array around the pivot.
3. Recursively sort the partitions.

Time and Space Complexity

Average Case: O(n log n)

Worst Case: O(n²) when the pivot is always the smallest or largest element.

Space Complexity: O(log n) for the recursion stack.

Pseudo Code for Quick Sort

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

Quick Sort Visualization

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);
    }
}