суббота, 18 сентября 2010 г.

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

[Все сортировки]

Теория: Общая информация изложена здесь

Практика
: informatics.mccme.ru

Визуализатор: rain.ifmo.ru  [Java]

Реализация
:
  1. void merge (vector<int> &mas, int l, int m, int r)
  2. {
  3.   vector<int> buffer(r - l + 1); // результирующий массив
  4.   int pos1 = l;  // начальная позициция первого подмассива
  5.   int pos2 = m+1; // начальная позиция второго подмассива
  6.   int posB = 0;  // начальная позиция результирующего массива
  7.  
  8.   while (pos1<=m && pos2<=r)
  9.   {
  10.     if (mas[pos1]<mas[pos2])
  11.       buffer[posB++] = mas[pos1++];
  12.     else
  13.       buffer[posB++] = mas[pos2++];
  14.   }
  15.   while (pos1<=m)
  16.     buffer[posB++] = mas[pos1++];
  17.   while (pos2<=r)
  18.     buffer[posB++] = mas[pos2++];
  19.  
  20.   copy(buffer.begin(),buffer.end(),mas.begin() + l);
  21.   buffer.clear();
  22. }
  23. void merge_sort(vector<int> &mas, int l, int r)
  24. {
  25.   if (l == r) // спустились до 1 элемента
  26.     return;
  27.   int m = (l + r)>>1;
  28.   merge_sort(mas,l,m);
  29.   merge_sort(mas,m+1,r);
  30.  
  31.   merge(mas,l,m,r);
  32. }
* This source code was highlighted with Source Code Highlighter.

Хотя сортировка слиянием и имеет сложность O(N*logN), но константа у нее может быть велика. В первую очередь это связано с созданием временного массива(buffer) в функции merge. Для того, чтобы просто отсортировать массив больше подойдет алгоритм Быстрой сортировки. Но тем не менее важно знать и уметь использовать механизм слияния двух отсортированных массивов.

1 комментарий:

  1. Как дополнение к применению. Техника Merge Sort может быть применена для подсчёта количества инверсий в перестановках, нахождения результата операций для множеств после предварительной сортировки.

    ОтветитьУдалить