Class 12 Sorting — cheat sheet

Bubble, selection and insertion sort as the textbook codes them, pass by pass, with their swaps, shifts and comparisons, and their time complexity.

Key ideas

Bubble sort compares neighbours from left to right and swaps any pair out of order; after pass k the k largest items are in place at the end.

Selection sort finds the smallest item of the unsorted part and swaps it to the front of that part: at most one swap a pass.

Insertion sort takes the next item (pass 1 takes the second) and shifts the larger items of the sorted left part one place right to fit it in.

A list of n items needs at most n − 1 passes.

The textbook’s bubble sort never stops early, so it always makes (n − 1) + (n − 2) + … + 1 comparisons.

All three sorts take O(n²) time in the worst case, as each has a loop inside a loop.

Remember

Bubble, pass 1

5, 1, 4, 2, 8 → 1, 4, 2, 5, 8 (3 swaps)

Selection, pass 1

5, 1, 4, 2, 8 → 1, 5, 4, 2, 8 (1 and 5 swap places)

Insertion, passes 1 and 2

5, 1, 4, 2, 8 → 1, 5, 4, 2, 8 → 1, 4, 5, 2, 8

Bubble comparisons, n items

n(n − 1)/2: 6 items → 15

Total swaps or shifts

the number of pairs out of order: in 5, 1, 4, 2 the pairs 5 1, 5 4, 5 2, 4 2 give 4

Decreasing order

bubble sort swaps when the left item is the smaller

Worked example

Sort 29, 12, 28, 54, 47, 31 into increasing order (a) by selection sort and (b) by insertion sort, writing the list after every pass.

Working: selection: swap the smallest of the rest to the front; insertion: insert the next item into the sorted left part

Answer: (a) 12, 29, 28, 54, 47, 31 → 12, 28, 29, 54, 47, 31 → 12, 28, 29, 54, 47, 31 → 12, 28, 29, 31, 47, 54 → 12, 28, 29, 31, 47, 54; (b) 12, 29, 28, 54, 47, 31 → 12, 28, 29, 54, 47, 31 → 12, 28, 29, 54, 47, 31 → 12, 28, 29, 47, 54, 31 → 12, 28, 29, 31, 47, 54

Sorting

Key ideas

Remember

Watch out

Worked example