Week 13 — Sorting: count the work and preserve the meaning

The big question

How can several correct ways to sort the same values require different amounts of work? Sorting is a useful place to connect traces, exact counts, growth classes, memory, and measurement. The slow sorts are learning tools. Python's built-in sorting is the practical baseline in the original lesson.

Your outcomes are to trace bubble and selection sort accurately, explain insertion sort's sensitivity to existing order, derive triangular comparison counts, and interpret O(n log n) as repeated levels of linear work. You should also distinguish a new sorted list from mutation of an existing list and preserve the intended ordering of tied records.

Türkçe: Bütün yöntemlerin sonunda aynı sıralı listeye ulaşması, aynı işi yaptıkları anlamına gelmez. Karşılaştırma, takas ve kaydırma sayılarını ayrı ayrı sayacağız. “Hızlı” kararını da yalnızca küçük bir örneğe veya tek bir süreye bağlamayacağız.

Prerequisite warm-up, with answers

How many adjacent pairs exist in five items? Add 4 + 3 + 2 + 1. If doubling input changes modeled time from n² to (2n)², what happens to the time?

Answers: There are four adjacent pairs, because the final item has no next neighbor. The sum is ten. Expanding (2n)² = (2n)(2n) = 4n² gives four times the leading quadratic term. An exact count containing both n² and n terms need not increase by exactly four.

Remember that a comparison asks a question such as “is the left value greater?” A swap changes two positions. A comparison may produce no swap, so these counters must not be treated as identical.

Worked example 1 — Bubble sort, one pass at a time

Use the actual lesson input [5, 1, 4, 2, 8]. Bubble sort compares adjacent values and swaps out-of-order neighbors. After one pass, the largest value in the unsorted region is at its right end. That final position no longer needs checking in later passes.

During pass one, compare 5 with 1 and swap: [1, 5, 4, 2, 8]. Compare 5 with 4 and swap: [1, 4, 5, 2, 8]. Compare 5 with 2 and swap: [1, 4, 2, 5, 8]. Compare 5 with 8 and leave them alone. Four comparisons, three swaps.

The third pass makes no swaps. Every adjacent pair it checks is in order, and the previously completed suffix is already correct. The early-exit flag therefore stops the algorithm. Total comparisons are 4 + 3 + 2 = 9; total swaps are 3 + 1 + 0 = 4. Although the list became sorted after pass two, the algorithm needs the clean pass to discover that it can stop.

def bubble_sort(data):
    items = data[:]
    comparisons = swaps = 0
    for end in range(len(items) - 1, 0, -1):
        swapped = False
        for i in range(end):
            comparisons += 1
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]
                swaps += 1
                swapped = True
        if not swapped:
            break
    return items, comparisons, swaps

assert bubble_sort([5, 1, 4, 2, 8]) == ([1, 2, 4, 5, 8], 9, 4)
assert bubble_sort([]) == ([], 0, 0)
print(bubble_sort([3, 2, 1]))

The printed result is ([1, 2, 3], 3, 3). The initial slice protects the caller's input, but it costs O(n) time and O(n) additional space. A function that sorts a copy is not an O(1)-extra-space implementation merely because its swap operation uses constant storage.

Türkçe: Liste ikinci tur sonunda sıralandı; fakat program bunu henüz kesin olarak bilmiyor. Üçüncü turdaki “hiç takas yok” bilgisi durma gerekçesidir. Kağıt üzerinde sonucu görmemiz ile algoritmanın durma koşuluna ulaşması aynı an olmak zorunda değildir.

Worked example 2 — Selection sort makes a different promise

Selection sort repeatedly finds the smallest value in the remaining suffix and puts it at the next final position. It cannot stop examining a suffix merely because the values inspected so far look sorted: a smaller value might still be near the end.

This gives ten comparisons and two swaps. The fact that the list becomes sorted early does not remove the later scans from this implementation.

def selection_sort(data):
    items = data[:]
    comparisons = swaps = 0
    for start in range(len(items)):
        smallest = start
        for i in range(start + 1, len(items)):
            comparisons += 1
            if items[i] < items[smallest]:
                smallest = i
        if smallest != start:
            items[start], items[smallest] = items[smallest], items[start]
            swaps += 1
    return items, comparisons, swaps

assert selection_sort([5, 1, 4, 2, 8]) == ([1, 2, 4, 5, 8], 10, 2)
assert selection_sort([1, 2, 3]) == ([1, 2, 3], 3, 0)
print(selection_sort([2, 1]))

