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

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

 

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

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

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

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

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

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

Процедура слияния предполагает объединение двух предварительно упорядоченных подпоследовательностей размерности 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(temp)); // дополнительный массив
  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;
}

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


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

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

  • Анатолий

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


    • Елена Вставская

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



  • Виталий

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


  • Виталий

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


    • Виталий

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


      • Елена Вставская

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



    • Елена Вставская

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


  • Дмитрий

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


    • Елена Вставская

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


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

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