- Foundation
- About 13 min
- 5 practice questions
Finding a given step and the number of steps
Predict a particular step and count the total steps without writing every line, by tracking what each step fixes in place.
If something looks wrong, please tell us.
Exams may ask 'what is Step III?' or 'how many steps are needed to complete the arrangement?'. You still have to trust the rule, but you can work faster by tracking what each step finishes: after k steps, the first k (or last k) places are already correct.
Useful facts
- After k steps of a 'smallest to the left' rule, the k smallest numbers are in place at the left end.
- The machine stops at the first step at which the line is fully sorted; this can be earlier than the number of elements, because some numbers may already be in place.
- A line of n elements needs at most n - 1 steps, because the last element falls into place automatically.
Worked examples
Example 1. Input: 56 34 12 8 41. Rule: smallest remaining number moves to the left each step. Sorted order: 8 12 34 41 56. Step I: 8 56 34 12 41. Step II: 8 12 56 34 41. Step III: 8 12 34 56 41. Step IV: 8 12 34 41 56. Done in 4 steps, and Step IV is the last step.
Example 2. A machine applies two rules in alternation. Odd steps: the smallest remaining number moves to the left. Even steps: the largest remaining number moves to the right. Input: 56 34 12 8 41. Step I: 8 56 34 12 41. Step II: 8 34 12 41 56 (56 goes to the right end). Step III: 8 12 34 41 56 (12 goes to second place). The line is sorted after 3 steps.
Two rules in alternation
- Input: 56 34 12 8 41
- Step I: 8 56 34 12 41 Odd step: the smallest remaining number moves to the left.
- Step II: 8 34 12 41 56 Even step: the largest remaining number moves to the right end.
- Step III: 8 12 34 41 56 Odd step: 12 goes to second place; the line is sorted.
Example 3. Input: 5 9 3 7. Rule: the largest remaining number moves to the left end each step (descending order, from the left). Sorted descending: 9 7 5 3. Step I: 9 5 3 7. Step II: 9 7 5 3. Sorted after 2 steps.
Example 4. How many steps for the input 3 7 1 9 under 'smallest to the left'? Step I: 1 3 7 9. Sorted already after 1 step.
After k steps of an ascending rule from the left, the k smallest numbers are fixed at the left end.
Key takeaways
- After k steps, k places are fixed.
- The number of steps may be fewer than the number of elements.
- Write each step on paper; do not skip.
Check your understanding
-
1. Rule: at each step the smallest remaining number moves to the next place from the left, and the others keep their order. Input: 47 29 15 6 38. How many steps are needed?
- 3
- 5
- 2
- 4
Show answer
Answer: D. Step I: 6 47 29 15 38. Step II: 6 15 47 29 38. Step III: 6 15 29 47 38. Step IV: 6 15 29 38 47. So 4 steps.
-
2. Rule: at each step the smallest remaining number moves to the next place from the left, and the others keep their order. Input: 47 29 15 6 38. What is Step III?
- 6 15 29 47 38
- 6 15 47 29 38
- 6 15 29 38 47
- 6 29 15 47 38
Show answer
Answer: A. Step I: 6 47 29 15 38. Step II: 6 15 47 29 38. Step III: 29 moves to third place, giving 6 15 29 47 38.
-
3. A line has 7 elements. At most how many steps does a one-move-per-step sorting machine need?
- 7
- 6
- 8
- 5
Show answer
Answer: B. At most n - 1 steps are needed, because the last element falls into place by itself: 7 - 1 = 6.
-
4. A machine alternates two rules. Odd steps: the smallest remaining number moves to the next place from the left. Even steps: the largest remaining number moves to the next place from the right. Input: 47 29 15 6 38. In how many steps is the line sorted?
- 2
- 4
- 3
- 5
Show answer
Answer: C. Step I: 6 47 29 15 38. Step II: 47 goes to the right end, giving 6 29 15 38 47. Step III: 15 goes to second place, giving 6 15 29 38 47, which is sorted. So 3 steps.
-
5. Rule: at each step the smallest remaining number moves to the next place from the left, and the others keep their order. Input: 30 10 50 20 40 60. After Step III, which numbers are certainly fixed at the left end?
- 30 10 50
- 40 50 60
- 10 20 30
- 10 30 50
Show answer
Answer: C. After k steps of a 'smallest to the left' rule, the k smallest numbers are in place at the left. The three smallest are 10, 20 and 30.
Sign in to keep track of the lessons you finish.