The printed result is ([1, 2], 1, 1). At most one swap happens for each of the first n − 1 positions, so at most n − 1 swaps occur. Comparison count is still quadratic. Fewer swaps may improve a measured constant without changing that growth class.

Slow concept — Derive the exact count before simplifying

Selection sort's comparisons are (n − 1) + (n − 2) + ... + 1. Let the sum be S. Write the terms in reverse order beneath them. Each column adds to n; there are n − 1 columns. Therefore 2S = n(n − 1), and S = n(n − 1)/2.

For n = 2,000, S = 2,000 × 1,999 / 2 = 1,999,000. For n = 4,000, S = 4,000 × 3,999 / 2 = 7,998,000. The ratio is approximately 4.001, not exactly four. The dominant n² term explains O(n²), while the exact expression explains the slightly different ratio.

For the bubble implementation, the same sum is its full-pass worst-case count, not a mandatory count for every input. On an already sorted list of n ≥ 2 items, it performs n − 1 comparisons, zero swaps, and exits. A strictly descending list requires every comparison and swap. Random input often requires nearly all passes, but the precise count depends on the actual permutation.

Türkçe: Seçmeli sıralamada üçgen toplam her girdide geçerlidir. Erken durmalı kabarcık sıralamasında ise bu toplam en kötü durum içindir. Aynı formülü kullanırken “hangi algoritma, hangi girdi, hangi durum?” sorularını belirtmek gerekir.

Insertion sort and existing order

Insertion sort maintains a sorted prefix. Take the next value, shift larger prefix values right, and place the held value into the gap. On the same five-item example, inserting 1 requires one comparison and one shift. Inserting 4 requires two comparisons and one shift. Inserting 2 requires three comparisons and two shifts. Inserting 8 requires one comparison and no shift. Totals are seven comparisons and four shifts, matching the original lesson's counting convention.

On already sorted input, each new item needs one comparison: n − 1 comparisons. On strictly reverse-sorted input, all earlier items shift, giving the triangular sum. Thus insertion sort is O(n) in its best case and O(n²) in its worst case. All three lesson functions copy their input first and therefore use O(n) extra space; their in-place cores can use O(1) auxiliary space.

Why n log n appears, and what sorted() guarantees

Imagine splitting eight items until single items remain. There are three splitting levels because 8 = 2³. When combining sorted pieces, each merge level processes eight items in total: first four two-item merges, then two four-item merges, then one eight-item merge. The work model is 8 + 8 + 8 = 8 × 3 = 24. This is an illustration of total processing, not an exact claim of 24 key comparisons.

In general, about log₂ n levels each perform O(n) work, yielding O(n log n). On doubling n, the leading work ratio is 2(log₂ n + 1)/log₂ n. At n = 1,024, it is 2 × 11 / 10 = 2.2. The ratio changes slowly with size; 2.1 or 2.2 is not a universal constant.

Python's built-in sorting is adaptive: it can exploit existing order. It has O(n log n) worst-case comparison-sort behavior and can be linear on already ordered data. sorted(data) returns a new list. data.sort() modifies the existing list and returns None. In-place modification does not promise zero workspace; built-in list sorting may use O(n) auxiliary storage.

A stable sort preserves relative order among records with equal keys. It does not mean equally valued records remain at their original absolute indices. reverse=True also preserves tie order. See the official sorting guide for the language guarantees.

Three graduated practice problems

Problem 1 — Best versus worst

For six distinct items, give bubble sort's comparisons and swaps on sorted and reverse-sorted input. Give selection sort's comparisons in both cases. Use the implementations above.

Solution 1 — Use the stopping rules

Sorted bubble input uses 6 − 1 = 5 comparisons and zero swaps. Reverse-sorted bubble input uses 6 × 5 / 2 = 15 comparisons and 15 swaps. Selection sort always uses 15 comparisons here, including on sorted input; its sorted case makes zero swaps. Do not assign selection sort 15 swaps merely because it makes 15 comparisons.

Problem 2 — Preserve ties, then deliberately break them

Records arrive as [("Cem", 88), ("Ada", 88), ("Ece", 72)]. Sort by descending grade while preserving arrival order for ties. Then sort by descending grade and ascending name. Explain the difference.

Solution 2 — Define the full key

