Quick Sort

Quick Sort is a Comparison-Based Algorithm.

Quick Sort is slightly faster than Merge Sort and Heap Sort for randomized data, particularly on larger distributions. Run-time is better than $\Theta (n^2)$ for sure.

Example

Another non-tail-recursive example is quick sort, which employs double recursion like a tree traversal. The recursive algorithm chooses a pivot point in an array of unsorted values. Then all values less than the pivot are partitioned to the left of it and all greater values to the right of it, which means the pivot is now in its sorted location. After partitioning, quick sort is called recursively to sort the set of values on both sides of the pivot. The base case for the recursion is when there is only a single value to be sorted, which is a sorted set.

Pseudocode:

QuickSort(A)
Input: A - array of size n
 
1. if n ≤ 1 then
     return
2. p ← choose-pivot(A)
3. i ← partition(A, p)
4. QuickSort(A[0, 1, ..., i - 1])
5. QuickSort(A[i + 1, ..., n - 1])

• choose-pivot() is responsible of choosing a pivot element in array $A$.

• partition() takes in an array $A$ and pivot $p$ and returns the index $i$ where the pivot is placed.

• The partitioning step, which is performed in line 3, divides the array into two parts: elements smaller than the pivot and elements greater than the pivot. The goal is to place the pivot element in its correct sorted position in the array.

• The QuickSort algorithm then recursively applies itself to the two resulting subarrays on either side of the pivot. This process continues until the base case is reached (when subarrays have sizes less than or equal to 1).

• It’s important to note that the choice of the pivot in line 2 can affect the efficiency of the QuickSort algorithm. The efficiency of QuickSort heavily relies on a good choice of pivot to achieve balanced partitioning, which leads to better average and best-case performance. Various strategies can be used to select the pivot, such as choosing the first or last element, selecting a random element, or using median-of-three (choosing the median value among the first, middle, and last elements) to mitigate worst-case scenarios.

• Overall, the QuickSort algorithm based on Hoare’s partitioning scheme is a widely used and efficient sorting algorithm with an average-case time complexity of $O(n\log n)$ and a worst-case time complexity of $O(n^2)$.

Time Complexity

• Running time $\to \Theta (n\log n)$, analysis: average-case
• Worst-case $\to \Theta (n^2)$

Questions

• Suppose QuickSort is implemented with a linear-time algorithm that finds the median value to be the pivot. Then the worst-case runtime of QuickSort becomes

  • $\Theta (n\log n)$ and not $\Theta (n^2)$
  • Since time to find median is linear, it should not affect our run-time as partitioning also takes linear time. So, before we make recursive calls, we are still only doing linear time operations. So, at the end, it should not hurt our run-time analysis.

• Suppose QuickSort implemented with a randomly chosen pivot is modified to stop the recursion when the size of the array is less than $32$ and then uses insertion sort on the smaller arrays. If counting the number of comparisons between two keys of the array, which of the following are true:

  • The expected number of comparisons is $\Theta (n\log (n))$
  • The expected number of comparisons is $\Theta (n\log (n/32))$
  • WHY?

Worst case runtime of QuickSort can be avoided by choosing the median element of the array to be the pivot. Assume we can find the median in linear time.

• False, was on the midterm

Related