Cyclic Sort

The previous pattern paid the cost of sorting and got a single pass in return. This lesson’s pattern skips sorting entirely. Its idea is one sentence: if a value tells you its own destination, no comparison is needed. When values lie between 1 and n, value v’s place is position v-1; every value is sent straight home, and the value that comes out of that home determines the next placement.

What is paid in exchange is a heavy precondition, and it is in fact two separate preconditions: values must lie between 1 and n, and values must be without duplicates. This lesson breaks each separately, because the consequence of breaking each is also separate: one produces a wrong answer, the other produces no answer at all.

The Pattern’s Idea and Its Two Preconditions

The pattern stops at a position and looks at the value there. If the value is not at its home, it sends the value home; the new value that comes out of that home lands at the same position and the same operation repeats. If the value is already home, it moves to the next position. Because every swap puts at least one value permanently home, the total swap count cannot exceed n.

This count’s guarantee comes directly from the precondition. When a value is sent home, if another value already sits there, that value must be different; otherwise the swap advances nothing and the same two values swap places forever.

PP32. The array has 12 values and the target range is 1..12; seed 20260218. PP33. There are three corpora and all three come from the same generator: a 1..n arrangement (no duplicates, within range), duplicate values, and arrays with two values moved out of range. PP34. The oracle uses one of the comparison-based procedures measured in the Algorithms course and counts every comparison as one step. The procedure itself is not repeated here. PP35. The pattern is given a step cap (400 steps). A run that hits the cap returns did not stop and is counted as diverging from the oracle.

SEED, LENGTH, CORPUS_SIZE = 20260218, 12, 40


def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def value_corpus(seed=SEED, n=CORPUS_SIZE, length=LENGTH):
    """Three corpora: 1..n arrangement; duplicate values; out-of-range values."""
    r = generator(seed)
    items = []
    for i in range(n):
        arrangement = list(range(1, length + 1))
        for j in range(length, 1, -1):
            k = r(j)
            arrangement[j - 1], arrangement[k] = arrangement[k], arrangement[j - 1]
        duplicates = [r(length) + 1 for _ in range(length)]
        out_of_range = list(arrangement)
        for _ in range(2):
            out_of_range[r(length)] = length + 2 + r(length)
        items.append({"no": i + 1, "arrangement": arrangement,
                     "duplicates": duplicates, "out_of_range": out_of_range})
    return items


class Counter:
    def __init__(self):
        self.step = 0

    def count(self):
        self.step += 1


def oracle_arrangement(array, s):
    """Comparison-based selection sort. Always correct, always expensive."""
    a = list(array)
    for i in range(len(a)):
        least = i
        for j in range(i + 1, len(a)):
            s.count()
            if a[j] < a[least]:
                least = j
        a[i], a[least] = a[least], a[i]
    return a


def pattern_plain(array, s, cap=400):
    """PRECONDITION: values must be within 1..n and WITHOUT DUPLICATES."""
    a, n = list(array), len(array)
    i = 0
    while i < n:
        s.count()
        if s.step > cap:
            return "did not stop"
        home = a[i] - 1
        if 0 <= home < n and home != i:
            a[i], a[home] = a[home], a[i]
        else:
            i += 1
    return a


def pattern_guarded(array, s, cap=400):
    """Duplicate guard added: no swap if the value at home is already the same."""
    a, n = list(array), len(array)
    i = 0
    while i < n:
        s.count()
        if s.step > cap:
            return "did not stop"
        home = a[i] - 1
        if 0 <= home < n and a[i] != a[home]:
            a[i], a[home] = a[home], a[i]
        else:
            i += 1
    return a


POOL = (("1..n arrangement   ", "arrangement"),
        ("duplicate values   ", "duplicates"),
        ("out-of-range values", "out_of_range"))

