Алгоритмы сортировки массивов не всегда применимы, если сортируемые данные расположены в структуре с последовательным доступом, которая характеризуется тем, что в каждый момент имеется непосредственный доступ к одному и только одному компоненту.
Основной применяемый метод для сортировки файлов — сортировка слиянием.
Сортировка слиянием — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке.
Слияние означает объединение двух (или более) последовательностей в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент.
Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Затем их решения комбинируются, и получается решение исходной задачи.
Операция, которая однократно обрабатывает множество данных, называется фазой.
Наименьший подпроцесс, который, повторяясь, образует процесс сортировки, называется проходом или этапом.
Процедура слияния предполагает объединение двух предварительно упорядоченных подпоследовательностей размерности n/2 в единую последовательность размерности n. Начальные элементы предварительно упорядоченных последовательностей сравниваются между собой, и из них выбирается наименьший. Соответствующий указатель перемещается на следующий элемент. Процедура повторяется до тех пор, пока не достигнут конец одной из подпоследовательностей. Оставшиеся элементы другой подпоследовательности при этом передаются в результирующую последовательность в неизменном виде.
Сортировка слиянием во многом похожа на метод быстрой сортировки. Производительность сортировки слиянием лежит между производительностью пирамидальной и быстрой сортировки. Но в отличие от пирамидальной и быстрой сортировок, метод сортировки слиянием ведет себя стабильно, поскольку он не зависит от перестановок элементов в массиве.
Еще одним достоинством сортировки слиянием является то, что он удобен для структур с последовательным доступом к элементам, таким как файлы на внешнем устройстве или связные списки. Этот метод, прежде всего, используется для внешней сортировки.
Недостатки метода заключаются в том, что он требует дополнительной памяти по объему равной объему сортируемого файла. Поэтому для больших файлов проблематично организовать сортировку слиянием в оперативной памяти.
В случаях, когда гарантированное время сортировки важно и размещение в оперативной памяти, возможно, следует предпочесть метод сортировки слиянием.
Алгоритм двухпутевого слияния
Исходная последовательность разбивается на две подпоследовательности:
Эти две подпоследовательности объединяются в одну, содержащую упорядоченные пары.
Полученная последовательность снова разбивается на две, и пары объединяются в упорядоченные четверки:
Полученная последовательность снова разбивается на две и собирается в упорядоченные восьмерки.
Данная операция повторяется до тех пор, пока полученная упорядоченная последовательность не будет иметь такой же размер, как у сортируемой.
Основной операцией является слияние. При слиянии требуется дополнительная память для размещения файла, образующегося при слиянии. Операция линейно зависит от количества элементов в объединяемых массивах.
Реализация метода двухпутевого слияния на Си
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <stdlib.h>
// Функция сортировки двухпутевым слиянием
void merge(int *a, int n)
{
int mid = n / 2; // находим середину сортируемой последовательности
if (n % 2 == 1)
mid++;
int h = 1; // шаг
// выделяем память под формируемую последовательность
int *c = (int*)malloc(n * sizeof(int));
int step;
while (h < n)
{
step = h;
int i = 0; // индекс первого пути
int j = mid; // индекс второго пути
int k = 0; // индекс элемента в результирующей последовательности
while (step <= mid)
{
while ((i < step) && (j < n) && (j < (mid + step)))
{ // пока не дошли до конца пути
// заполняем следующий элемент формируемой последовательности
// меньшим из двух просматриваемых
if (a[i] < a[j])
{
c[k] = a[i];
i++; k++;
}
else {
c[k] = a[j];
j++; k++;
}
}
while (i < step)
{ // переписываем оставшиеся элементы первого пути (если второй кончился раньше)
c[k] = a[i];
i++; k++;
}
while ((j < (mid + step)) && (j<n))
{ // переписываем оставшиеся элементы второго пути (если первый кончился раньше)
c[k] = a[j];
j++; k++;
}
step = step + h; // переходим к следующему этапу
}
h = h * 2;
// Переносим упорядоченную последовательность (промежуточный вариант) в исходный массив
for (i = 0; i<n; i++)
a[i] = c[i];
}
}
int main()
{
int a[8];
// Заполнение массива случайными числами
for (int i = 0; i<8; i++)
a[i] = rand() % 20 - 10;
// Вывод элементов массива до сортировки
for (int i = 0; i<8; i++)
printf("%d ", a[i]);
printf("\n");
merge(a, 8); // вызов функции сортировки
// Вывод элементов массива после сортировки
for (int i = 0; i<8; i++)
printf("%d ", a[i]);
printf("\n");
getchar();
return 0;
}
Результат выполнения
Метод нисходящего слияния
Исходная последовательность рекурсивно разбивается на половины, пока не получим подпоследовательности по 1 элементу. Из полученных подпоследовательностей формируем упорядоченные пары методом слияния, затем - упорядоченные четверки и т.д.
Рассмотрим последовательность
Разбиваем последовательность на 2 половины (рекурсивно, пока не получим пары).
Каждую подпоследовательность упорядочиваем методом слияния и получаем готовую последовательность.
Реализация метода нисходящего слияния на Си
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdlib.h>
#define SIZE 16
// Функция сортировки нисходящим слиянием
void mergeSort(int *a, int l, int r)
{
if (l == r) return; // границы сомкнулись
int mid = (l + r) / 2; // определяем середину последовательности
// и рекурсивно вызываем функцию сортировки для каждой половины
mergeSort(a, l, mid);
mergeSort(a, mid + 1, r);
int i = l; // начало первого пути
int j = mid + 1; // начало второго пути
int *tmp = (int*)malloc(r * sizeof(int)); // дополнительный массив
for (int step = 0; step < r - l + 1; step++) // для всех элементов дополнительного массива
{
// записываем в формируемую последовательность меньший из элементов двух путей
// или остаток первого пути если j > r
if ((j > r) || ((i <= mid) && (a[i] < a[j])))
{
tmp[step] = a[i];
i++;
}
else
{
tmp[step] = a[j];
j++;
}
}
// переписываем сформированную последовательность в исходный массив
for (int step = 0; step < r - l + 1; step++)
a[l + step] = tmp[step];
}
int main()
{
int a[SIZE];
// Заполняем элементы массива
for (int i = 0; i<SIZE; i++)
{
a[i] = (rand() % 100);
printf(" %d ", a[i]);
}
mergeSort(a, 0, SIZE - 1); // вызываем функцию сортировки
printf("\n");
// Выводим отсортированный массив
for (int i = 0; i<SIZE; i++)
printf(" %d ", a[i]);
getchar();
return 0;
}
Результат выполнения
Метод восходящего слияния
В методе восходящего слияния отсутствует процедура рекурсивного разделения последовательности пополам. Исходная последовательность представляется как последовательный набор отдельных элементов.
Реализация метода восходящего слияния на Си
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdlib.h>
#define SIZE 15
// Метод восходящего слияния
void mergeSort(int *a, int n)
{
int step = 1; // шаг разбиения последовательности
int *temp = (int*)malloc(n * sizeof(int)); // дополнительный массив
while (step < n) // пока шаг меньше длины массива
{
int index = 0; // индекс результирующего массива
int l = 0; // левая граница участка
int m = l + step; // середина участка
int r = l + step * 2; // правая граница участка
do
{
m = m < n ? m : n; // сортируемый участок не выходит за границы последовательности
r = r < n ? r : n;
int i1 = l, i2 = m; // индексы сравниваемых элементов
for (; i1 < m && i2 < r; ) // пока i1 не дошёл до середины и i2 не дошёл до конца
{
if (a[i1] < a[i2]) { temp[index++] = a[i1++]; } // заполняем участок результирующей последовательности
else { temp[index++] = a[i2++]; }
}
// Или i1 < m или i2 < r - только один из операторов while может выполниться
while (i1 < m) temp[index++] = a[i1++]; // заносим оставшиеся элементы сортируемых участков
while (i2 < r) temp[index++] = a[i2++]; // в результирующий массив
l += step * 2; // перемещаемся на следующий сортируемый участок
m += step * 2;
r += step * 2;
} while (l < n); // пока левая граница сортируемого участка - в пределах последоватльности
for (int i = 0; i < n; i++) // переносим сформированный массив обратно в a
a[i] = temp[i];
step *= 2; // увеличиваем в 2 раза шаг разбиения
}
}
int main()
{
int a[SIZE];
// Заполняем элементы массива
for (int i = 0; i<SIZE; i++)
{
a[i] = (rand() % 100);
printf(" %d ", a[i]);
}
mergeSort(a, SIZE); // вызываем функцию сортировки
printf("\n");
// Выводим отсортированный массив
for (int i = 0; i<SIZE; i++)
printf(" %d ", a[i]);
getchar();
return 0;
}
Результат выполнения
