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 Average Case

Indeed, in a worst-case scenario, Selection Sort is faster than Insertion Sort. However, it is critical that we also take into account the average-case scenario.

Why?

By definition, the cases that occur most frequently are average scenarios. The worst- and best-case scenarios happen only rarely. Let’s look at this simple bell curve:

images/chapter7/new/optimizing_for_optimistic_scenarios-centered-no-text_bell_curve.png

Best- and worst-case scenarios happen relatively infrequently. In the real world, however, average scenarios are what occur most of the time.

And this makes a lot of sense. Think of a randomly sorted array. What are the odds that the values will occur in perfect ascending or descending order? It’s ...

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