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

Одна из сортировок на основе слияния называется простым слиянием.

Алгоритм сортировки простым слияния является простейшим алгоритмом внешней сортировки, основанный на процедуре слияния серией.

В данном алгоритме длина серий фиксируется на каждом шаге. В исходном файле все серии имеют длину 1, после первого шага она равна 2, после второго – 4, после третьего – 8, после k-го шага – .

Алгоритм сортировки простым слиянием

Шаг 1. Исходный файл f разбивается на два вспомогательных файла f1 и f2.

Шаг 2. Вспомогательные файлы f1 и f2 сливаются в файл f, при этом одиночные элементы образуют упорядоченные пары.

Шаг 3. Полученный файл f вновь обрабатывается, как указано в шагах 1 и 2. При этом упорядоченные пары переходят в упорядоченные четверки.

Шаг 4. Повторяя шаги, сливаем четверки в восьмерки и т.д., каждый раз удваивая длину слитых последовательностей до тех пор, пока не будет упорядочен целиком весь файл (рис. 1).

После выполнения i проходов получаем два файла, состоящих из серий длины . Окончание процесса происходит при выполнении условия . Следовательно, процесс сортировки простым слиянием требует порядка проходов по данным.

Признаками конца сортировки простым слиянием являются следующие условия:

· длина серии не меньше количества элементов в файле (определяется после фазы слияния);

· количество серий равно 1 (определяется на фазе слияния).

· при однофазной сортировке второй по счету вспомогательный файл после распределения серий остался пустым.

Рис.1. Демонстрация сортировки двухпутевым двухфазным простым слиянием

//Описание функции сортировки простым слиянием

void Simple_Merging_Sort (char *name){

int a1, a2, k, i, j, kol, tmp;

FILE *f, *f1, *f2;

kol = 0;

if ( (f = fopen(name,"r")) == NULL )

printf("\nИсходный файл не может быть прочитан...");

else {

while ( !feof(f) ) {

fscanf(f,"%d",&a1);

kol++;

}

fclose(f);

}

k = 1;

while ( k < kol ){

f = fopen(name,"r");

f1 = fopen("smsort_1","w");

f2 = fopen("smsort_2","w");

if ( !feof(f) ) fscanf(f,"%d",&a1);

while ( !feof(f) ){

for ( i = 0; i < k && !feof(f) ; i++ ){

fprintf(f1,"%d ",a1);

fscanf(f,"%d",&a1);

}

for ( j = 0; j < k && !feof(f) ; j++ ){

fprintf(f2,"%d ",a1);

fscanf(f,"%d",&a1);

}

}

fclose(f2);

fclose(f1);

fclose(f);

f = fopen(name,"w");

f1 = fopen("smsort_1","r");

f2 = fopen("smsort_2","r");

if ( !feof(f1) ) fscanf(f1,"%d",&a1);

if ( !feof(f2) ) fscanf(f2,"%d",&a2);

while ( !feof(f1) && !feof(f2) ){

i = 0;

j = 0;

while ( i < k && j < k && !feof(f1) && !feof(f2) ) {

if ( a1 < a2 ) {

fprintf(f,"%d ",a1);

fscanf(f1,"%d",&a1);

i++;

}

else {

fprintf(f,"%d ",a2);

fscanf(f2,"%d",&a2);

j++;

}

}

while ( i < k && !feof(f1) ) {

fprintf(f,"%d ",a1);

fscanf(f1,"%d",&a1);

i++;

}

while ( j < k && !feof(f2) ) {

fprintf(f,"%d ",a2);

fscanf(f2,"%d",&a2);

j++;

}

}

while ( !feof(f1) ) {

fprintf(f,"%d ",a1);

fscanf(f1,"%d",&a1);

}

while ( !feof(f2) ) {

fprintf(f,"%d ",a2);

fscanf(f2,"%d",&a2);

}

fclose(f2);

fclose(f1);

fclose(f);

k *= 2;

}

remove("smsort_1");

remove("smsort_2");

}

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