What is Quick sort

QuickSort is a sorting algorithm based on the Divide and Conquer algorithm that picks an element as a pivot (any element can be chosen to be a pivot) and partitions the given array around the picked pivot by placing the pivot in its correct position in the sorted array (all left elements of pivot are smaller than pivot and vice versa).

class QuickSort {
  private partition(arr: number[], low: number, high: number): number {
    const pivot = arr[high];
    let i = low - 1;
    for (let j = low; j < high; j++) {
      if (arr[j] <= pivot) {
        i++;
        this.swap(arr, i, j);
      }
    }

    this.swap(arr, i + 1, high);
    return i + 1;
  }

  private swap(arr: number[], i: number, j: number): void {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }

  private quickSortRecursive(arr: number[], low: number, high: number): void {
    if (low < high) {
      const partitionIndex = this.partition(arr, low, high);
      this.quickSortRecursive(arr, low, partitionIndex - 1);
      this.quickSortRecursive(arr, partitionIndex + 1, high);
    }
  }

  public sort(inputArray: number[]): number[] {
    const array = [...inputArray];
    const arrayLength = array.length;
    this.quickSortRecursive(array, 0, arrayLength - 1);
    return array;
  }
}

const quickSort = new QuickSort();
const inputArray = [5, 7, 12, 11, 13, 5, 6, 7];
const sortedArray = quickSort.sort(inputArray);
console.log('Sorted Array:', sortedArray);

Output
[5,5,6,7,7,11,12,13]

Time Complexity:

• Best Case: Ω (N log (N))
  The best-case scenario for QuickSort occur when the pivot chosen at the each step divides the array into roughly equal halves.
  In this case, the algorithm will make balanced partitions, leading to efficient Sorting.
• Average Case: θ ( N log (N))
  QuickSort’s average-case performance is usually very good in practice, making it one of the fastest sorting Algorithm.
• Worst Case: O(N2)
  The worst-case Scenario for QuickSort occur when the pivot at each step consistently results in highly unbalanced partitions. When the array is already sorted and the pivot is always chosen as the smallest or largest element. To mitigate the worst-case Scenario, various techniques are used such as choosing a good pivot (e.g., median of three) and using Randomized algorithm (Randomized QuickSort) to shuffle the element before sorting.

Auxiliary Space: O(1), if we don’t consider the recursive stack space. If we consider the recursive stack space then, in the worst case QuickSort could make O(N)

Advantages of Quick Sort:

• It is a divide-and-conquer algorithm that makes it easier to solve problems.
• It is efficient on large data sets.
• It has a low overhead, as it only requires a small amount of memory to function.

Disadvantages of Quick Sort:

• It has a worst-case time complexity of O(N²), which occurs when the pivot is chosen poorly.
• It is not a good choice for small data sets.
• It is not a stable sort, meaning that if two elements have the same key, their relative order will not be preserved in the sorted output in case of quick sort, because here we are swapping elements according to the pivot’s position (without considering their original positions).

Summary:

• QuickSort is generally believed to be fastest in common real-life settings. This is mainly due to its lower memory consumption (because it use in-place sorting algorithm) which usually affects time performance as well
• The Worst Case scenario can be overcome by Randomized QuickSort (Randomly pick the pivot or shuffle the array before sort)
• When working with LinkedList or need to perform stable sorting, Merge Sort will be preferred due to QuickSort requires random access and is not a stable sort.