Сортировка массива

Научиться понимать, как работают основные алгоритмы сортировки массивов, и уметь выбирать подходящий способ в зависимости от задачи.

Сортировка — одна из самых частых операций в программировании и повседневной жизни: от упорядочивания списка контактов до поиска самой дешёвой цены в интернет-магазине. Понимание алгоритмов сортировки — основа для изучения более сложных структур данных и алгоритмов.

• Сортировка массива — это процесс перестановки его элементов в определённом порядке (например, по возрастанию или убыванию).
• Существует множество алгоритмов сортировки, каждый из которых имеет свои преимущества и недостатки.
• Алгоритмы сортировки основаны на сравнении пар элементов и их обмене (или вставке) в нужное место.
• Эффективность алгоритма оценивается количеством операций сравнения и обмена, которое зависит от размера массива.
• Для небольших массивов подходят простые алгоритмы (пузырьком, выбором), а для больших — более сложные (быстрая сортировка, слиянием).
• Сортировка может быть устойчивой (сохраняет порядок равных элементов) или неустойчивой.
• Понимание сортировки помогает в поиске данных: упорядоченный массив можно искать быстрее (бинарный поиск).

Массив

Набор элементов одного типа, хранящихся в памяти последовательно и имеющих общее имя. Каждый элемент доступен по индексу (номеру).

Индекс элемента

Номер позиции элемента в массиве. Обычно индексация начинается с нуля (в большинстве языков программирования).

Сортировка

Процесс упорядочивания элементов массива по заданному правилу (например, по возрастанию чисел или в алфавитном порядке строк).

Алгоритм сортировки

Чёткая последовательность действий, которая преобразует неупорядоченный массив в упорядоченный.

Сравнение элементов

Операция, которая определяет, какой из двух элементов больше, меньше или равен другому. Лежит в основе большинства сортировок.

Обмен элементов

Перестановка двух элементов массива местами, чтобы изменить их порядок.

Устойчивая сортировка

Сортировка, при которой равные элементы сохраняют свой исходный относительный порядок.

Сложность алгоритма

Оценка того, как время выполнения алгоритма зависит от размера входных данных (обычно обозначается как O(n), O(n²) и т.д.).

• Сортировка пузырьком: многократно проходит по массиву, сравнивая соседние элементы и меняя их местами, если они стоят в неправильном порядке. Наибольший элемент «всплывает» в конец. Сложность O(n²).
• Сортировка выбором: на каждом шаге находит минимальный (или максимальный) элемент в неотсортированной части массива и меняет его с первым элементом этой части. Сложность O(n²).
• Сортировка вставками: строит отсортированную часть массива, вставляя каждый следующий элемент в правильное место среди уже отсортированных. Эффективна для небольших массивов и почти отсортированных данных. Сложность O(n²) в худшем случае, но O(n) в лучшем.
• Для массива из n элементов количество сравнений в сортировке пузырьком в худшем случае равно n*(n-1)/2.
• Быстрая сортировка (Quicksort) в среднем работает за O(n log n) и является одной из самых быстрых на практике, но в худшем случае может быть O(n²).
• Сортировка слиянием (Merge Sort) всегда работает за O(n log n), но требует дополнительную память для временного массива.

1. Пример 1случай
   • Представь, что у тебя есть список оценок за контрольную: [4, 2, 5, 3, 4]
   • Сортировка по возрастанию превратит его в [2, 3, 4, 4, 5] — так удобнее увидеть минимальную и максимальную оценку
2. Пример 2случай

   В интернет-магазине можно отсортировать товары по цене (от дешёвых к дорогим)

   Пояснение

   • это тоже сортировка массива цен
3. Пример 3случай

   Телефонная книга отсортирована по алфавиту

   Пояснение

   • это сортировка массива строк по возрастанию (по алфавиту)
4. Пример 4случай
   • При сортировке пузырьком на каждом проходе самый большой элемент «всплывает» в конец, как пузырёк воздуха в воде

• Сортировка пузырьком — один из самых простых, но и самых неэффективных алгоритмов. Название происходит от того, что большие элементы «всплывают» в конец массива, как пузырьки в газировке.
• В языке Python встроенная функция sorted() использует алгоритм Timsort, который сочетает сортировку вставками и слиянием и очень эффективен на реальных данных.
• Существуют алгоритмы сортировки, которые работают за O(n) (например, сортировка подсчётом), но они применимы только для ограниченного диапазона значений (например, целых чисел от 0 до 100).

• Одномерные массивы: ввод и вывод
• Поиск элемента в массиве
• Обработка массивов: поиск максимума и минимума
• Бинарный поиск в отсортированном массиве