Track quiz
Check the eight ideas. Then try the quiz.
| Idea | The line to keep |
|---|---|
| The walk | Walk the list and answer yes or no. Say yes the moment you find it. Say no only after the whole walk. |
| The counted loop | A counted loop has three parts. Init makes the counter, once. Test checks before every turn. Update moves the counter, after every turn. The loop ends when the test says no. |
| The halving search | Sort the list first. Then check the middle. If it matches, stop. If it is smaller than the target, search the right half. If it is bigger, search the left half. No part left means not found. |
| The two counts | Count comparisons, not seconds. In the worst case, doubling the list doubles the walk. It adds one comparison to halving. |
| One pass | Walk the unsorted part. Track the smallest seen so far. Swap it to the front, using a temp box. |
| The whole sort | Repeat the pass. Each pass puts the smallest of the rest in place. Sorting a copy keeps the original. |
| The plan | Walking needs no order. Halving needs the list sorted first. Sorting costs comparisons, paid once. Count the questions before you pay for order. |
| The growth | Double the list and watch each count. The walk doubles. Halving adds one. Selection sort grows about four times. |
A walk finds the fare it wants on check 4. What does it do next?
A walk has no line after its loop. The fare is missing. What does the call give back?
A counted loop runs over a list of 3. How many times does the test run?
Sorted board of 7 fares. What is the most checks halving needs?
What can go wrong if you halve an unsorted board?
A board has 32 fares. What are the worst-case comparisons for the walk and for halving?
The board grows from 32 to 64 fares. What happens to halving's worst case?
Why do we count comparisons, not seconds?
One pass of selection sort runs on 32, 18, 45, 24. What does the list read after?
Why does the swap need a temp box?
How many passes does selection sort need for five crates?
How many comparisons does selection sort make on five crates?
A board of 7 fares gets 6 questions. Which plan costs less in the worst case?
A board of 7 fares gets only 5 questions. Which plan costs less?
Selection sort takes 28 comparisons on 8 items. About how many on 16 items?
That is the track. Your next track is Data Handling II: Databases & Structured Data. You will work with tables of records.