Creative Coding · Session c18

Sorting & Searching

Put things in order, then find them faster than anyone expects.

Picture the yard at a horse show. Six horses stand in a messy line and the judge wants them lined up from shortest to tallest. You can only compare two neighbours at a time, like checking two horses side by side. How would you do it? A computer faces the same problem with any list: names, scores, times. Putting a list in order is called sorting, and finding one item in a list is called searching. In c17 you saw that every extra bit doubles what you can count. This session uses the same doubling idea backwards: halving.

Picture one pass of bubble sort

Heights are in hands (the unit horse people use). Each frame shows the row before the next comparison. The two bars being compared are orange. If the left one is taller, they swap.

pair being compared   in its final place   not finished

Pass 1 made 5 comparisons and 3 swaps. The tallest bar always ends up at the right end, as if it floated up like a bubble. That is where the name comes from. Pass 2 does the same on the first 5 bars, and so on.

Live sketch: bubble sort, one comparison at a time

Press Step to do one comparison. Watch the orange pair and the counter. Press Run to watch it go by itself, and Shuffle to start with a new random order.

let heights = [15, 12, 16, 13, 17, 14]; // horse heights in hands let j = 0; // left bar of the pair we are comparing let pass = 0; // how many passes are finished let comparisons = 0; let running = false; function setup() { createCanvas(420, 260); createButton('Step').mousePressed(stepSort); createButton('Run').mousePressed(() => { running = !running; }); createButton('Shuffle').mousePressed(shuffleBars); } function stepSort() { if (pass >= heights.length - 1) return; // already sorted comparisons++; if (heights[j] > heights[j + 1]) { // wrong order? let temp = heights[j]; // hold one bar heights[j] = heights[j + 1]; heights[j + 1] = temp; // swap } j++; if (j >= heights.length - 1 - pass) { // end of this pass j = 0; pass++; } } function shuffleBars() { heights = shuffle(heights); j = 0; pass = 0; comparisons = 0; } function draw() { background('#ecfeff'); if (running && frameCount % 12 === 0) stepSort(); let done = pass >= heights.length - 1; let w = (width - 40) / heights.length; textAlign(CENTER); for (let i = 0; i < heights.length; i++) { let h = heights[i] * 11; let inPair = !done && (i === j || i === j + 1); let fixed = done || i >= heights.length - pass; noStroke(); fill(fixed ? '#06b6d4' : inPair ? '#f59e0b' : '#a5f3fc'); rect(20 + i * w, 240 - h, w - 10, h, 4); fill(20); text(heights[i], 20 + i * w + (w - 10) / 2, 232); } textAlign(LEFT); text('Comparisons: ' + comparisons, 15, 25); }

Why these lines?

Counting steps: for 6 bars that is 5 + 4 + 3 + 2 + 1 = 15 comparisons. For 4 bars it would be 3 + 2 + 1 = 6. Programmers count comparisons because they show how much work a method really does. Watch the counter: Shuffle and run it again. The count is always 15. The number of swaps changes, but the comparisons do not.

Searching: the slow way and the clever way

Linear search checks the list one item at a time from the start, like walking along the stable doors until you find the right horse.

