Алгоритмы сортировки массивов не всегда применимы, если сортируемые данные расположены в структуре с последовательным доступом, которая характеризуется тем, что в каждый момент имеется непосредственный доступ к одному и только одному компоненту.
Основной применяемый метод для сортировки файлов — сортировка слиянием.
Сортировка слиянием — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке.
Слияние означает объединение двух (или более) последовательностей в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент.
Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Затем их решения комбинируются, и получается решение исходной задачи.
Операция, которая однократно обрабатывает множество данных, называется фазой.
Наименьший подпроцесс, который, повторяясь, образует процесс сортировки, называется проходом или этапом.
Процедура слияния предполагает объединение двух предварительно упорядоченных подпоследовательностей размерности 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;
}
Результат выполнения
Самый лаконичный вариант, который мне удалось реализовать
«`c
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
{
if (size == 1)
return;
merge_sort(arr, size/2);
merge_sort(&arr[size/2], size - size/2);
uint32_t liter = 0; /* left half iteraor */
uint32_t riter = 0; /* right half iteraor */
uint32_t tmp[size];
for(uint32_t i = 0; i < size; i++){
if(arr[liter] < arr[size/2 + riter])
tmp[i] = arr[liter++];
else
tmp[i] = arr[size/2 + riter++];
if (liter == size / 2){ /* ran out of left half */
while(riter < size - size / 2)
tmp[++i] = arr[size/2 + riter++];
break;
} else if (riter == size - size / 2){ /* ran out of right half */
while(liter < size / 2)
tmp[++i] = arr[liter++];
break;
}
}
for(uint32_t i = 0; i < size; i++)
arr[i] = tmp[i];
}
«`
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
{
if (fsize < 2)return;
sort_direct_merge(a, fsize / 2);
sort_direct_merge(&a[fsize / 2], fsize - (fsize / 2));
int* buf = new int[fsize];
int idbuf = 0, idl = 0, idr = fsize / 2 ;
while ((idl < fsize / 2) && (idr < fsize))
if (a[idl] > a[idr])
buf[idbuf++] = a[idl++];
else
buf[idbuf++] = a[idr++];
while (idl < fsize / 2) buf[idbuf++] = a[idl++];
while (idr < fsize) buf[idbuf++] = a[idr++];
for (idl = 0; idl < fsize; idl++)a[idl] = buf[idl];
delete[]buf;
}
если вдруг кому надо рабочее
Код сортировки двухпутевого слияния некорректен, для больших наборов данных (> 10 элементов), не сортирует массив.
да даже для 5 элементов не работает
Опытным путём выяснилось, что алгоритм сортировки двухпутёвым слиянием (кода приведённого в статье, по крайней мере) годен только для массивов размерности степени двойки (т.е. 2, 4, 8, 16 и т.д.). В остальных случаях же выдаётся несуразица.
как построит код соритировки по слиянием с интерации
А есть сортировка естественным слиянием?
Здравствуйте, Елена.Как лучше поступить, если в программе строки двумерного массива уже отсортированы, как их слить в единую возрастающую последовательность?
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
using namespace std;
int main()
{
// Заполнение массивов (то, что уже есть)
int a[] = { 1,4,5,8,9 };
int b[] = { 2,3,4,7 };
// определение длины массивов
const int alength = sizeof(a) / sizeof(a[0]);
const int blength = sizeof(b) / sizeof(b[0]);
int aindex = 0;
int bindex = 0;
int cindex = 0;
// создание массива для отсортированной последовательности
int* c = new int[alength + blength];
// сортировка
while ((aindex < alength) && (bindex < blength))
{
if (a[aindex] < b[bindex])
{
c[cindex] = a[aindex];
aindex++;
}
else
{
c[cindex] = b[bindex];
bindex++;
}
cindex++;
}
// загружаем остатки строк (работать будет всегда только один из этих циклов)
while (aindex < alength)
c[cindex++] = a[aindex++];
while (bindex < blength) // загружаем остатки строк
c[cindex++] = b[bindex++];
// вывод получившейся последовательности
for (int i = 0; i < cindex; i++)
cout << c[i] << " ";
cin.get();
return 0;
}
Это,как я понял,только для двух одномерных массивов.Я имел ввиду, что если у нас матрица из n строк, то есть n одномерных массивов одинаковой известной длины, и они уже отсортированы, вот как их слиять в один одномерный массив по возрастанию?
Самое простое — слить попарно и проделать эту процедуру нужное количество раз.
В этом и проблема,я написал алгоритм для слияния двух отдельных одномерных массивов, а как это сделать в матрице? Можете написать как,я понимаю, что последовательно сливать одну за другой , но как это написать в программе?
пусть int *func(int *a,int *b) — функция слияния массивов а и b, выдаёт указатель на слитый воедино массив с, N — число строк матрицы, M — число столбцов
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
using namespace std;
int* merge(int* a, int* b, int N, int M)
{
int aindex = 0;
int bindex = 0;
int cindex = 0;
// создание массива для отсортированной последовательности
int *c = new int[N + M];
// сортировка
while ((aindex < N) && (bindex < M))
{
if (a[aindex] < b[bindex])
{
c[cindex] = a[aindex];
aindex++;
}
else
{
c[cindex] = b[bindex];
bindex++;
}
cindex++;
}
// загружаем остатки строк (работать будет всегда только один из этих циклов)
while (aindex < N)
c[cindex++] = a[aindex++];
while (bindex < M) // загружаем остатки строк
c[cindex++] = b[bindex++];
return c;
}
int main()
{
int a[4][3] = { {1,4,5},{8,9,12}, {2,3,7}, {6,10,14}};
int alength = 3;
int *c = merge(a[0], a[1], alength, alength);
int size = alength + alength;
for (int i = 2; i < 4; i++)
{
c = merge(c, a[i], size, alength);
size += alength;
}
// вывод получившейся последовательности
for (int i = 0; i < size; i++)
cout << c[i] << " ";
cin.get();
return 0;
}
Конечно, не самый эффективный алгоритм, поскольку каждый раз придется просматривать уже сформированную последовательность. Но рабочий.
Можно просматривать все строки матрицы одновременно — будет быстрее, но это уже в личку, если интересно.
Я немножко поумничаю 🙂
Метод нисходящего слияния на Си нужно немного доработать:
Добавить в конец функции сортировки >> free(tmp);
количество выделяемой памяти для того же tmp можно уменьшить, если чуть подправить строку 14 >> int *tmp = (int*)malloc((r-l+1) * sizeof(int));
Админу бобра, добра и виноградной чачи
Спасибо за примеры, помогли разобраться с сортировкой слиянием. Зашел второй раз написать о найденных ошибках, приводящие к утечкам памяти в нисходящем слиянии. Но Павел Милько меня опередил).
Почему для больших массивов(например 567) программа не работает?
Как пофиксить в нисходящем слияние на Си чтобы при не четном mid всё работало
с этой строчкой появляется много багов, если вместо нее написать просто
код становится рабочим.
Вы что-то путаете.Строчка
int temp[n];
будет работать в единственном случае — если n — константа.
Если n задаётся на этапе выполнения программы, то от динамического выделения памяти никуда не деться.
Да, я что-то путаю. В нисходящем слиянии вылетает программа при нечетном количестве элементов, и, если заменить динамическое выделение памяти на
int tmp[r];
, программа работает корректно.
Несмотря на то что Макар действительно неправильно сформулировал мысль, но в данной строчке действительно есть ошибка:
А именно: sizeof(temp) — неправильное взят sizeof, правильные варианты:
sizeof(*temp) и sizeof(int)
Исходный вариант возьмёт sizeof(temp) = 8 байт для 64 битных машин, и выделяется
n * 8 байт. Что никак не является корректным выделением.
Спасибо, исправила
В Вашей строке int *temp = (int*)malloc(n * sizeof(temp)); есть баг: sizeof(temp), а в приведенном коде его нет:
int *temp = (int*)malloc(n * sizeof(int));
Первый код при нечетном mid не работает.
функция нисходящего слияния (рекурсия) не работает, вы конечно знаете об этом, тем более вопрос — почему ?
Не поняла вопрос. Что именно не работает? При каком наборе исходных данных?
Спасибо вам огромное, вы просто спасительница!
Буду очень признательна любому, даже маленькому «спасибо» в форме поддержки сайта 🙂 .
Если Вам не трудно, то могли бы вы мне помочь? Напишите этот код, нужен позарез.
Добавила код реализации в текст статьи
Есть где-то реализация (код) для метода восходящего слияния? Прям очень надо, буду признателен за помощь
Елена, если сможете код предоставить я буду очень вам благодарен. Биты день сижу над этим и безрезультатно
Быстро помочь не могу, потому что готового кода у меня нет
А где применяется эта сортировка на практике?
Такой способ сортировки применяется для структур с последовательным доступом. В частности, если необходимо отсортировать данные, организованные в виде связных списков.
А можете представить, как будет работать алгоритм при количестве элементов 15, а лучше — 19?
Дмитрий, Вы можете скопировать код примера и пронаблюдать его работу с тем количеством элементов, с каким хотите.
Первый код, при не четном значении mid, работает не корректно!
мне нужен код по теме сортировка файлов простым слиянием есть у вас?
Всё, что есть — в этой статье.