K = value_corpus()
print("corpus:", len(K), "arrays x", LENGTH, "values | examples:")
print("  arrangement :", K[0]["arrangement"])
print("  duplicates  :", K[0]["duplicates"])
print("  out_of_range:", K[0]["out_of_range"])
print()
print("pattern    pool                  diverging/40  pattern  oracle   ratio")
for kad, pattern in (("plain    ", pattern_plain), ("guarded  ", pattern_guarded)):
    for ad, key in POOL:
        diverging, pk, ok = 0, 0, 0
        for k in K:
            s1, s2 = Counter(), Counter()
            a = pattern(k[key], s1)
            b = oracle_arrangement(k[key], s2)
            pk, ok = pk + s1.step, ok + s2.step
            diverging += (a != b)
        print(f"{kad}  {ad}  {diverging:8d}  {pk:5d}  {ok:5d}  {ok / pk:5.2f}")

corpus: 40 arrays x 12 values | examples:
  arrangement : [5, 9, 3, 4, 7, 10, 1, 12, 11, 2, 6, 8]
  duplicates  : [3, 4, 1, 2, 3, 4, 5, 6, 7, 12, 9, 2]
  out_of_range: [5, 9, 3, 4, 7, 18, 1, 12, 11, 2, 6, 16]

pattern    pool                  diverging/40  pattern  oracle   ratio
plain      1..n arrangement            0    826   2640   3.20
plain      duplicate values           40  16040   2640   0.16
plain      out-of-range values        40    801   2640   3.30
guarded    1..n arrangement            0    826   2640   3.20
guarded    duplicate values           39    750   2640   3.52
guarded    out-of-range values        40    801   2640   3.30

The first row is the pattern’s promise: the same arrangement as the oracle on 40 of 40 inputs, 826 steps against 2640, a ratio of 3.20. The result is correct even though no comparison is ever performed.

The second row carries this topic’s most extreme result. On duplicate values, the plain pattern spends 16,040 steps and the ratio drops to 0.16 — six times more expensive than the oracle. This number is not a slowdown, it is a measure of not stopping: all forty of the forty inputs hit the 400-step cap. Without the cap, the measurement would have finished on the first input and no result would ever have come out.

The third row shows an entirely different defect. On out-of-range values, the pattern finishes in 801 steps, ratio 3.30 — even faster than the first row — and wrong on 40 of 40 inputs. An out-of-range value has no home; the pattern leaves it where it is and moves on, and the resulting arrangement differs from the oracle’s. There is no warning, no delay, no sign at all.

The Guard Fixes Not Stopping, Not the Wrongness

The change that stops the infinite swap is a single comparison: before sending a value home, check whether the same value is already there. If it is, sending it home is pointless and the position advances instead.

def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def value_corpus(seed, n=40, length=12):
    r = generator(seed)
    items = []
    for i in range(n):
        arrangement = list(range(1, length + 1))
        for j in range(length, 1, -1):
            k = r(j)
            arrangement[j - 1], arrangement[k] = arrangement[k], arrangement[j - 1]
        duplicates = [r(length) + 1 for _ in range(length)]
        out_of_range = list(arrangement)
        for _ in range(2):
            out_of_range[r(length)] = length + 2 + r(length)
        items.append({"arrangement": arrangement, "duplicates": duplicates,
                     "out_of_range": out_of_range})
    return items


def oracle_arrangement(array):
    a = list(array)
    for i in range(len(a)):
        least = i
        for j in range(i + 1, len(a)):
            if a[j] < a[least]:
                least = j
        a[i], a[least] = a[least], a[i]
    return a


def pattern(array, guard, cap=400):
    a, n, i, step = list(array), len(array), 0, 0
    while i < n:
        step += 1
        if step > cap:
            return "did not stop"
        home = a[i] - 1
        if 0 <= home < n and ((a[i] != a[home]) if guard else (home != i)):
            a[i], a[home] = a[home], a[i]
        else:
            i += 1
    return a


example = value_corpus(20260218)[0]
print("duplicate input:", example["duplicates"])
print("  plain pattern  :", pattern(example["duplicates"], False))
print("  guarded pattern:", pattern(example["duplicates"], True))
print("  oracle         :", oracle_arrangement(example["duplicates"]))
print()
print("seed       pattern   pool        diverging/40   ratio")
for seed in (20260218, 20260219):
    K = value_corpus(seed)
    for kad, guard in (("plain   ", False), ("guarded ", True)):
        for key in ("arrangement", "duplicates", "out_of_range"):
            diverging = sum(1 for k in K
                            if pattern(k[key], guard) != oracle_arrangement(k[key]))
            print(f"{seed}  {kad}  {key:12s}  {diverging:8d}   {diverging / 40:.4f}")

