AlgoVerse

Minimum and maximum together

Take the items in pairs: the smaller of a pair is compared only with the minimum and the larger only with the maximum; 3 comparisons per 2 items.

Finding the minimum alone takes n − 1 comparisons, and so does the maximum; done separately that is 2n − 2. The trick is to take the items in pairs. First compare the two items of the pair with each other; the smaller can only be the minimum and the larger only the maximum. So every two items need just 3 comparisons.

Read the full explanation ↓
Input:
n=8PDF export

Eight numbers: 1 comparison for the first pair and 3 for each of the next three pairs, 10 in all instead of 14.

  1. def min_max(a):
  2. n = len(a)
  3. if n % 2 == 1:
  4. lo = a[0]
  5. hi = a[0]
  6. start = 1
  7. else:
  8. if a[0] < a[1]:
  9. lo = a[0]
  10. hi = a[1]
  11. else:
  12. lo = a[1]
  13. hi = a[0]
  14. start = 2
  15. for i in range(start, n - 1, 2):
  16. if a[i] < a[i + 1]:
  17. small = a[i]
  18. big = a[i + 1]
  19. else:
  20. small = a[i + 1]
  21. big = a[i]
  22. if small < lo:
  23. lo = small
  24. if big > hi:
  25. hi = big
  26. return lo, hi

Invariant: lo and hi are the minimum and maximum of the items seen so far.

Start

3081129344752667

Local variables

Orange = changed in this step

a list

38194726

Call stack

  1. min_max()line 1
Step 1 of 29
Black = init, new_min, new_max · Orange = key stepcompare: 0/10 · new_min: 0/1 · new_max: 0/1

    How the work grows with input size

    Average of 12 random graphs per n (fixed seeds). Hollow marker = the input on screen.

    • comparisons
    • current input (n=8)
    010203046810121416n = number of itemscomparisons
    Show as a table
    ncomparisons
    44
    67
    810
    1013
    1216
    1419
    1622
    Explanation

    The idea

    Finding the minimum alone takes n − 1 comparisons, and so does the maximum; done separately that is 2n − 2. The trick is to take the items in pairs. First compare the two items of the pair with each other; the smaller can only be the minimum and the larger only the maximum. So every two items need just 3 comparisons.

    Cost

    At most 3⌊n/2⌋ comparisons, about 1.5n instead of 2n. This is also optimal: no comparison-based algorithm can find both with fewer than ⌈3n/2⌉ − 2 comparisons.

    What to watch in the trace

    • The i arrow marks the first item of each pair; lo and hi are in the memory panel.
    • Compare the number of compare steps with 2n − 2.