One pass, and the box in the middle
Show on a big screenFour crates arrived weighing 32, 18, 45 and 24 kg. Put the lightest first. The register lists their weights in arrival order. Best means the lightest crate seen so far. In the code, best holds that crate's position.
- Register: 32, 18, 45, 24. Best = 32.
- 18 < 32. Best becomes 18.
- 45 is not smaller. Best stays 18.
- 24 is not smaller. Best stays 18.
- Swap 18 to the front.
- Position 0 is sorted.
The rule
Walk the unsorted part. Track the smallest seen so far. Swap it to the front, using a temp box.
This is one pass of selection sort. A pass is one trip through the unsorted part. It selects the smallest, then swaps it into place.
Here kg is the register of crate weights. i is the position being checked. The name temp is a box holding one weight briefly.
`` const n = kg.length; let best = 0; for (let i = 1; i < n; i = i + 1) { if (kg[i] < kg[best]) { best = i; } } let temp = kg[best]; kg[best] = kg[0]; kg[0] = temp; ``
After the pass, the register reads [18, 32, 45, 24]. The pass made 3 comparisons for 4 crates.
The swap needs three lines. Copy 18 into temp. Put 32 where 18 was. Put temp at the front.
Watch out!
Halfway through the swap, the register holds two 32s and no 18. The temp box keeps the 18 safe.
Step through the pass. Watch i, best and temp change.
Loading lab…
Try the lab to finish this lesson.