Программирование на языке высокого уровня. Марапулец Ю.В. - 50 стр.

UptoLike

ВУЗ: 

КамчатГТУ | Петропавловск-Камчатский

Составители: 

Рубрика: 

На практике слияние эффективно при работе с данными большого объема в после-
довательных файлах, где принцип слияния последовательно читаемых данных без про-
смотра вперед выглядит естественно.
Простое однократное слияние базируется на других алгоритмах сортировки.
Массив разбивается на n частей, каждая из них сортируется независимо, а затем отсор-
тированные части объединяются слиянием. Реально такое слияние используется, если
массив целиком не помещается в памяти. В данной простой модели одномерный массив
разделяется на 10 частей - используется двумерный массив из 10 строк по 10 элементов.
Затем каждая строка сортируется отдельно. Алгоритм слияния использует стандартные
контексты: выбирается строка, в которой первый элемент минимальный (минимальный
из очередных), он и сливается в выходную последовательность. Исключение его произ-
водится сдвигом содержимого строки к началу, причем в конец добавляется «очень
большое число», играющее роль «пробки» при окончании этой последовательности.
void sort(int a[], int n); // Любая сортировка одномерного массива
#define N 4 // Количество массивов
void sort_sleave (int A[], int n)
{
int B[N][10]; // Размерность массивов
int i, j, m = n/N;
for (i=0; i<n; i++) // Распределение
B[i/m][i%m]=A[i];
for (i=0; i<N; i++) // Сортировка частей
sort(B[i],10);
for (i=0; i<n; i++) // Слияние
{
for ( int k=0, j=0; j<N; j++) // Индекс строки с минимальным
if (B[j][0] < B[k][0]) k=j; // B[k][0]
A[i] = B[k][0]; // Слияние элемента
for (j=1; j<m; j++) // Сдвиг сливаемой строки
B[k][j-1]=B[k][j];
B[k][m-1]=10000; // Запись ограничителя
}
}
Циклическое слияние. Оригинальный алгоритм «сортировки без сортировки» ба-
зируется на том факте, что при слиянии двух упорядоченных последовательностей дли-
ной s длина результирующей - в 2 раза больше. Главный цикл включает в себя разделе-
ние последовательности на 2 части и их обратное слияние в одну. Первоначально они
неупорядочены, тем не менее, можно считать, что в них имеются группы упорядочен-
ных элементов длиной s=1. Каждое слияние увеличивает размер группы вдвое, то есть
размер группы меняется s=2, 4, 8... Поэтому идея заключена в способе слияния: оно не
может выйти за пределы очередной группы, пока обе сливаемые группы не закончились.
Это значит, переход к следующей паре осуществляется «скачком».
В приведенной программе для простоты размерность массива должна быть равна
степени 2, чтобы группы были всегда полными. Внешний цикл организован формально:
переменная s принимает значения степени 2. В теле цикла сначала производится разде-
ление массива на две части, а затем - их слияние. Для успешного проектирования слия-
ния важно правильно выбрать индексы с учетом независимости и относительности
«движений» по отдельным массивам. Поэтому их здесь целых четыре на три массива.
Индекс i в выходном массиве увеличивается в заголовке цикла. Это значит, что за один
50
     На практике слияние эффективно при работе с данными большого объема в после-
довательных файлах, где принцип слияния последовательно читаемых данных без про-
смотра вперед выглядит естественно.

     Простое однократное слияние базируется на других алгоритмах сортировки.
Массив разбивается на n частей, каждая из них сортируется независимо, а затем отсор-
тированные части объединяются слиянием. Реально такое слияние используется, если
массив целиком не помещается в памяти. В данной простой модели одномерный массив
разделяется на 10 частей - используется двумерный массив из 10 строк по 10 элементов.
Затем каждая строка сортируется отдельно. Алгоритм слияния использует стандартные
контексты: выбирается строка, в которой первый элемент минимальный (минимальный
из очередных), он и сливается в выходную последовательность. Исключение его произ-
водится сдвигом содержимого строки к началу, причем в конец добавляется «очень
большое число», играющее роль «пробки» при окончании этой последовательности.

void sort(int a[], int n); // Любая сортировка одномерного массива
#define N 4           // Количество массивов
void sort_sleave (int A[], int n)
{
        int B[N][10]; // Размерность массивов
        int i, j, m = n/N;
        for (i=0; i

Страницы