Quick Sort

Quick Sort is an in-place sorting algorithm that sorts an array using a divide-and-conquer approach. It starts with selecting a pivot element from the array, then partitions the array into two sub-arrays based on whether each of its elements is smaller or larger than the pivot, and finally recursively sorts those sub-arrays.

Explanation

Here is a step-by-step explanation of the Quick Sort algorithm:

Step 1. Initial Checks

• If the array is empty or has only one element low >= high, then it’s already sorted. So, the function returns the array itself.
  • This is the reason behind not using data.length == 1 as the stopping case for partitioning.

Step 2. Partitioning

• Takes the last element’s index high as the pivot.
• Initializes two pointers, i.e., left at the beginning low and right at the end high - 1 (since high is the pivot element).
• Iterates until left and right meet or cross.
  • Moves the pointer left to the right when the elements at left are less than or equal to the pivot.
  • Moves right to the left when the elements at right are greater than or equal to the pivot.
    • If both the above conditions are violated and left and right haven’t crossed, then swaps the numbers at indices left and right.
• If the pointers cross, swaps the pivot with the element at left to place the pivot element in its sorted position.

Here is a visual representation for the first iteration:

Step 3: Recursive Calls

• Recursively sorts the left subarray (data[low..left-1]).
• Recursively sorts the right subarray (data[left+1..high]).

Step 4: Helper Function

• swap(data, a, b): Swaps elements at indices a and b in the array data.

Implementation

The following example written in Java shows an implementation of Quick Sort:

public static void quickSort(int[] data, int low, int high) {
  if(low >= high) {
      return;
  }

  int left = low;
  int right = high;
  int pivot = high;

  while(left != right) {
      while(data[left] <= data[pivot] && left < right) {
          left++;
      }

      while(data[right] >= data[pivot] && right > left) {
          right--;
      }

      swap(data,left, right);
  }

  swap(data, left, pivot);
  quickSort(data,low,left-1);
  quickSort(data,left+1, high);
}

public static void swap(int[] data, int a, int b) {
  int temp = data[a];
  data[a] = data[b];
  data[b] = temp;
}

Time Complexity

• Divide and Conquer: Quick Sort divides the array into smaller subarrays and recursively sorts them.
• Pivot Selection: The choice of pivot affects performance. The last element is often used, but other strategies exist that could improve runtime.
• Average-Case Time Complexity: O(n log n); This occurs when the pivot element roughly divides the array into two equal halves. Randomized selection of the pivot helps achieve this on average, as it’s less likely to consistently pick the smallest or largest element.
• Worst-Case Time Complexity: O(n^2); This worst case scenario occurs when the pivot element is either the smallest or largest element in the array, resulting in partitioning until only one element in one of the sub-arrays.
  • While Merge Sort has a worst-case time complexity of O(n log n), Quick Sort has the advantage of being an in-place sorting algorithm. This means it sorts the data within the same array, avoiding the need for extra space during the sorting process.