duplicate input: [3, 4, 1, 2, 3, 4, 5, 6, 7, 12, 9, 2]
  plain pattern  : did not stop
  guarded pattern: [1, 2, 3, 4, 5, 6, 7, 4, 9, 2, 3, 12]
  oracle         : [1, 2, 2, 3, 3, 4, 4, 5, 6, 7, 9, 12]

seed       pattern   pool        diverging/40   ratio
20260218  plain     arrangement          0   0.0000
20260218  plain     duplicates          40   1.0000
20260218  plain     out_of_range        40   1.0000
20260218  guarded   arrangement          0   0.0000
20260218  guarded   duplicates          39   0.9750
20260218  guarded   out_of_range        40   1.0000
20260219  plain     arrangement          0   0.0000
20260219  plain     duplicates          40   1.0000
20260219  plain     out_of_range        39   0.9750
20260219  guarded   arrangement          0   0.0000
20260219  guarded   duplicates          40   1.0000
20260219  guarded   out_of_range        39   0.9750

The example input shows the mechanism plainly. The plain pattern returns did not stop. The guarded pattern stops and produces [1, 2, 3, 4, 5, 6, 7, 4, 9, 2, 3, 12]; the oracle’s answer is [1, 2, 2, 3, 3, 4, 4, 5, 6, 7, 9, 12]. They are not the same — the guard fixed not stopping, it did not fix the wrongness. Diverging inputs dropped from 40 to 39, which by the resolution rule is not even a measured difference, because it stays at the same order of magnitude.

PP36. The second corpus comes from seed 20260219. In twelve of twelve rows, diverging inputs are either 0 or 39–40; the result does not depend on the corpus. PP37. A gap between 39 and 40 in 40 inputs counts as unmeasured; the swaps between the two corpora (39/40 on duplicates, 40/39 on out-of-range) are therefore not a trend.

The Precondition Belongs Not to the Pattern but to the Pattern-Question Pair

So far only one question has been asked: what will the arrangement itself be. The same pattern, with the same broken inputs, can also be used to answer a different question: which values from 1..n are missing. Here the pattern uses the arrangement not as a goal but as an intermediate product; positions that are not home directly give the missing values.

PP38. In this measurement the pattern is the guarded form, and the answer is the list of positions not at home. The oracle searches for each value by scanning the array. PP39. The question changed; the pattern, oracle, corpus, and seed did not.

def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def value_corpus(seed, n=40, length=12):
    r = generator(seed)
    items = []
    for i in range(n):
        arrangement = list(range(1, length + 1))
        for j in range(length, 1, -1):
            k = r(j)
            arrangement[j - 1], arrangement[k] = arrangement[k], arrangement[j - 1]
        duplicates = [r(length) + 1 for _ in range(length)]
        out_of_range = list(arrangement)
        for _ in range(2):
            out_of_range[r(length)] = length + 2 + r(length)
        items.append({"arrangement": arrangement, "duplicates": duplicates,
                     "out_of_range": out_of_range})
    return items


class Counter:
    def __init__(self):
        self.step = 0

    def count(self):
        self.step += 1


def oracle_missing(array, s):
    """Searches for every value in 1..n by scanning the array."""
    missing = []
    for v in range(1, len(array) + 1):
        found = False
        for x in array:
            s.count()
            if x == v:
                found = True
                break
        if not found:
            missing.append(v)
    return missing


def pattern_missing(array, s, cap=400):
    """First places, then collects the positions not at home."""
    a, n = list(array), len(array)
    i = 0
    while i < n:
        s.count()
        if s.step > cap:
            return "did not stop"
        home = a[i] - 1
        if 0 <= home < n and a[i] != a[home]:
            a[i], a[home] = a[home], a[i]
        else:
            i += 1
    missing = []
    for j in range(n):
        s.count()
        if a[j] != j + 1:
            missing.append(j + 1)
    return missing


