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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Двухпутевое слияние
Двухпутевое слияние

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

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

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

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

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

Реализация метода двухпутевого слияния
void merge(int *a, int n) {
  int mid = n/2;
  if(n%2==1)
    mid++;
  int h = 1; // шаг
  int *c;
  int step;
  c = (int*)malloc(n*sizeof(int));
  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];
    }
  }
}
Метод нисходящего слияния

Исходная последовательность рекурсивно разбивается на половины, пока не получим подпоследовательности по 1 элементу. Из полученных подпоследовательностей формируем упорядоченные пары методом слияния, затем - упорядоченные четверки и т.д.

Рассмотрим последовательность
Исходная последовательность
Разбиваем последовательность на 2 половины (рекурсивно, пока не получим пары).
Разбиение на пары

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

Реализация метода нисходящего слияния
#include <stdio.h>
#include <stdlib.h>
#define SIZE 16
int merge_sort(int *a, int l, int r) {
  if(l==r) return 0;
  int mid =(l+r)/2;
  merge_sort(a,l,mid);
  merge_sort(a,mid+1,r);
  int * tmp;
  int i=l;
  int j;
  j=mid+1;
  tmp = (int*)malloc(r*sizeof(int));
  for(int step=0; step<r-l+1; step++) {
    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];
  int i;
  for(i = 0; i<SIZE; i++) {
    a[i] = (rand() % 100);
    printf(" %d ",a[i]);
  }
  merge_sort(a,0,SIZE-1);
  printf("\n");
  for(i = 0; i<SIZE; i++)
    printf(" %d ",a[i]);
  getchar();
  return 0;
}

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

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

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

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

  • Дмитрий

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


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

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


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

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