The Efficiency of Quicksort

To figure out the efficiency of Quicksort, let’s first determine the efficiency of a partition. When breaking down the steps of a partition, we’ll note that a partition consists of two types of steps:

  • Comparisons: We compare each value to the pivot.
  • Swaps: When appropriate, we swap the values being pointed to by the left and right pointers.

Each partition has at least N comparisons—that is, we compare each element of the array with the pivot. This is true because a partition always has the left and right pointers move through each cell until the left and right pointers reach each other.

The number of swaps depends on how the data is sorted. Each partition has at least one swap, and the most swaps that a partition can ...

Get A Common-Sense Guide to Data Structures and Algorithms now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.