Quick Sort

Quick Sort

Quick Sort is an efficient sorting algorithm that works on the divide and conquer principle. It was developed by British computer scientist Tony Hoare in 1959 and published in 1961. The algorithm is well-suited for sorting large datasets, as it has an average-case time complexity of O(n log n), where n is the number of items being sorted. However, the worst-case time complexity is O(n^2), which occurs when the input array is already sorted or reverse sorted. Despite its worst-case time complexity, Quick Sort is often faster in practice than other sorting algorithms like Merge Sort and Heap Sort.

Algorithm

The Quick Sort algorithm works by selecting a "pivot" element from the array and partitioning the other elements into two groups: those less than the pivot and those greater than the pivot. The algorithm then recursively sorts the two groups.

The key steps in the Quick Sort algorithm are:

   Choose a pivot element.
   Partition the array into two groups:
   a. Elements less than the pivot.
   b. Elements greater than the pivot.
   Recursively apply the Quick Sort algorithm to the two groups.

Pseudocode

Here is a high-level pseudocode for the Quick Sort algorithm:

function quickSort(arr, low, high)
  if low < high
    pivotIndex = partition(arr, low, high)
    quickSort(arr, low, pivotIndex - 1)
    quickSort(arr, pivotIndex + 1, high)
  end if
end function

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

C++ Example

Here is a C++ implementation of the Quick Sort algorithm:

#include <iostream>
#include <vector>

void swap(int &a, int &b) {
  int temp = a;
  a = b;
  b = temp;
}

int partition(std::vector<int> &arr, int low, int high) {
  int pivot = arr[high];
  int i = low - 1;

  for (int j = low; j <= high - 1; j++) {
    if (arr[j] <= pivot) {
      i++;
      swap(arr[i], arr[j]);
    }
  }
  swap(arr[i + 1], arr[high]);
  return (i + 1);
}

void quickSort(std::vector<int> &arr, int low, int high) {
  if (low < high) {
    int pivotIndex = partition(arr, low, high);

    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
  }
}

int main() {
  std::vector<int> arr = {10, 7, 8, 9, 1, 5};
  int n = arr.size();
  quickSort(arr, 0, n - 1);
  std::cout << "Sorted array: \n";
  for (int i = 0; i < n; i++)
    std::cout << arr[i] << " ";
  std::cout << std::endl;
  return 0;
}