O'Reilly logo

A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required