Алгоритмы сортировки
| 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, большие элементы сдвигаются вправо, чтобы освободить место, и ключ вставляется. - Так большинство людей сортируют колоду игральных карт, что и ожидается на экзамене.
Слева отсортировано, справа нет трогали, граница движется вправо
Алгоритмы сортировки
сравнивают соседние элементы, меняют местами при необходимости
Продемонстрируйте пузырьковую сортировку: каждый проход выталкивает наибольшее значение в конец.
Пузырьковая сортировка работает путем:
Каждый проход меняет местами соседние пары, «всплывая» наибольший элемент в конец.
Средняя/худшая сложность по времени пузырьковой сортировки составляет:
Два вложенных цикла по n элементам дают O(n²); лучший случай (уже отсортировано) — O(n) с ранним выходом.
Разбор примера: проследите один проход
- Проследите первый проход пузырьковой сортировки на 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. Покажите массив после каждого шага; там находятся баллы.
Сортировка вставками строит отсортированный результат путем:
Она наращивает отсортированный префикс слева, сдвигая большие элементы вправо, чтобы поместить каждый ключ на свое место.
Как сортировка вставками размещает каждый новый элемент?
Удержание ключа в стороне и сдвиг — это то, что отличает её от многократных соседних обменов пузырьковой сортировки.
Производительность
| пузырьковая | вставочная | |
|---|---|---|
| лучший случай | $O(n)$, один проход без обменов | $O(n)$, уже отсортирована, нет сдвигов |
| средний и худший | $O(n^2)$ | $O(n^2)$ |
| дополнительная память | $O(1)$, in place (на месте) | $O(1)$, in place (на месте) |
| стабильная | да | да, стабильная |
- In place означает, что требуется только постоянный объём дополнительной памяти, сортировка происходит внутри самого массива. Стабильная означает, что два равных значения сохраняют свой исходный относительный порядок, что важно, когда список уже был отсортирован по другому полю.
- Оба достигают $O(n)$ на уже отсортированных данных, но только если сортировка пузырьком имеет флаг
swapped. Без него она всегда выполняет каждый проход.
После первого прохода пузырьковой сортировки над 5, 3, 8, 1, каков будет массив? Запишите четыре числа через запятую.
5 и 3 меняются местами, 5 и 8 не меняются, 8 и 1 меняются местами. Наибольшее значение достигло конца, поэтому следующий проход может быть короче на одно сравнение.
Разбор примера: какая сортировка и почему
- Список из 200,000 записей должен быть отсортирован с нуля. Ни то, ни другое: оба являются $O(n^2)$, поэтому требуется слияние или быстрая сортировка на $O(n \log n)$. Укажите это вместо выбора наименее плохого варианта.
- Отсортированный список из 10,000 получает 5 новых записей в конце и должен быть отсортирован снова. Сортировка вставками: данные почти отсортированы, поэтому каждый новый ключ сдвигается лишь на короткое расстояние, и алгоритм приближается к $O(n)$.
- Учебный пример должен быть прослежен вручную на бумаге. Пузырьковая сортировка: её проще всего проследить, что является её настоящим оставшимся применением.
- Обоснуйте, исходя из состояния данных и размера, а не из общих предпочтений.
Соотнесите каждую идею сортировки с её значением.
Пузырьковая сортировка меняет соседей, сортировка вставками наращивает отсортированный префикс; обе имеют худшую сложность O(n²); стабильность касается порядка равных ключей.
Сортировка вставками работает близко к O(n) на малых или почти отсортированных массивах, так как малому числу элементов нужно делать сдвиги.
На почти отсортированных данных каждый новый элемент уже почти на своем месте — именно поэтому сортировка вставками превосходит более сложные методы на малых входных данных.
Что верно для обеих: пузырьковой сортировки и сортировки вставками? Выберите все подходящие варианты.
На большом не отсортированном списке O(n log n) сортировка побеждает решительно. Утверждение этого является правильным ответом, а не выбором наименее плохого из двух вариантов.
Почему одного прохода недостаточно
- Обе сортировки выполняют многократные проходы, и экзамен различает их по тому, чего достигает один проход и когда они останавливаются.
- Проход пузырьковой сортировки сравнивает соседние пары и меняет их местами, поэтому один переносит наибольшее оставшееся значение на своё финальное место. Вся сортировка занимает $n - 1$ проходов.
- Проход вставочной сортировки берёт следующий элемент и возвращает его обратно в уже отсортированную часть, поэтому после $k$ проходов первые $k$ элементов отсортированы между собой, но ещё не на финальных позициях.
- Пузырьковую сортировку можно улучшить с помощью флага: если проход не совершает обменов, список уже отсортирован, и алгоритм останавливается. На почти отсортированных данных это превращает её в один проход.
- Без флага обе являются $n^2$ в худшем случае, поэтому либо является плохим выбором для большого файла, и поэтому экзамен спрашивает о маленьких.
Отсортированный список из 10,000 записей получает 5 новую запись в конце. Какой метод сортировки подходит для повторной сортировки?
Почти отсортированные данные — это именно лучший случай для сортировки вставками, приближающийся к O(n). Реальные библиотеки переключаются на неё по этой причине.
Сопоставьте каждый метод сортировки с тем, чего достигается за один проход.
Именно эту разницу и проверяет вопрос о трассировке. Флаг пузырьковой сортировки также позволяет ей преждевременно завершиться на почти отсортированных данных, что сортировка вставками обрабатывает хорошо и без того.
Потерянные баллы
- Пузырьковая сортировка сравнивает соседние пары. Ответ, в котором элемент сравнивается со всеми остальными, описывает другой алгоритм.
- Внутренний цикл сокращается с каждой итерацией, потому что конец массива уже отсортирован. Объясните почему.
- Сортировка вставками сдвигает элементы вправо, чтобы освободить место; она не выполняет многократных обменов. Разница между этими подходами является сутью алгоритма.
- Оба алгоритма имеют сложность $O(n^2)$ в среднем и в худшем случае, и $O(n)$ в лучшем. Укажите случай для каждого порядка.
Вы поняли
- Пузырьковая сортировка: многократные проходы, сравнивающие смежные пары элементов и выполняющие обмен, при этом максимальный элемент «всплывает» к концу, внутренний цикл сокращается с каждым проходом, используется флаг
swappedдля раннего выхода. - Сортировка вставками: формирование отсортированной секции спереди, временное хранение текущего элемента, сдвиг больших элементов вправо и установка ключа на освободившееся место.
- Оба алгоритма имеют сложность $O(n^2)$ в среднем и худшем случае, $O(n)$ в лучшем, работают на месте и являются устойчивыми.
- Сортировка вставками действительно выигрывает на малых или почти отсортированных списках; для большого неотсортированного списка ни один из них не подходит.