Ключевые термины

Алгоритм сортировки – это алгоритм для упорядочения некоторого множества элементов.

Бинарная пирамидальная сортировка – это алгоритм внутренней сортировки, основанный на построении пирамиды и просеивании элементов из ее вершины методом спуска вниз в соответствии с ключом сортировки.

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

Внешняя сортировка – это алгоритм сортировки, который при проведении упорядочивания данных использует внешнюю память, как правило, жесткие диски.

Внутренняя сортировка – это алгоритм сортировки, который в процессе упорядочивания данных использует толькооперативную память (ОЗУ) компьютера.

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

Естественность поведения – это один из параметров трудоемкости алгоритма, которой указывает на эффективность метода при обработке уже отсортированных, или частично отсортированных данных.

Ключ сортировки – это атрибут (или несколько атрибутов), по значению которого определяется порядок элементов во множестве.

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

Память – один из параметров трудоемкости алгоритма, который характеризует размер выделяемой дополнительной памяти под временное хранение данных.

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

Просеивание – это построение новой пирамиды посредством спуска вниз элемента из вершины дерева в соответствии с ключом сортировки

Слияние – это объединение двух или более упорядоченных массивов в один упорядоченный.

Сортировка слиянием – это одна из разновидностей алгоритмов быстрых сортировок, основанная на слиянии подмножеств массива.

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

Сортировка Шелла – это алгоритм внутренней сортировки, основанный на сравнении и перемещении пар значений, расположенных сначала достаточно далеко друг от друга в упорядочиваемом наборе данных, с дальнейшим сокращением расстояний между ними.

Устойчивость – это один из параметров трудоемкости алгоритма, который характеризует то, что сортировка не меняет взаимного расположения равных элементов.