Quick Sort

1. Description of Quick Sort (Focusing on Partitioning)

The Quick Sort algorithm is a highly efficient sorting algorithm that, like Mergesort, is based on the divide-and-conquer strategy.

Mergesort, which divides its input based on position, Quicksort divides elements according to their value relative to a chosen "pivot" element.

The core idea of Quicksort involves partitioning an array:

1. Divide: It selects a "pivot" element from the array.

2. Partition: It rearranges the array elements such that all elements less than or equal to the pivot are placed to its left, and all elements greater than or equal to the pivot are placed to its right. The pivot element A[s] is placed in its final sorted position s.

3. Conquer: The algorithm then recursively sorts the two sub-arrays to the left and right of the pivot.

This process continues until the sub-arrays are small enough (e.g., a single element), at which point they are considered sorted.

---

2. Quick Sort Pseudocode

The main Quicksort procedure typically calls a separate Partition procedure.

Algorithm Quicksort(A[l..r]):
// Sorts a subarray A[l..r] of array A[0..n-1] in nondecreasing order
// Input: Subarray of array A[0..n-1], defined by its left and right indices l and r
// Output: Subarray A[l..r] sorted in nondecreasing order

if l < r then
    s <- HoarePartition(A[l..r])
    Quicksort(A[l..s-1])
    Quicksort(A[s+1..r])

// s is split position, final place of the pivot

Hoare Partition Procedure

This procedure partitions a subarray A[l..r] using the first element A[l] as the pivot. It scans from both ends of the subarray, swapping elements that are on the wrong side of the pivot until the scans cross or meet.

Partitioning Step in Detail:

• Set two indices: low at the start and high at the end of the array segment.
• Move low forward until an element greater than the pivot is found.
• Move high backward until an element less than or equal to the pivot is found.
• Swap these two elements.
• Continue until low ≥ high, then place the pivot in its correct position.

Algorithm HoarePartition(A[l..r]):
// Partitions a subarray by Hoare’s algorithm, using the first element as a pivot
// Input: Subarray of array A[0..n-1], defined by its left and right indices l and r (l < r)
// Output: Partition of A[l..r], with the split position returned as this function’s value

p <- A[l]    // Choose the first element as the pivot
i <- l       // Left-to-right scanning index
j <- r + 1   // Right-to-left scanning index (one past the end)

repeat
    repeat  i <- i + 1  until A[i] >= p

    repeat  j <- j - 1  until A[j] <= p

    swap(A[i], A[j])
until i >= j    
				// Loop until scanning indices cross over

// Undo the last swap involving crossed over elements
swap(A[i], A[j])

// Place pivot in its final position
swap(A[l], A[j])

return j     // Return final index of the pivot

Page 205

Time Efficiency Analysis using Recurrence Relation

Let C(n) be the number of key comparisons.

• Best-Case Efficiency: The best case occurs when the partitioning splits the array into two nearly equal halves at each step. The recurrence relation is:

• Cbest(n) = 2Cbest(n/2) + n for n > 1, with Cbest(1) = 0.

• According to the Master Theorem, the solution to this recurrence is in Θ(n log2 n). Specifically, for n = 2^k, Cbest(n) = n log2 n.

• Worst-Case Efficiency: The worst case occurs when the partitioning consistently results in one subarray of size n-1 and another of size 0. This happens if the pivot element is always the smallest or largest element in the subarray. The recurrence for the number of key comparisons is:

• Cworst(n) = (n + 1) + n + ... + 3 = (n + 1)(n + 2)/2 - 3 ∈ Θ(n²).

• Thus, in the worst case, Quick Sort has a quadratic time complexity, similar to elementary sorting algorithms like selection sort or bubble sort.

• Average-Case Efficiency: For a randomly ordered array of size n, the average number of key comparisons Cavg(n) is approximated by:

• Cavg(n) ≈ 2n ln n ≈ 1.39n log2 n.

• This shows that on average, Quick Sort performs only about 39% more comparisons than its best case.

Practical Performance: Despite its quadratic worst-case, Quick Sort is often faster than other Θ(n log n) algorithms like Mergesort and Heapsort on randomly ordered arrays due to its very efficient innermost loop. This justifies its name.

• Stability: Quick Sort is not a stable sorting algorithm. A stable sorting algorithm preserves the relative order of equal elements.

• Space Efficiency: Quick Sort requires a stack to store parameters for recursive calls. While its space complexity can be optimized to O(log n), it is generally worse than the O(1) space efficiency of Heapsort.

---

4. Worst-Case in Quick Sort and Mitigation

Conditions Leading to the Worst Case:

When the input array is already sorted in increasing order (or strictly decreasing order), and the first element is consistently chosen as the pivot. All the partitioning steps result in extremely skewed splits. This means one of the two subarrays created by the partition is empty, and the other contains n-1 elements (where n is the size of the subarray being partitioned).

This situation significantly reduces the problem size by only one element at each step, instead of roughly by half. causing the worst-case efficiency for Quick Sort.

For instance, if A[0..n-1] is a strictly increasing array and A[0] is chosen as the pivot. The left-to-right scan will stop at A[0], and the right-to-left scan will go all the way to A[n-1], resulting in a split at position 0.

This leads to recursively sorting an array of n-1 elements (the right subarray) and an empty left subarray. This process repeats, leading to a large number of comparisons.

In such a worst-case scenario, the number of key comparisons Cworst(n) is quadratic, specifically Θ(n^2).

Mitigation Strategies to Avoid Worst Case:

To reduce the likelihood of the worst-case quadratic running time there are several improvements:

Better Pivot Selection Methods:

• Randomized Quick Sort: Picking a random element from the subarray as the pivot. Making the chance of consistently picking the bad pivot across all recursive calls is very low for any specific input.

• Median-of-Three Method: Selecting the median of the leftmost, rightmost, and middle element of the array as the pivot. This approach makes the worst-case scenario (like strictly increasing or decreasing arrays) perform like the best case, as the median of these three elements will be a good splitting point.

Switching to Insertion Sort for Small Subarrays: For very small subarrays (typically between 5 and 15 elements), it's beneficial to switch to Insertion Sort without the Quick Sort's recursive overhead. or even leave them unsorted and apply Insertion Sort to the entire nearly sorted array at the very end.

Three-Way Partitioning: This modification partitions the array into three segments: elements smaller than the pivot, elements equal to the pivot, and elements larger than the pivot. This is particularly effective for arrays with many duplicate elements, helping to achieve more even splits and faster execution.

5. Is Quick Sort an In-Place Sorting Algorithm? Is it a Stable Sorting Algorithm?

Is Quick Sort an In-Place Sorting Algorithm?

Quick Sort is generally not considered a strictly in-place sorting algorithm because it requires a stack to store parameters for its recursive calls.

While the space required for the recursion stack in Quick Sort can be optimized to O(log n), it is still more than the O(1) space efficiency of algorithms like Heapsort, which is explicitly stated as in-place.

Is Quick Sort a Stable Sorting Algorithm?

No, Quick Sort is not a stable sorting algorithm. Algorithms that exchange keys located far apart, which is typical during Quick Sort's partitioning phase, are generally not stable.