August 2017
Intermediate to advanced
222 pages
5h 3m
English
Content preview from A Common-Sense Guide to Data Structures and AlgorithmsBecome an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
Start your free trial
The Efficiency of Bubble Sort
The Bubble Sort algorithm contains two kinds of steps:
-
Comparisons: two numbers are compared with one another to determine which is greater.
-
Swaps: two numbers are swapped with one another in order to sort them.
Let’s start by determining how many comparisons take place in Bubble Sort.
Our example array has five elements. Looking back, you can see that in our first passthrough, we had to make four comparisons between sets of two numbers.
In our second passthrough, we had to make only three comparisons. This is because we didn’t have to compare the final two numbers, since we knew that the final number was in the correct spot due to the first passthrough.
In our third passthrough, we made two comparisons, and in ...