Данные: Массив данных о пассажирах некоторой авиакомпании: номер рейса, дата рейса, ФИО пассажира, номер места в самолете (сравнение по полям – дата рейса, номер рейса, ФИО, номер места)
Сортировки:
- Сортировка пузырьком
- Сортировка простыми вставками
- Пирамидальная сортировка
Идея заключается в том, чтобы сортировать по шагам. На каждом шаге проходимся "снизу" (начало массива) "вверх" (конец массива) и попарно сравниваем соседние элементы. Если элемент "ниже" больше "верхнего", то меняем их местами. Повторяем эту процедуру N раз, где N -- размер массива.
На каждом шаге бОльшие элементы будут "всплывать" вверх как пузырьки, hence the name
Каждый шаг сортировки мы сравниваем i-ый элемент с предшествующими ему (уже отсортированными). Как только мы находим элемент, который больше i-го -- они меняются местами и процесс повторяется. Таким образом в начале массива у нас потихоньку растёт "отсортированная" часть.
Пирамиду (кучу) определяем как бинарное дерево высоты k, где:
- Все вершины имеют глубину k или k - 1 (сбалансированное)
- Уровень k - 1 заполнен целиком, а уровень k -- слева направо
- Каждый элемент меньше или равен родителю
Сортировка производится в 2 фазы:
- Построение пирамиды
- Сама сортировка
Построение пирамиды производится следующим образом:
Хранить пирамиду предлагается в массиве. Для любого элемента с индексом i его детьми будут элементы с индексами 2i + 1 и 2i + 2
Строить пирамиду предлагается "расширением":
Если на индексах vec[i+1] .. vec[n] хранится пирамида, то мы можем расширить её до индекса vec[i] следующим образом:
- Выбираем наибольшего ребенка из vec[2i+1], vec[2i+2]
- Если наибольший ребенок больше vec[i] -- меняем их местами и повторяем процедуру, иначе останавливаем процедуру
Когда пирамида была построена, остаётся всего лишь взять первый элемент массива (самый верхний в пирамиде), поменять местами с нижним (самым последним) и повторить процесс построения пирамиды, "забыв" о последнем (теперь самом большом) элементе