С++: Внешняя сортировка на 3х лентах

Приступим. Закончив с рассмотрением основных внутренних алгоритмов сортировки, приступим к рассмотрению внешних алгоритмов. Одним из таких есть внешняя сортировка на 3 лентах или простое слияние

Прямое слияние

Слияние означает объединение двух (или более) последовательностей в одну-единственную упорядоченную последовательность с помощью повторяющегося выбора из доступных в данный момент элементов. Слияние намного проще сортировки, и его используют как вспомогательную операцию в более сложных процессах сортировки последовательностей. Одна из сортировок на основе слияния называется простым слиянием. Она выполняется следующим образом:

C++ : Алгоритмы сортировок[2]

Продолжение предыдущей статьи...

Рекурсивные алгоритмы и улучшение известных нам из предыдущей статьи.

 Быстрая сортировка

Теперь коснемся третьего улучшения метода, основанного на обмене. Если учесть, что пузырьковая сортировка в среднем была самой неэффективной из всех трех алгоритмов прямой сортировки, то следует ожидать относительно существенного улучшения. Оно, оказывается, приводит к самому лучшему из известных в данный момент методу сортировки для массивов. Его изобретатель Ч. Хоар назвал метод быстрой сортировкой (QuickSort).

Алгоритм. Выберем наугад какой-либо элемент (назовем его x) и будем просматривать слева наш массив до тех пор, пока не обнаружим элемент  , затем будем просматривать массив справа, пока не встретим  . Теперь Поменяем местами эти два элемента и продолжим наш процесс просмотра и обмена , пока оба просмотра не встретятся где-то в середине массива. В результате массив окажется разбитым на левую часть, с ключами меньше (или равными) x, и правую – с ключами больше (или равными) x.

C++ : Алгоритмы сортировок

Для начала немного теории:

Сортировка – это упорядочение данных по некоторому признаку.

Все методы сортировки разбиты на два класса – сортировку массивов и сортировку файлов (последовательностей). Их называют соответственно внутренней и внешней сортировкой, поскольку массивы хранятся в быстрой оперативной внутренней памяти машины со случайным доступом, а файлы обычно размещаются в более медленной, но более емкой внешней памяти (на носителях). При рассмотрении элементов значение каждого будем называть ключом (key) элемента.

Сейчас мы будем говорить про сортировку массивов, то есть про Внутреннюю сортировку данных.

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

Пусть задан массив с элементами a1, a2, .......an, которые нужно расположить в возрастающем порядке.