Алгоритмы сортировки
| English | Русский |
|---|---|
| Sorting/ˈsɔːtɪŋ/ | Сортировка |
| selection sort/sɪˈlekʃn sɔːt/ | сортировка выбором |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | сортировка вставками |
| in place/ɪn pleɪs/ | на месте |
Упорядочивание элементов
- Сортировка переставляет элементы по порядку (от наименьшего к наибольшему, например).
- Курс AP охватывает две простые сортировки: сортировку выбором и сортировку вставками.
- Обе используют вложенные циклы и меняют местами или сдвигают элементы на свои места.
- Сначала отсортировать — это то, что позволяет потом использовать быстрый бинарный поиск.
Сортировка выбором
- Найдите наименьший из оставшихся элементов и поменяйте его местами с первым.
- Затем найдите наименьший среди оставшихся, переместите его на следующее место и так далее.
- Передняя часть массива становится отсортированной; задняя уменьшается, оставаясь неотсортированной.
- Один обмен за проход — но каждый раз сканируется остальная часть.
Вставочная сортировка
- Возьмите следующий элемент и сдвиньте его назад, чтобы поставить на нужное место среди уже отсортированной передней части.
- Как сортировка карт в руке: вставьте каждую новую карту на её место.
- Отсортированная область увеличивается на один элемент за каждый проход.
- Быстро работает, когда данные уже почти отсортированы.
Объем работы
- Обе сортировки используют вложенные циклы, поэтому в худшем случае выполняют около
n²сравнений. - Это нормально для малых массивов, но медленно для очень больших.
- Они сортируют на месте — дополнительный массив не требуется.
- На экзамене нужно уметь их трассировать, а не просто называть.
Сортировка выбором ПОМЕНЯТЬ МИЕСТАМИ наименьший оставшийся элемент в начало; сортировка вставками СДВИГАЕТ каждый новый элемент назад в отсортированную часть — не путайте. Обе являются вложенными-циклическими, in-place, O(n²) сортировками. Трассируйте их пошагово (AP-экзамен требует показать состояние массива после каждого прохода), вместо того чтобы заучивать названия.
Сортировка выбором на [3, 1, 2]:
- Проход 1: наименьший —
1; обмен с началом →[1, 3, 2]. - Проход 2: наименьший из
[3, 2]— это2; обмен →[1, 2, 3]. - Отсортировано — передняя часть увеличилась на один элемент за проход.
Сортировка упорядочивает элементы. Сортировка выбором многократно меняет местами наименьший оставшийся элемент в начало; сортировка вставками сдвигает каждый новый элемент назад в отсортированную часть. Обе являются вложенными-циклическими, in-place, O(n²) сортировками. Сортировка позволяет быстро выполнять бинарный поиск позже.
Прохождение через процесс сортировки
Каждый проход размещает еще один элемент на правильное место.
Сортировка выбором работает путем...
Сортировка выбором выбирает минимум и перемещает его вперед.
Сортировка вставками работает путем...
Сортировка вставками вставляет каждый элемент на свое отсортированное место.
В худшем случае обе сортировки выполняют около...
Вложенные циклы дают сложность O(n²).
Оба метода, выбор и вставки, работают in place (без второго массива).
Они переставляют элементы в том же самом массиве.
Расставьте проходы сортировки выбором для [3, 1, 2].
Начало массива растет отсортированным, один элемент за проход.
Предварительная сортировка полезна, потому что позволяет позже использовать...
Бинарный поиск требует отсортированные данные.