Sorting and Ranking

Top-K Select

Find the three largest values in a list by repeated max-pick: locate the current maximum, record it, remove it from the working copy, and repeat. The trace shows work shrinking and result filling one element at a time.

By hand

Copy values into work so the original is not modified. Loop exactly three times: find the maximum of whatever remains in work, append it to result, and remove it so it cannot be chosen again.

naive.py
Replay: real traced execution (multi-file project)
values = [4, 7, 2, 9, 5, 8, 1, 6]
work = list(values)
result = []
for _ in range(3):
    best = max(work)
    result.append(best)
    work.remove(best)
print('RESULT:', result)

  1. values ← [4, 7, 2, 9, 5, 8, 1, 6]

    1values = [4, 7, 2, 9, 5, 8, 1, 6]2work = list(values)
    values this step[4, 7, 2, 9, 5, 8, 1, 6]values

  2. work ← [4, 7, 2, 9, 5, 8, 1, 6]

    1values = [4, 7, 2, 9, 5, 8, 1, 6]2work = list(values)3result = []
    values this step[4, 7, 2, 9, 5, 8, 1, 6]work

  3. result ← []

    2work = list(values)3result = []4for _ in range(3):
    values this step[]result

  4. _ ← 0

    3result = []4for _ in range(3):5    best = max(work)
    values this step0_

  5. best ← 9

    4for _ in range(3):5    best = max(work)6    result.append(best)
    values this step9best

  6. result ← [9]

    5best = max(work)6result.append(best)7work.remove(best)
    values this step[] → [9]result

  7. work ← [4, 7, 2, 5, 8, 1, 6]

    6    result.append(best)7    work.remove(best)8print('RESULT:', result)
    values this step[4, 7, 2, 9, 5, 8, 1, 6] → [4, 7, 2, 5, 8, 1, 6]work

  8. _ ← 1

    3result = []4for _ in range(3):5    best = max(work)
    values this step0 → 1_

  9. best ← 8

    4for _ in range(3):5    best = max(work)6    result.append(best)
    values this step9 → 8best

  10. result ← [9, 8]

    5best = max(work)6result.append(best)7work.remove(best)
    values this step[9] → [9, 8]result

  11. work ← [4, 7, 2, 5, 1, 6]

    6    result.append(best)7    work.remove(best)8print('RESULT:', result)
    values this step[4, 7, 2, 5, 8, 1, 6] → [4, 7, 2, 5, 1, 6]work

  12. _ ← 2

    3result = []4for _ in range(3):5    best = max(work)
    values this step1 → 2_

  13. best ← 7

    4for _ in range(3):5    best = max(work)6    result.append(best)
    values this step8 → 7best

  14. result ← [9, 8, 7]

    5best = max(work)6result.append(best)7work.remove(best)
    values this step[9, 8] → [9, 8, 7]result

  15. work ← [4, 2, 5, 1, 6]

    6    result.append(best)7    work.remove(best)8print('RESULT:', result)
    values this step[4, 7, 2, 5, 1, 6] → [4, 2, 5, 1, 6]work

  16. for _ in range(3):

    3result = []4for _ in range(3):5    best = max(work)

  17. stdout ← RESULT: [9, 8, 7]

    7    work.remove(best)8print('RESULT:', result)
    values this stepRESULT: [9, 8, 7]stdout

The Pythonic way

heapq.nlargest(3, values) returns the three largest values in descending order without modifying the input. Internally it maintains a min-heap of size k, scanning the list once in O(n log k) — more efficient than repeated max for large k.

library.py 
import heapq
values = [4, 7, 2, 9, 5, 8, 1, 6]
result = heapq.nlargest(3, values)
print('RESULT:', result)

RESULT: [9, 8, 7]

Implementation notes

  • work.remove(best) removes the first occurrence of the maximum; since all values here are distinct, this is unambiguous.
  • The loop variable _ signals "the count matters, the value does not"; it still appears in the trace as 0, 1, 2.
  • For k ≪ n, prefer heapq.nlargest; for k close to n, sorted(values, reverse=True)[:k] is simpler; for k = 1, just max(values).