print("seed       pool        diverging/40  pattern  oracle   ratio")
for seed in (20260218, 20260219):
    K = value_corpus(seed)
    for key in ("arrangement", "duplicates", "out_of_range"):
        diverging, pk, ok = 0, 0, 0
        for k in K:
            s1, s2 = Counter(), Counter()
            a = pattern_missing(k[key], s1)
            b = oracle_missing(k[key], s2)
            pk, ok = pk + s1.step, ok + s2.step
            diverging += (a != b)
        print(f"{seed}  {key:12s}  {diverging:8d}  {pk:5d}  {ok:5d}"
              f"  {ok / pk:5.2f}")
print()
K = value_corpus(20260218)
print("out-of-range example array:", K[0]["out_of_range"])
print("  pattern missing:", pattern_missing(K[0]["out_of_range"], Counter()))
print("  oracle missing :", oracle_missing(K[0]["out_of_range"], Counter()))

seed       pool        diverging/40  pattern  oracle   ratio
20260218  arrangement          0   1306   3120   2.39
20260218  duplicates           0   1230   3531   2.87
20260218  out_of_range         0   1281   3536   2.76
20260219  arrangement          0   1313   3120   2.38
20260219  duplicates           0   1233   3525   2.86
20260219  out_of_range         0   1294   3548   2.74

out-of-range example array: [5, 9, 3, 4, 7, 18, 1, 12, 11, 2, 6, 16]
  pattern missing: [8, 10]
  oracle missing : [8, 10]

Six of six rows give diverging inputs of zero. The same pattern, the same duplicate and out-of-range inputs, two corpora — and no divergence at all. The rows that read 39 and 40 in the previous table read 0 here.

The only thing that changed is the question. “What will the arrangement be” requires every value in the array to have a home; “which values are missing” does not, because a homeless value’s position does not affect the answer. The pattern’s precondition lies not in the pattern’s own code, but in which question the pattern is answering.

The rule that follows from this holds for the entire topic: a pattern’s precondition is not defined when the pattern’s name is asked, it is defined once the question asked is fixed. The sentence “cyclic sort does not work with duplicate values” is false in this table; the correct sentence is “cyclic sort does not give the correct answer to the arrangement question with duplicate values.”

Three Numbers

Metric	Oracle	Pattern	Diverging input
Arrangement, 1..n values	2640 steps	826 steps	0/40
Arrangement, duplicates, plain pattern	2640 steps	16,040 steps	40/40
Arrangement, duplicates, guarded pattern	2640 steps	750 steps	39/40
Arrangement, out-of-range	2640 steps	801 steps	40/40
Missing value, out-of-range	3536 steps	1281 steps	0/40

The second row is a measure of not stopping, the third row of silent wrongness, the fifth row of the question changing. In none of the five rows can the correct rows be picked out by looking at the step column.

Summary

• Cyclic sort performs no comparison at all; it sends every value straight to position v-1, and total swaps never exceed n.
• The pattern has two separate preconditions, and their breakdowns lead to separate consequences: duplicate values lead to not stopping, out-of-range values lead to silent wrongness.
• On duplicate input, the plain pattern hits the step cap on 40 of 40 inputs and the ratio drops to 0.16; on out-of-range input it finishes in 801 steps and is wrong on 40 of 40.
• The duplicate guard removes not stopping but drops diverging inputs on the arrangement question only from 40 to 39.
• When the same pattern answers “which values are missing,” diverging inputs are zero on six of six measurements; the precondition belongs not to the pattern but to the pattern-question pair.

Next Step

The five patterns so far held the entire input in hand: the array could be seen start to end, revisited at any position. The next pattern loses that ability. Values flow one at a time, and after each new value a question must be answered: what is the median of what has been seen so far. The pattern holds two heaps, and its precondition is that these two heaps stay balanced. The next lesson will count how many wrong medians appear at how many steps once that balance breaks.