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

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

 

Алгоритмы сортировки массивов не всегда применимы, если сортируемые данные расположены в структуре с последовательным доступом, которая характеризуется тем, что в каждый момент имеется непосредственный доступ к одному и только одному компоненту.

Основной применяемый метод для сортировки файлов — сортировка слиянием.
Сортировка слиянием — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке.

Слияние означает объединение двух (или более) последовательностей в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент.

Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Затем их решения комбинируются, и получается решение исходной задачи.

Операция, которая однократно обрабатывает множество данных, называется фазой.

Наименьший подпроцесс, который, повторяясь, образует процесс сортировки, называется проходом или этапом.

Процедура слияния предполагает объединение двух предварительно упорядоченных подпоследовательностей размерности n/2 в единую последовательность размерности n. Начальные элементы предварительно упорядоченных последовательностей сравниваются между собой, и из них выбирается наименьший. Соответствующий указатель перемещается на следующий элемент. Процедура повторяется до тех пор, пока не достигнут конец одной из подпоследовательностей. Оставшиеся элементы другой подпоследовательности при этом передаются в результирующую последовательность в неизменном виде.

Процедура слияния

Сортировка слиянием во многом похожа на метод быстрой сортировки.  Производительность сортировки слиянием лежит между производительностью пирамидальной и быстрой сортировки. Но в отличие от пирамидальной и быстрой сортировок, метод сортировки слиянием ведет себя стабильно, поскольку он не зависит от перестановок элементов в массиве.

Еще одним достоинством сортировки слиянием является то, что он удобен для структур с последовательным доступом к элементам, таким как файлы на внешнем устройстве или связные списки. Этот метод, прежде всего, используется для внешней сортировки.

Недостатки метода заключаются в том, что он требует дополнительной памяти по объему равной объему сортируемого файла. Поэтому для больших файлов проблематично организовать сортировку слиянием в оперативной памяти.

В случаях, когда гарантированное время сортировки важно и размещение в оперативной памяти, возможно, следует предпочесть метод сортировки слиянием.

 

Алгоритм двухпутевого слияния

Исходная последовательность разбивается на две подпоследовательности:
Двухпутевое слияние
Двухпутевое слияние

Эти две подпоследовательности объединяются в одну, содержащую упорядоченные пары.
Упорядоченные пары

Полученная последовательность снова разбивается на две, и пары объединяются в упорядоченные четверки:
Упорядоченные четверки
Упорядоченные четверки

Полученная последовательность снова разбивается на две и собирается в упорядоченные восьмерки.
Упорядоченные восьмерки
Упорядоченные восьмерки

Данная операция повторяется до тех пор, пока полученная упорядоченная последовательность не будет иметь такой же размер, как у сортируемой.

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

Реализация метода двухпутевого слияния на Си

1
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 <stdio.h>
#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 половины (рекурсивно, пока не получим пары).
Разбиение на пары

Каждую подпоследовательность упорядочиваем методом слияния и получаем готовую последовательность.
Готовая последовательность

Реализация метода нисходящего слияния на Си

1
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 <stdio.h>
#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;
}

Результат выполнения
Результат нисходящего слияния

Метод восходящего слияния

В методе восходящего слияния отсутствует процедура рекурсивного разделения последовательности пополам. Исходная последовательность представляется как последовательный набор отдельных элементов.
Восходящее слияние

Реализация метода восходящего слияния на Си

1
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 <stdio.h>
#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;
}

Результат выполнения
Реализация метода восходящего слияния


Назад: Алгоритмы сортировки и поиска

Комментариев к записи: 40

  • Самый лаконичный вариант, который мне удалось реализовать ```c
    1
    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
    void merge_sort(uint32_t* arr, uint32_t size)
    {
      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];
    }
    ```

  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    void sort_direct_merge(int a[], int fsize)
    {
        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 элементов), не сортирует массив.


    • Опытным путём выяснилось, что алгоритм сортировки двухпутёвым слиянием (кода приведённого в статье, по крайней мере) годен только для массивов размерности степени двойки (т.е. 2, 4, 8, 16 и т.д.). В остальных случаях же выдаётся несуразица.



  • Здравствуйте, Елена.Как лучше поступить, если в программе строки двумерного массива уже отсортированы, как их слить в единую возрастающую последовательность?

    • Елена Вставская
      1
      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
      #include <iostream>
      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 - число столбцов

          • Елена Вставская
            1
            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
            #include <iostream>
            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)); Админу бобра, добра и виноградной чачи

    • Виталий
      Спасибо за примеры, помогли разобраться с сортировкой слиянием. Зашел второй раз написать о найденных ошибках, приводящие к утечкам памяти в нисходящем слиянии. Но Павел Милько меня опередил).


  • Как пофиксить в  нисходящем слияние на Си чтобы при не четном mid всё работало

  • 1
    int *temp = (int*)malloc(n * sizeof(temp));
     с этой строчкой появляется много багов, если вместо нее написать просто
    1
    int temp[n];
    код становится рабочим.

    • Елена Вставская
      Вы что-то путаете.Строчка int temp[n]; будет работать в единственном случае - если n - константа. Если n задаётся на этапе выполнения программы, то от динамического выделения памяти никуда не деться.

      • Да, я что-то путаю. В нисходящем слиянии вылетает программа при нечетном количестве элементов, и, если заменить динамическое выделение памяти на int tmp[r]; , программа работает корректно.

      • Несмотря на то что Макар действительно неправильно сформулировал мысль, но в данной строчке действительно есть ошибка:
        1
        int *temp = (int*)malloc(n * sizeof(temp));
        А именно: 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));


  • Анатолий
    функция нисходящего слияния (рекурсия) не работает, вы конечно знаете об этом, тем более вопрос - почему ?

    • Елена Вставская
      Не поняла вопрос. Что именно не работает? При каком наборе исходных данных?


  • Виталий
    Если Вам не трудно, то могли бы вы мне помочь? Напишите этот код, нужен позарез.

  • Виталий
    Есть где-то реализация (код) для метода восходящего слияния? Прям очень надо, буду признателен за помощь

    • Виталий
      Елена, если сможете код предоставить я буду очень вам благодарен. Биты день сижу над этим и безрезультатно

      • Елена Вставская
        Быстро помочь не могу, потому что готового кода у меня нет


    • Елена Вставская
      Такой способ сортировки применяется для структур с последовательным доступом. В частности, если необходимо отсортировать данные, организованные в виде связных списков.

  • Дмитрий
    А можете представить, как будет работать алгоритм при количестве элементов 15, а лучше - 19?

    • Елена Вставская
      Дмитрий, Вы можете скопировать код примера и пронаблюдать его работу с тем количеством элементов, с каким хотите.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *