Comparing sorting algorithms

Computer Science · Sorting algorithms

Bubble sort, one comparison at a time

Press Next and watch the list change. Keep an eye on the tally: every comparison and every swap is counted.

Before you start: which number do you think will be at the far right after pass 1?

 1  REPEAT  (each time round is one pass)
 2      FOR each neighbouring pair, from left to right
 3          IF left item > right item THEN
 4              swap the two items
 5  UNTIL a whole pass makes no swaps
 6  OUTPUT the list

What you need to know

• A sorting algorithm puts the items of a list into order, such as ascending or descending, numerical or alphabetical.
• Different sorting algorithms reach the same sorted result by different steps, so we compare them by the work they do (comparisons and swaps or moves), how quickly they finish and how simple they are.
• Bubble sort: go through the list comparing each pair of neighbouring items and swap them if they're in the wrong order. At the end of each pass, the largest remaining item has bubbled to the end of the unsorted part.
• Bubble sort repeats passes until a whole pass makes no swaps. That no-swap pass is what shows the list is sorted.
• Insertion sort: the first item starts as the sorted part. Take the next item from the unsorted part and insert it into its correct place in the sorted part, moving larger items along one place. Repeat until every item is inserted.
• To trace an algorithm, carry it out step by step and write down the list after each pass or each insertion.
• Both are simple and sort in place. On the same list, insertion sort usually needs fewer comparisons and moves, so it's usually quicker. On a list that's already or nearly in order, both do very little work (bubble sort can stop early). On long, jumbled lists both become slow.
• To choose between them, look at the size of the list and how close it already is to being in order.

The big picture

A sorting algorithm puts a list in order. Bubble sort compares neighbouring pairs and swaps any in the wrong order, pass after pass, until a pass makes no swaps. Insertion sort slides each item from the unsorted part into its place in the sorted part. Both give the same sorted list, but insertion sort usually needs fewer comparisons and moves. On a nearly sorted list both do little work; on a long, jumbled list both are slow. So the better choice depends on the list's size and how close it is to sorted.

⚠ Watch out

Stopping bubble sort the moment the list looks sorted. Bubble sort can only be sure the list is in order after it has made a whole pass with no swaps, so if the last pass made even one swap, it needs another pass.

Memory hook

Bubbles rise: in bubble sort the biggest item floats to the end, one pass at a time. Insertion is like sorting a hand of cards: pick up the next card and slide it into the right spot.

Check yourself

Cover the page. When does bubble sort stop, and why isn't one pass enough? What happens to each item in insertion sort? When would the two do about the same work?