Fig. 41. §3 AI and Computing
Sorting Machine
A sorting algorithm is a step-by-step recipe a computer follows to put things in order.
1Facts
- Shelf
- AI and Computing
- Kind
- Built from a recipe
- Sound
- Yes
- Hands-on
- Yes
- Licenses
- Own work (made in the page)
2How to play
Tap it to sort. Hands-on: pick a piece up and drop it on another place to swap them.
3Its controls
Table I. Every control on this Splash.
| Control | Kind | Range | Start |
|---|---|---|---|
| Sort the bars | Tap | ||
| Sort | Button | ||
| Algorithm | List | 8 choices | Bubble sort |
| View | List | 4 choices | Bars |
4About it
A sorting algorithm is a step-by-step recipe a computer follows to put things in order. Bubble sort keeps swapping neighbors that are the wrong way around; quicksort picks one item and splits the rest into smaller and bigger piles; merge sort sorts small groups, then merges them. On a long list, some need far fewer steps than others.
Tap it: eight bars sort themselves, each gliding to its new place, while a counter counts the swaps, or moves for merge sort; then they shuffle back. Pick one of eight algorithms in the Splash tab. Listen too: each comparison plays the two bars' notes softly, each swap the moving bar's note, every algorithm on its own instrument, so you hear how it works. The View option shows the same steps as crates of different sizes, a ring of colored pucks that sorts into a color wheel, or the classic dots. The steps come from each algorithm's real code, checked step by step against separate reference code. With ✋ Hands-on on, drop a piece on another place and the two swap.
5Details
- Splats
- Opens at 200,000 at Mid Detail, 59,999 at Low, and up to 830,000 at Max
6Is it right?
All eight implementations match independent comparison and array-change traces. The display counts swaps, except that merge sort counts single-item moves. The bar animation omits comparisons that do not change the array.
Correct.
Bubble sort compares adjacent items in shrinking passes.[1]
It runs all shrinking passes, including any pass with no swaps.
Correct.
Quicksort uses the Lomuto partition.[2]
The last item is the pivot, values strictly below it move left, self-swaps are omitted, and left partitions run first.
Correct.
Merge sort combines runs bottom up and stably.[3]
Runs double in size. Equal values stay left; each needed right item is moved ahead of a left item.
Correct.
Insertion sort moves each new value into the sorted prefix.[4]
Adjacent swaps move the value left until it is in order.
Correct.
Selection sort selects the minimum of each remaining suffix.[5]
It exchanges the selected minimum with the current destination, omitting self-swaps.
Correct.
Cocktail sort alternates forward and backward sweeps.[6]
Both sweeps shrink the active bounds and compare neighboring values.
Correct.
Shell sort uses gaps 4, 2, 1.[7]
Each gap performs insertion by exchanges within the interleaved subsequences.
Correct.
Heap sort builds and drains a max heap.[8]
Heap construction starts from the last parent and repeated extraction moves the maximum to the sorted suffix.
Correct.
The counter counts swaps or merge moves.[3][1]
For every recorded stage of all eight default traces, the seven-segment display shows the stage count and uses MOVES for merge, SWAPS otherwise.
Simplified.
Animated bar movements show only the exchanges or moves.[3][1]
Only changed arrays are saved; comparisons with no array change have no visible step. Merge insertion is one move, not a count of every write.
- [1]Bubble sort, NIST Dictionary of Algorithms and Data Structures
- [2]Quicksort, Sedgewick and Wayne, Princeton Algorithms
- [3]Mergesort, Sedgewick and Wayne, Princeton Algorithms
- [4]Insertion sort, NIST Dictionary of Algorithms and Data Structures
- [5]Selection sort, NIST Dictionary of Algorithms and Data Structures
- [6]Bidirectional bubble sort, NIST Dictionary of Algorithms and Data Structures
- [7]Shell sort, NIST Dictionary of Algorithms and Data Structures
- [8]Priority queues and heapsort, Sedgewick and Wayne, Princeton Algorithms
- Simplified
- There are eight fixed bars in the picture. Comparison-only work is invisible. Merge counts one insertion move even when that move rewrites several array slots, so its counter is not comparable to a count of memory writes.
7Sources and credits
Made in Splashery. Its code is MIT.