records = [("Cem", 88), ("Ada", 88), ("Ece", 72)]
by_grade = sorted(records, key=lambda item: item[1], reverse=True)
by_grade_name = sorted(records, key=lambda item: (-item[1], item[0]))
assert by_grade == [("Cem", 88), ("Ada", 88), ("Ece", 72)]
assert by_grade_name == [("Ada", 88), ("Cem", 88), ("Ece", 72)]
print(by_grade_name)

In the first result, Cem stays before Ada because their keys are equal. In the second, negated numeric grade sorts larger grades first; name breaks the tie alphabetically. A tuple can express these mixed directions for a numeric grade. Two stable passes are another valid option, beginning with the less important key. The original records remain unchanged because both calls use sorted.

Problem 3 — Predict without pretending to measure

Suppose a repeated benchmark gives 0.20 seconds for bubble sort at n = 2,000 and 0.80 seconds at n = 4,000 on comparable difficult inputs. Predict at n = 8,000. Explain what a fair comparison with sorted() needs.

Solution 3 — State the model and its limits

The observed doubling ratio is 0.80 / 0.20 = 4. Under the same quadratic-dominant model, predict 0.80 × 4 = 3.20 seconds at 8,000. This is a prediction, not an observed runtime, and it assumes similar input structure and operating conditions.

Give both sorts identical input values, fresh inputs when mutation matters, and equivalent output requirements. Build test data outside the timed region. Repeat runs and report the chosen summary. Include copying consistently: the lesson's bubble function already copies internally. Check equality with a trusted sorted result outside timing. Benchmark multiple input patterns because already sorted data activates early exits and adaptive behavior.

Misconceptions and a short bridge to the chapter puzzle

Do not infer “quadratic” from any two nested loops without counting their bounds. Do not infer a proof from near-four timing ratios. Do not replace data with data.sort(), because the assigned result is None. Do not call every in-place operation constant-space.

The optional triangle puzzle uses the same “count contributions” habit. Row sums are 1, 3, 9, 27. Every entry contributes to exactly three positions in the next row, so each new total is three times the previous total. Row i therefore sums to 3 raised to the power i − 1. The explanation establishes the general pattern; the four observed totals alone do not.

You are ready when you can reproduce 9/4 for bubble and 10/2 for selection, derive the triangular count, and explain a stable tie. Repair counting gaps with three items before returning to five. Repair complexity gaps by naming the input case explicitly. Bring these habits to Week 14, where two correct approaches become a complete, evidence-based recommendation.

Put one more item in its final place

Selection sort finds the smallest item in the part that is still unsorted. It puts that item in the next position at the front. The finished part grows by one item each round. This explains why the answer is sorted. Counting comparisons answers a separate question: how much work was needed?

Draw or trace. Trace [4, 1, 3, 2] with a boundary between finished front part and unfinished remaining part. Record comparisons for each minimum search.

Predict before checking. If the list is already sorted, does this ordinary selection-sort version avoid the minimum searches?

Worked reasoning

No. This version still makes 3, 2 and 1 comparisons: six for four items. For n items it makes n(n − 1)/2 comparisons, whatever the starting order. A bubble sort that stops when no swaps occur behaves differently, so name the version you are analysing. Also check what happens to equal values. A stable sort keeps equal-value records in their original order; not every sort does.

values = [4, 1, 3, 2]
comparisons = 0
for start in range(len(values) - 1):
    smallest = start
    for index in range(start + 1, len(values)):
        comparisons += 1
        if values[index] < values[smallest]:
            smallest = index
    values[start], values[smallest] = values[smallest], values[start]
assert values == [1, 2, 3, 4]
assert comparisons == 6
print(values, comparisons)

Change one thing. Add record labels to equal sorting values. Inspect whether swapping a later minimum across an record with the same sorting value changes their order, even though the key values finish sorted.

Türkçe: Doğruluk için her turda kesinleşen bölgeyi açıkla; maliyet için karşılaştırmaları say. Sıralı girdi her algoritmada daha az iş demek değildir.

Additional analysis laboratory

Sorting connects correctness, stability, and cost. A sort is not only "put items in order"; it must say which key defines order and what happens to ties.

Extra exam-style prompt: Sort student records by grade descending, preserving original order among equal grades. What must the contract say?

Solution: The key is grade, the direction is descending, and ties must keep input order. A stable sort with key grade and reverse order satisfies the tie requirement. If ties may be reordered, the output contract is different. Analysis should include key computation cost if it is expensive.

Turkce: Siralama kuralini tam soyle: hangi alana gore, artan mi azalan mi, esitlikte ne olacak? Bu ayrinti hem dogrulugu hem maliyeti etkileyebilir.