A+DS

Quick Sort

Pick a pivot, partition around it.

Choose one element as a "pivot." Put everything smaller on the left and everything larger on the right. The pivot is now in its correct final position! Recursively do the same for the left and right partitions.

  [ ?  ?  ? | PIVOT | ?  ?  ? ]

    < pivot    PIVOT    > pivot
  [ smaller ] [ ✔ ] [ larger ]

  recurse      done!    recurse
  on left              on right

How it works

  1. 1Choose a pivot element (often the last)
  2. 2Partition: move smaller elements left, larger right
  3. 3The pivot lands in its correct sorted position
  4. 4Recursively sort the left and right partitions

Loading...