AlgoVerse

Table sort

Instead of moving large records around, sort a table of indices, then move each record just once, following the cycles of the permutation.

If each record is large (say, a student's file), moving it is expensive. Table sort works in two steps:

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

Six records; the index table is sorted, then one cycle of four is followed (14 and 50 are already in place).

  1. def table_sort(a):
  2. n = len(a)
  3. # 1. Sort a table of indices instead of the (large) records themselves.
  4. t = list(range(n))
  5. for i in range(1, n):
  6. j = i
  7. while j > 0 and a[t[j - 1]] > a[t[j]]:
  8. t[j - 1], t[j] = t[j], t[j - 1]
  9. j = j - 1
  10. # 2. Move each record once, following the cycles of the permutation t.
  11. for i in range(n):
  12. if t[i] == i:
  13. continue
  14. temp = a[i]
  15. j = i
  16. while t[j] != i:
  17. k = t[j]
  18. a[j] = a[k]
  19. t[j] = j
  20. j = k
  21. a[j] = temp
  22. t[j] = j
  23. return a

Invariant: In step 2, every index with t[j] = j already holds its final record and never moves again.

Start

350141122423264505

Local variables

Orange = changed in this step

a list

351412422650

Call stack

  1. table_sort()line 1
Step 1 of 73
Black = open_cycle · Orange = key stepswap_index: 0/5 · open_cycle: 0/1 · move: 0/3 · close_cycle: 0/1

    How the work grows with input size

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

    • swap_index
    • move
    • current input (n=6)
    01020304681012n = number of itemsswap_indexmove
    Show as a table
    nswap_indexmove
    43.32.2
    67.64.1
    8125
    1021.36.3
    1229.49.3
    Explanation

    The idea

    If each record is large (say, a student's file), moving it is expensive. Table sort works in two steps:

    1. Sort a table of indices: sort an array t of indices so that a[t[0]] ≤ a[t[1]] ≤ …. The records do not move at all; only the small numbers in t do. (Sometimes that is enough: read the records in the order of t.)
    2. Move the records: t is a permutation, and every permutation is made of cycles. In each cycle, keep one record aside, move each of the others once into its final place, and put the kept record into the last free place.

    Cost

    Step 2 moves each record at most once: O(n) record moves, against O(n²) in a plain insertion sort.

    What to watch in the trace

    • In step 1 the bars stand still and only t changes in the memory panel; in step 2 the bars go to their places cycle by cycle.