Sorting algorithms
Введено| English | Значение |
|---|---|
| bubble sort/ˈbʌbl sɔːt/ | сортировка пузырьком |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | сортировка вставками |
| in place/ɪn pleɪs/ | на месте |
| stable/ˈsteɪbl/ | устойчивая |
Сортировка, которая медленна специально
- Каждая серьезная библиотека использует алгоритм сортировки, который не требуется писать на экзамене. Пузырьковая и вставочная сортировки — обе $O(n^2)$, и любая нормальная сортировка превосходит их на большом списке.
- Они есть в программе всё равно, и на то есть веская причина: они достаточно коротки, чтобы проследить вручную, и прослеживание одной из них — это способ понять, что сортировка на самом деле делает с массивом.
- Также существует реальный случай для вставочной сортировки. На маленьком списке или почти отсортированном списке она действительно самая быстрая, и реальные библиотеки переключаются на неё именно для таких случаев.
- Этот урок посвящён пузырьковой сортировке и вставочной сортировке: алгоритмам, их поведению и тому, где каждый из них побеждает.
Сортировка пузырьком
FOR pass ← 1 TO n - 1
swapped ← FALSE
FOR i ← 1 TO n - pass
IF A[i] > A[i + 1] THEN
swap A[i], A[i + 1]
swapped ← TRUE
ENDIF
NEXT i
IF NOT swapped THEN // already sorted
EXIT FOR
ENDIF
NEXT pass
- Каждый проход сравнивает соседние пары и меняет местами любые, которые не упорядочены, так что наибольшее оставшееся значение «всплывает» в конец.
- После прохода $k$ последние $k$ элементов окончательны, поэтому внутренний цикл останавливается на $n - \text{pass}$.
- Флаг
swappedпозволяет ему остановиться раньше: если весь проход не содержит обменов, список уже отсортирован.
Вставочная сортировка
FOR i ← 2 TO n
key ← A[i]
j ← i - 1
WHILE j >= 1 AND A[j] > key DO
A[j + 1] ← A[j] // shift right
j ← j - 1
ENDWHILE
A[j + 1] ← key // drop it in
NEXT i
- Она формирует отсортированную секцию спереди, увеличивая её на один элемент за раз. Каждый новый элемент временно выдерживается как
key, большие элементы сдвигаются вправо, чтобы освободить место, и ключ вставляется. - Так большинство людей сортируют колоду игральных карт, что и ожидается на экзамене.

