The whole sort, written down

One pass puts one crate in place. A whole register needs more. A crate is in place when it sits at its final position.

The rule

Repeat the pass. Each pass puts the smallest of the rest in place. Sorting a copy keeps the original.

Five crates need four passes. Once four crates are in place, the fifth is too. Only one place is left, so the last crate fits it.

The passes make 4, then 3, then 2, then 1 comparisons. That is 10 in all. For n crates, the total is n × (n − 1) ÷ 2.

Here order is the list being sorted. place is the position to fill. look is the position being checked.

`` function selectPass(order, place) { let best = place; for (let look = place + 1; look < order.length; look = look + 1) { if (order[look] < order[best]) { best = look; } } const temp = order[best]; order[best] = order[place]; order[place] = temp; } ``

The pass fills one place with the smallest of the rest. The sort repeats it for each place.

`` function sortByWeight(weights) { const order = []; for (let i = 0; i < weights.length; i = i + 1) { order.push(weights[i]); } for (let place = 0; place < order.length - 1; place = place + 1) { selectPass(order, place); } return order; } ``

The sort copies the weights into order, so the original stays. Then it runs one pass for each place except the last. Take board as the arrival list. sortByWeight(board) gives [12, 18, 26, 33, 41]. The board still reads [26, 41, 18, 33, 12]. The sort worked on a copy.

Move the best marker to the smallest crate of the rest. Then swap it to the front. Do this for every pass.

Try the lab to finish this lesson.