function linearSearch(list, target) { for (let i = 0; i < list.length; i++) { if (list[i] === target) return i; // found it at place i } return -1; // checked everything: not here }

In the worst case the item is last (or missing), so a list of 100 needs 100 checks.

Binary search is the game "guess my number from 1 to 100". You never guess 1, then 2, then 3. You guess the middle, 50, and the answer "higher" or "lower" throws away half of all the numbers at once.

Picture the halving

How many numbers could still be the secret number, in the worst case?

Before guess 1
100
Before guess 2
at most 50
Before guess 3
at most 25
Before guess 4
at most 12
Before guess 5
at most 6
Before guess 6
at most 3
Before guess 7
at most 1

100 → 50 → 25 → 12 → 6 → 3 → 1. That is 7 guesses at most. It matches the powers of 2 you know: 27 = 128, which is bigger than 100, while 26 = 64 is too small. With 7 guesses you can cover up to 127 numbers. For a million numbers you need only 20 guesses, because 220 = 1,048,576.

Live sketch: I will guess your number

Think of a number from 1 to 100 and do not tell anyone. Tap Higher if your number is higher than my guess, Lower if it is lower, and Yes! when I get it. The blue strip shows the numbers still possible and the orange line is my guess.

The heart of the program is just this (the live version also draws the strip and has the Yes and Restart buttons):

let lo = 1; // smallest number still possible let hi = 100; // biggest number still possible let guess = 50; let count = 1; function setup() { createCanvas(420, 120); createButton('Higher').mousePressed(() => { lo = guess + 1; nextGuess(); }); createButton('Lower').mousePressed(() => { hi = guess - 1; nextGuess(); }); } function nextGuess() { guess = floor((lo + hi) / 2); // always guess the middle count++; } function draw() { background('#ecfeff'); text('Guess ' + count + ': is it ' + guess + '?', 20, 40); text('Numbers left: ' + lo + ' to ' + hi, 20, 70); }

The same idea works on a list in the computer. Here lo and hi are list places, not numbers 1 to 100:

function binarySearch(list, target) { let lo = 0; let hi = list.length - 1; while (lo <= hi) { // keep going while something is left let mid = floor((lo + hi) / 2); // look at the middle if (list[mid] === target) return mid; if (list[mid] < target) lo = mid + 1; // target must be on the right else hi = mid - 1; // target must be on the left } return -1; }
Watch out: binary search only works on SORTED lists.

Throwing away half the list relies on one fact: everything to the left of the middle is smaller and everything to the right is bigger. If the list is a mess, that fact is false. Predict first: the horse heights below are NOT in order. We search for the height 12, and 12 is definitely in the list.

let heights = [15, 12, 17, 11, 16, 13, 14]; let place = binarySearch(heights, 12); console.log(place);

What do you think place will be? Trace the search on paper: write down lo, hi, mid and heights[mid] at each step before opening the answer.

Check the unsorted search

The list places are 0 to 6. Start: lo = 0, hi = 6, mid = 3, heights[3] is 11. Since 11 < 12 the code goes right: lo = 4. Then mid = 5, value 13. Since 13 > 12 it goes left: hi = 4. Then mid = 4, value 16, so hi = 3. Now lo (4) is bigger than hi (3), so the loop stops and the answer is -1: not found, even though 12 sits at place 1.

The code assumed "11 is smaller than 12, so 12 must be to the right". In a sorted list that is true. Here it is not. With the sorted list below, the same function finds 12 at place 1 after only two checks (places 3, then 1).

let heights = [11, 12, 13, 14, 15, 16, 17]; let place = binarySearch(heights, 12); console.log(place);

This is why you sort first, then search. Sorting costs work once, and after that every search is fast.

Quick check
  1. Bubble sort on 4 bars: how many comparisons in total?
  2. You guess a number from 1 to 1000 with binary search. At most how many guesses?

Answers: (1) 3 + 2 + 1 = 6. (2) 10 guesses, because 210 = 1024 is the first power of 2 above 1000 (and 29 = 512 is too small).

Challenges: run, predict, fix, create

Copy the sorting code into your p5 editor to try these.

  1. Modify. Add two more heights to the heights list (for example 11 and 18), so there are 8 horses. Before you run it, predict the number of comparisons for a full sort. Then run it and check the counter.
  2. Predict. Change the list to [12, 13, 14, 15, 16, 17], which is already sorted. Predict the comparisons the code makes before you press Run. Is the code smart enough to stop early? Check, then decide what surprised you.
  3. Bug hunt. A friend wrote the swap like the block below. Run it on the starting list with Step. Which horse disappears, and why? Fix it using temp.
    if (heights[j] > heights[j + 1]) { heights[j] = heights[j + 1]; heights[j + 1] = heights[j]; }
  4. Create. Add a swaps counter next to comparisons and show it on the canvas. Predict the swaps for the starting list [15, 12, 16, 13, 17, 14] from the frames above (pass 1 had 3), then check yours. Does Shuffle change the swaps, the comparisons, or both?
  5. Modify one symbol. Change a single character in stepSort so the bars end up sorted from tallest to shortest instead. Explain in one sentence why that character controls the direction.
  6. Play. In the guessing sketch, secretly choose 100 and count the guesses. Then try 1. Which needs more? Are both within the 7-guess limit?
Check your predictions (after you have tried)
  1. 8 horses: 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 comparisons.
  2. Still 15 comparisons and 0 swaps. This code never stops early, it always does every comparison. (A smarter version stops after a pass with no swaps.)
  3. The swap copies the right bar over the left, then copies the left bar (now a duplicate) back. The first height is lost and the same height appears twice. Fix: let temp = heights[j]; heights[j] = heights[j + 1]; heights[j + 1] = temp;
  4. 6 swaps for the starting list (3, then 2, then 1, then none). Shuffle changes the swaps but not the comparisons.
  5. Change > to < in the comparison. Now a swap happens when the left bar is shorter, so tall bars bubble to the left.
  6. Secret 100 takes 7 guesses (50, 75, 88, 94, 97, 99, 100). Secret 1 takes 6 (50, 25, 12, 6, 3, 1). Both are within 7.
Next session → c19: Recursion
Binary search keeps making the problem smaller: 100 numbers, then 50, then 25. What if a function could solve a problem by handing a smaller copy of the same problem to itself? Next you will write a function that calls itself and use it to grow a tree.
← All lessons
25:00

Ask your tutor