Слева отсортировано, справа нет трогали, граница движется вправо
Алгоритмы сортировки
compare adjacent, swap if needed
Step through a bubble sort: each pass floats the largest value to the end.
Bubble sort works by:
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Each pass swaps adjacent pairs, "bubbling" the largest element to the end.
The average/worst-case time complexity of bubble sort is:
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Two nested loops over n elements give O(n²); the best case (already sorted) is O(n) with the early exit.
Разбор примера: проследите один проход
- Проследите первый проход пузырьковой сортировки на 5, 3, 8, 1.
- Сравните 5 и 3: неупорядочено, обмен, получаем 3, 5, 8, 1. Сравните 5 и 8: упорядочено, обмена нет. Сравните 8 и 1: обмен, получаем 3, 5, 1, 8.
- После одного прохода наибольшее значение, 8, находится на своём финальном месте, и с этого момента можно пропускать одно сравнение на каждый проход.
- Теперь проследите третий шаг вставочной сортировки на 3, 5, 8, 1. Ключ равен 1. Сдвиньте 8, 5 и 3 каждое на одну позицию вправо, затем поместите 1 в начало: 1, 3, 5, 8. Покажите массив после каждого шага; там находятся баллы.
Insertion sort builds the sorted result by:
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
It grows a sorted prefix on the left, shifting larger elements right to drop each key into place.
How does insertion sort place each new element?
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Holding the key aside and shifting is what distinguishes it from bubble sort's repeated adjacent swaps.
Производительность
| пузырьковая | вставочная | |
|---|---|---|
| лучший случай | $O(n)$, один проход без обменов | $O(n)$, уже отсортирована, нет сдвигов |
| средний и худший | $O(n^2)$ | $O(n^2)$ |
| дополнительная память | $O(1)$, in place (на месте) | $O(1)$, in place (на месте) |
| стабильная | да | да, стабильная |
- In place означает, что требуется только постоянный объём дополнительной памяти, сортировка происходит внутри самого массива. Стабильная означает, что два равных значения сохраняют свой исходный относительный порядок, что важно, когда список уже был отсортирован по другому полю.
- Оба достигают $O(n)$ на уже отсортированных данных, но только если сортировка пузырьком имеет флаг
swapped. Без него она всегда выполняет каждый проход.
After the first pass of a bubble sort on 5, 3, 8, 1, what is the array? Write the four numbers separated by commas.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
5 and 3 swap, 5 and 8 do not, 8 and 1 swap. The largest value has reached the end, so the next pass can be one comparison shorter.
Разбор примера: какая сортировка и почему
- Список из 200,000 записей должен быть отсортирован с нуля. Ни то, ни другое: оба являются $O(n^2)$, поэтому требуется слияние или быстрая сортировка на $O(n \log n)$. Укажите это вместо выбора наименее плохого варианта.
- Отсортированный список из 10,000 получает 5 новых записей в конце и должен быть отсортирован снова. Сортировка вставками: данные почти отсортированы, поэтому каждый новый ключ сдвигается лишь на короткое расстояние, и алгоритм приближается к $O(n)$.
- Учебный пример должен быть прослежен вручную на бумаге. Пузырьковая сортировка: её проще всего проследить, что является её настоящим оставшимся применением.
- Обоснуйте, исходя из состояния данных и размера, а не из общих предпочтений.
Match each sorting idea to what it means.
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
Bubble swaps neighbours, insertion grows a sorted prefix; both are O(n²) worst-case; stability is about equal-key order.
Insertion sort runs close to O(n) on small or nearly-sorted arrays, because few elements need to be shifted.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
On nearly-sorted data each new item is already almost in place — which is why insertion sort beats fancier sorts on small inputs.
Which are true of both bubble sort and insertion sort? Select все that apply.
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
On a large unsorted list an O(n log n) sort wins decisively. Saying so is the right answer, not choosing the least bad of the two.
Почему одного прохода недостаточно
- Обе сортировки выполняют многократные проходы, и экзамен различает их по тому, чего достигает один проход и когда они останавливаются.
- Проход пузырьковой сортировки сравнивает соседние пары и меняет их местами, поэтому один переносит наибольшее оставшееся значение на своё финальное место. Вся сортировка занимает $n - 1$ проходов.
- Проход вставочной сортировки берёт следующий элемент и возвращает его обратно в уже отсортированную часть, поэтому после $k$ проходов первые $k$ элементов отсортированы между собой, но ещё не на финальных позициях.
- Пузырьковую сортировку можно улучшить с помощью флага: если проход не совершает обменов, список уже отсортирован, и алгоритм останавливается. На почти отсортированных данных это превращает её в один проход.
- Без флага обе являются $n^2$ в худшем случае, поэтому либо является плохим выбором для большого файла, и поэтому экзамен спрашивает о маленьких.
A sorted list of 10,000 records gains 5 new records at the end. Which sort suits re-sorting it?
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Nearly sorted data is exactly insertion sort's best case, approaching O(n). Real libraries switch to it for this reason.
Match each sort to what one pass achieves.
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
That difference is what a trace question is really testing. A bubble-sort flag also lets it stop early on nearly-sorted data, which insertion sort handles well anyway.
Потерянные баллы
- Пузырьковая сортировка сравнивает соседние пары. Ответ, в котором элемент сравнивается со всеми остальными, описывает другой алгоритм.
- Внутренний цикл сокращается с каждой итерацией, потому что конец массива уже отсортирован. Объясните почему.
- Сортировка вставками сдвигает элементы вправо, чтобы освободить место; она не выполняет многократных обменов. Разница между этими подходами является сутью алгоритма.
- Оба алгоритма имеют сложность $O(n^2)$ в среднем и в худшем случае, и $O(n)$ в лучшем. Укажите случай для каждого порядка.
Вы поняли
- Пузырьковая сортировка: многократные проходы, сравнивающие смежные пары элементов и выполняющие обмен, при этом максимальный элемент «всплывает» к концу, внутренний цикл сокращается с каждым проходом, используется флаг
swappedдля раннего выхода. - Сортировка вставками: формирование отсортированной секции спереди, временное хранение текущего элемента, сдвиг больших элементов вправо и установка ключа на освободившееся место.
- Оба алгоритма имеют сложность $O(n^2)$ в среднем и худшем случае, $O(n)$ в лучшем, работают на месте и являются устойчивыми.
- Сортировка вставками действительно выигрывает на малых или почти отсортированных списках; для большого неотсортированного списка ни один из них не подходит.