Algorithm Analysis: Quicksort Overview

Study Notes

Algorithm Analysis and Design - Quicksort

Quicksort Overview:
- A divide-and-conquer sorting algorithm.
- Opposite of merge sort; most of the work occurs in the divide step.
- Sorts in place.
- Average case running time: O(n log n).
- Worst case running time: O(n²).
Quicksort Steps:
- Divide: Partition the array around a pivot element such that all elements in the lower subarray are less than or equal to the pivot and all elements in the upper subarray are greater than the pivot.
- Conquer: Recursively sort the two subarrays.
- Combine: Trivial, as the subarrays are already sorted.
Partitioning Subroutine:
- The algorithm maintains two indices, i and j.
- i tracks the last element of the lower subarray that is less than or equal to the pivot.
- j iterates through the array (except for the pivot).
- Elements in the lower subarray are all less than or equal to the pivot.
- Elements in the upper subarray are greater than the pivot.
- j initially is equal to p and i = p-1.
- If A[j] is less than or equal to the pivot then increment i and swap A[i] and A[j]. -After partitioning, the pivot is exchanged with A[i+1]. -The algorithm then returns i+1 as the partitioning index, or the pivot index.
Running time of Partitioning:
- Every element is compared once in the partitioning subroutine, thus the running time is O(n).
Quicksort Pseudocode:
- QUICKSORT(A, p, r):
  - If p < r:
    - q ← PARTITION(A, p, r)
    - QUICKSORT(A, p, q-1)
    - QUICKSORT(A, q+1, r)
- Initial Call: QUICKSORT(A,1, A.length)
Worst-Case Analysis
- Occurs when the elements are sorted or reversed, resulting in one subarray having almost no elements.
- Worst case time is O(n^2).
Best-Case Analysis:
- Partitioning always splits the array into roughly equal halves.
- Best case time is O(n log n).

Randomized-Quicksort

Randomized Partitioning:
- Randomized quicksort often avoids the worst-case scenario of quicksort.
- The RANDOMIZED-PARTITION function selects a random element from within the range [p,r] and puts it in the last position of the subarray A[p..r], the pivot. -The pivot is then put into its correct position using the partitioning subroutine.
- RANDOMIZED-PARTITION(A, p, r):
  - i= RANDOM(p,r)
  - exchange A[r] with A[i]
  - return PARTITION(A, p, r)

Quicksort in Practice

Practical Considerations:
- Quicksort is a highly optimized algorithm and exceptionally effective in practice over other similar algorithms.
- Practical quicksort implementations often use additional techniques like median-of-three or other methods to select the pivot to prevent worst-case scenarios for performance concerns.