Analysis of Algorithms - Quicksort (Chapter 7)

Overview

• Transitioning from Heapsort (O(n log n) in worst case) to Quicksort.
• Quicksort: Revolutionary algorithm getting average performance below O(n^2).
  • Influences later chapters (8 and 9).
  • Average case: O(n log n).
  • Worst case: O(n^2).

Comparison with Merge Sort

• Merge Sort:
  • Split easily by halving the numbers.
  • Sort two halves recursively.
  • Merge sorted halves takes O(n).
• Quicksort:
  • Spend time splitting (partitioning) the array.
  • Recursively sort partitions.
  • Combining partitions is easy.

Quicksort Algorithm

• Recursive algorithm, compact (three-line) main function.
• Focus on partitioning the array (complex part).

Partition Algorithm

• Goal: Split array into two (less than pivot and greater than pivot).
• Process:
  1. Select pivot (usually last element).
  2. Iterate through the array:
     • Track elements less than or equal to pivot.
     • Swap elements to move them into correct partition.
  3. Place pivot between partitions.
• Example: Pivoting around element '5' using iterative swaps and boundary adjustments.

Performance Analysis

• Average Case (Good Pivot): O(n log n).
  • Balanced split, recursive calls are T(n/2) + T(n/2) + O(n).
• Bad Pivot:
  • Imbalanced split leads to T(n/10) + T(9n/10) + O(n).
• Worst Case: O(n^2).
  • Extreme imbalanced splits (e.g., partially sorted list).

Handling Worst Case

• Worst case often with sorted or nearly sorted data, pivoting with extremes.
• Randomized Quicksort: Randomly select pivot to improve balance.
  • Still can hit worst case but less probable.

Improved Strategies

• Median-of-Three:
  • Pick three random elements.
  • Use the median (middle value) as pivot.
  • Helps avoid extreme variations.

Summary

• Quicksort is efficient on average (O(n log n)).
• Can degrade to O(n^2) but mitigations exist (randomized and median-of-three).
• Next chapter: Sorting in Linear Time.