Сортировка
Введено| English | Значение |
|---|---|
| insertion sort/ɪnˈsɜːʃn sɔːt/ | A sorting method that inserts each new item into its correct position in the already sorted part of a list. |
| merge sort/mɜːdʒ sɔːt/ | Sorting by recursively sorting parts and merging the sorted parts. |
| inversion/ɪnˈvɜːʃn/ | A pair of sequence positions whose values occur in the opposite order to the desired sorted order. |
The course dataset
- Sort $[5, 2, 9, 1, 7, 3]$. Insertion sort grows a sorted prefix, sliding each new card back; merge sort halves, sorts each half, merges; quicksort partitions around a pivot; bubble sort swaps adjacent inversions — educational, rarely used.
{exercise:uni-cs0506-families}
Any sort that only swaps adjacent pairs makes, on a dataset, exactly — swaps
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Each adjacent swap fixes exactly one inversion — the count is the bill.
The inversion count
- An inversion is one out-of-order pair; the course dataset has $8$: $(5,2), (5,1), (5,3), (2,1), (9,1), (9,7), (9,3), (7,3)$. Every adjacent swap fixes exactly one, so any swap-adjacent sort makes exactly $8$ swaps here — and insertion sort's shifts equal the inversions.
- Merge sort counts the same inversions across its merges while moving each element at most $\log_2 6 \approx 2.6$ levels: it fixes many inversions per move, which is the whole $O(n \log n)$ vs $O(n^2)$ story.
{exercise:uni-cs0506-inversions}
The dataset [5, 2, 9, 1, 7, 3] has — inversions
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Count the out-of-order pairs: (5,2), (5,1), (5,3), (2,1), (9,1), (9,7), (9,3), (7,3).
Both by hand
- Insertion: $2$ shifts one; $9$ none; $1$ three; $7$ one; $3$ three — total $8$ shifts, $11$ comparisons, result $[1, 2, 3, 5, 7, 9]$.
- Merge: halve to $[5, 2, 9]$ and $[1, 7, 3]$; recursively $[2, 5, 9]$ and $[1, 3, 7]$; merge once: $1, 2, 3, 5, 7, 9$ with $10$ comparisons. At $n = 1000$ the families divide by $100$.
Sorted input with a first-element pivot is quicksort's worst case, $O(n^2)$ — not a rarity but a trap. Stability survives in merge and insertion, not in quick or heap.
{exercise:uni-cs0506-trace}
Merge sort on the same dataset uses — comparisons
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Measured: 10 comparisons against insertion 11 — and the gap widens with size.