Информатика и технология программирования


Сортировка слиянием


Сортировка слиянием предполагает последовательный доступ к элементам сортируемых последовательностей. Это объясняется тем, что она была разработана для сортировки данных на устройствах последовательного доступа (магнитных лентах). Хотя никто не запрещает производить то же самое в массивах или списках. Если имеется n упорядоченных последовательностей, то получить из них общую упорядоченную последовательность достаточно просто, использую только последовательное извлечение элементов из них. При извлечении первого элемента из последовательности и переносе его в выходную следующий за ним становится первым и т.д.. Такой принцип доступа к данным имеет место при чтении последовательных файлов, поэтому слияние часто используется при сортировке файлов данных.

ОДНОКРАТНОЕ СЛИЯНИЕ. Очевидно, что если из упорядоченных последовательностей брать по одному очередному элементу из каждой, затем выбирать из них минимальный и переносить его, то выходная последовательность будет упорядоченной. Отсюда возможен самый простой способ однократного слияния : массив разбивается на n частей, каждая из них сортируется независимо, а затем отсортированные части объединяются слиянием. Текст ищите в " Вопросах без ответов " .

ЦИКЛИЧЕСКОЕ СЛИЯНИЕ. Первоначально массив разделяется на n последовательностей. Затем в каждой из них выбирается по одному элементу (первому) в таком порядке, чтобы получилась упорядоченная группа из n элементов, которая запоминается в выходной последовательности (слияние). Выходная последовательность будет состоять из групп по n элементов, каждая из которых упорядочена. Далее файл опять распределяется, но уже группами по n элементов по тем же самым n входным последовательностям. В результате слияния образуются упорядоченные группы из n*n элементов. Затем процесс повторяется группами по n*n*n и т.д.. В качестве примера рассмотрим случай с n=2 (двухпутевое слияние). Для простоты будем считать размерность сортируемого массива кратной 2.


void sort(int in[],int n, int v1[], int v2[])



Начало  Назад  Вперед



Книжный магазин