Overview
Quick Sort is a highly efficient, comparison-based sorting algorithm that uses a divide-and-conquer
strategy to sort lists. It operates by selecting a 'pivot' element from the list 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. This process results in a sorted array with a
significantly reduced number of comparisons.
Time Complexity:
Best case: O(n log n) - The algorithm performs optimally when the pivot divides the array into
two nearly equal halves.
Average case: O(n log n) - On average, the pivot divides the array into reasonably balanced
halves, leading to efficient sorting.
Worst case: O(n²) - If the pivot is poorly chosen (e.g., always the smallest or largest
element), the array may be divided very unevenly, leading to degraded performance.
Space Complexity: O(log n) - It is an in-place sorting algorithm with efficient space
usage, although the recursion stack may require O(log n) space.
function quickSort(list, low, high) if low < high pivotIndex = partition(list, low, high) quickSort(list, low, pivotIndex - 1) quickSort(list, pivotIndex + 1, high)function partition(list, low, high) pivot = list[high] i = low - 1 for j = low to high - 1 if list[j] < pivot i += 1 swap list[i] and list[j] end for swap list[i + 1] and list[high] return i + 1SHORT EXPLANATION------------------1. Choose a pivot element from the list2. Partition the list around the pivot3. Elements smaller than the pivot go to the left4. Elements larger than the pivot go to the right5. Recursively apply quicksort to the left and right sublists6. Continue until the entire list is sorted