A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

The Efficiency of Quicksort

To figure out the efficiency of Quicksort, let’s first determine the efficiency of a single partition.

When we break down the steps of a partition, we’ll note that a partition involves two primary types of steps:

• Comparisons: We compare each of the values at hand 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, however, will depend upon how the data is sorted. A single partition can have, at ...