A Common-Sense Guide to Data Structures and Algorithms

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 ...