Worksheets › Class 12 › Sorting › Cheat sheet
Class 12 Sorting: cheat sheet
CBSE Computer Science. 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 |
Watch out
- Thinking one bubble pass sorts the whole list.
- Mixing up selection sort (smallest swapped to the front) with bubble sort (neighbours swapped).
- Starting insertion sort with the first item: pass 1 places the second.
- Counting n passes instead of n − 1.
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
Practise Sorting
Revise with this page, then practise: every Sorting sheet in the app is new, with an answer key and working.
Coming soon for Android and iPhone.