Quick Sort

Quick Sort Animation

Quick Sort Infographic

---

Methodology

In Quick Sort, we will:

• Select the initial Pivot using the Median of Three approach

• Swap Pivot with last number

• Swap Numbers

  • Iterating left to right, find numbers >= to Pivot (GTP)

  • Iterating right to left, find numbers < Pivot (LTP)

  • Swap GTP with LTP while the index of GTP < LTP

• Swap the last GTP with the Pivot

• Quick Sort numbers left of Pivot

• Quick Sort numbers right of Pivot

Complexity

Time Complexity: N log(N)
Space Complexity: 1
Unstable

---