Skip to content
Smartable Academy
Smartable tools

← Programming Proper II: Functions, Lists & Simple Algorithms

Your progress

Checking your sign-in…

Who's learning?

Each profile keeps its own read lessons, badges, streak, and practice scores on this device.

Lesson 10 of 11

Track quiz

Show on a big screen

8 min

Text size

Check the eight ideas. Then try the quiz.

What each way of finding and ordering costs, counted in comparisons
IdeaThe line to keep
The walkWalk the list and answer yes or no. Say yes the moment you find it. Say no only after the whole walk.
The counted loopA 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 searchSort 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 countsCount comparisons, not seconds. In the worst case, doubling the list doubles the walk. It adds one comparison to halving.
One passWalk the unsorted part. Track the smallest seen so far. Swap it to the front, using a temp box.
The whole sortRepeat the pass. Each pass puts the smallest of the rest in place. Sorting a copy keeps the original.
The planWalking needs no order. Halving needs the list sorted first. Sorting costs comparisons, paid once. Count the questions before you pay for order.
The growthDouble 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?

  • It stops and says true at once
  • It carries on to the end
  • It starts again from the top

A walk has no line after its loop. The fare is missing. What does the call give back?

  • True, since the walk ended
  • False
  • Nothing, not false

A counted loop runs over a list of 3. How many times does the test run?

  • 3 times
  • 4 times
  • 2 times

Sorted board of 7 fares. What is the most checks halving needs?

  • 3 checks
  • 7 checks
  • 1 check

What can go wrong if you halve an unsorted board?

  • It counts some fares twice
  • It can miss a fare that is there
  • It finds the fare, but takes longer

A board has 32 fares. What are the worst-case comparisons for the walk and for halving?

  • 32 and 16
  • 6 and 32
  • 32 and 6

The board grows from 32 to 64 fares. What happens to halving's worst case?

  • It doubles, from 6 to 12
  • It stays at 6
  • It adds one, from 6 to 7

Why do we count comparisons, not seconds?

  • A clock changes from phone to phone
  • Seconds are too small to measure well
  • A comparison is quicker than a second

One pass of selection sort runs on 32, 18, 45, 24. What does the list read after?

  • 18, 24, 32, 45
  • 24, 18, 45, 32
  • 18, 32, 45, 24

Why does the swap need a temp box?

  • It makes the swap run much faster
  • Without it, one crate's value is lost
  • It sorts the rest of the list as well

How many passes does selection sort need for five crates?

  • Four
  • Five
  • Ten

How many comparisons does selection sort make on five crates?

  • 5
  • 10
  • 25

A board of 7 fares gets 6 questions. Which plan costs less in the worst case?

  • Walk every time: 42 against 39
  • They cost the same in the worst case
  • Sort once, then halve: 39 against 42

A board of 7 fares gets only 5 questions. Which plan costs less?

  • Walk every time: 35 against 36
  • Sort once, then halve: 36 against 35
  • They cost the same

Selection sort takes 28 comparisons on 8 items. About how many on 16 items?

  • 56
  • 120
  • 30

That is the track. Your next track is Data Handling II: Databases & Structured Data. You will work with tables of records.

Reveal every answer to finish this lesson.