Quick Sort

Quick Sort is a highly efficient, comparison-based sorting algorithm that uses the divide and conquer technique. It selects a pivot element, partitions the array around the pivot, and recursively applies the same process to the subarrays. Quick Sort is known for its average-case time complexity of \(O(n \log n)\) and is widely used for sorting large datasets.

In this tutorial, we will go through the Quick Sort Algorithm steps, a detailed example to understand the Quick Sort, and the Time and Space Complexities of this sorting algorithm.

Algorithm

Here are the steps of the Quick Sort algorithm:

  1. If the array has one or no elements, it is already sorted. Return the array. (Base Case)
  2. Choose a pivot element from the array. Common strategies include selecting the first, last, middle, or a random element.
  3. Partition the array into two subarrays:
    • Left subarray: Elements less than the pivot.
    • Right subarray: Elements greater than or equal to the pivot.
  4. Recursively apply Quick Sort to the left and right subarrays. Go to Step 1 for each subarray.
  5. Combine the sorted subarrays and the pivot into one sorted array.

Example

The following is the overall picture of the quick sort for an array [5, 3, 8, 4, 2].