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

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

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

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

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

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

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

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

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

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

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

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

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

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

Исходный файл f: 5 7 3 2 8 4 1
	Распределение	Слияние
1 проход	f1: 5 3 8 1   f2: 7 2 4	f: 5 7 2 3 4 8 1
2 проход	f1: 5 7 4 8   f2: 2 3 1	f: 2 3 5 7 1 4 8
3 проход	f1: 2 3 5 7   f2: 1 4 8	f: 1 2 3 4 5 7 8

Рис.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");

}

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

Дата добавления: 2014-01-04