Сортировка Слиянием (Merge-Sort)

Рейтинг:  3 / 5

Звезда активнаЗвезда активнаЗвезда активнаЗвезда не активнаЗвезда не активна
 

Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

 

  1. массив рекурсивно разбивается пополам, и каждая из половин делиться до тех пор, пока размер очередного подмассива не станет равным единице;
  2. далее выполняется операция алгоритма, называемая слиянием. Два единичных массива сливаются в общий результирующий массив, при этом из каждого выбирается меньший элемент (сортировка по возрастанию) и записывается в свободную левую ячейку результирующего массива. После чего из двух результирующих массивов собирается третий общий отсортированный массив, и так далее. В случае если один из массивов закончиться, элементы другого дописываются в собираемый массив;
  3. в конце операции слияния, элементы перезаписываются из результирующего массива в исходный.

 

 

 

 

Худшее время

O(n log n)

Лучшее время

O(n log n) обычно, O(n) на упорядоченном массиве

Среднее время

O(n log n)

Затраты памяти

O(n) вспомогательных

 

 

Реализация алгоритма на различных языках программирования:

 

C++

 

               /**
                * @brief         Сортировка элементов от l до r массива buf
                * @param[in/out] buf - сортируемый массив
                * @param[in]     l - левая граница. При первой итерации l = 0
                * @param[in]     r - правая граница. При первой итерации r = buf.size() - 1
                *
                * В результате сортируются все элементы массива buf от l до r включительно.
                */
               template<typename Type>
void MergeSort(vector<Type>& buf, size_t l, size_t r)
{
    //! Условие выхода из рекурсии
    if(l >= r) return;
 
    size_t m = (l + r) / 2;
 
    //! Рекурсивная сортировка полученных массивов
    MergeSort(buf, l, m);
    MergeSort(buf, m+1, r);
    merge(buf, l, r, m);
}
 
/**
 * @brief Слияние элементов.
 * @param[in/out] buf - массив
 * @param[in]     l - левая граница. При певой итерации l = 0
 * @param[in]     r - правая граница. При первой итерации r = buf.size() - 1
 * @param[in]     m - граница подмассивов.
 *
 * Массив buf содержит два отсортированных подмассива:
 * - [l; m] - первый отсортированный подмассив.
 * - [m+1; r] - второй отсортированный подмассив.
 * В результате получаем отсортированный массив, полученный из двух подмассивов,
 * который сохраняется в buf[l; r].
 */
template<typename Type>
static void merge(vector<Type>& buf, size_t l, size_t r, size_t m)
{
    if (l >= r || m < l || m > r) return;
    if (r == l + 1 && buf[l] > buf[r]) {
        swap(buf[l], buf[r]);
        return;
    }
 
    vector<Type> tmp(&buf[l], &buf[l] + (r + 1));
 
    for (size_t i = l, j = 0, k = m - l + 1; i <= r; ++i) {
        if (j > m - l) {      
            buf[i] = tmp[k++];
        } else if(k > r - l) {
            buf[i] = tmp[j++];
        } else {
            buf[i] = (tmp[j] < tmp[k]) ? tmp[j++] : tmp[k++];
        }
    }
}

 

Существует также итеративный алгоритм сортировки, избавленный от рекурсивных вызовов. Такой алгоритм называют «Восходящей сортировкой слиянием».

 

// Слияние двух упорядоченных массивов
// m1 - Первый массив
// m2 - Второй массив
// l1 - Длина первого массива
// l2 - Длина второго массива
// Возвращает объединённый массив
               template <class T>
T* merge(T *m1, T* m2, int l1, int l2)
{
    T* ret = new T[l1+l2];
    int n = 0;
    // Сливаем массивы, пока один не закончится
    while (l1 && l2) {
        if (*m1 < *m2) {
            ret[n] = *m1;
            m1++;
            --l1;
        } else {
            ret[n] = *m2;
            ++m2;
            --l2;
        }
        ++n;
    }
    // Если закончился первый массив
    if (l1 == 0) {
        for (int i = 0; i < l2; ++i) {
            ret[n++] = *m2++;
        }
    } else { // Если закончился второй массив
        for (int i = 0; i < l1; ++i) {
            ret[n++] = *m1++;
        }
    }
    return ret;
}
 
// Функция восходящего слияния
template <class T>
void mergeSort(T * mas, int len)
{
    int n = 1, l, ost;
    T * mas1;
    while (n < len) {
        l = 0;
        while (l < len) {
            if (l + n >= len) break;
            ost = (l + n * 2 > len) ? (len - (l + n)) : n;
            mas1 = merge(mas + l, mas + l + n, n, ost);
            for (int i = 0; i < n + ost; ++i)
                mas[l+i] = mas1[i];//тут нужно что-то поменять, потому что это лишнее копирование, и оно увеличивает время работы алгоритма в два раза
            delete [] mas1;
            l += n * 2;
        }
        n *= 2;
    }
}

 

Пример: char a[] = "ASORTINGEXAMPLE"; mergeSort(a, 16); Альтернативная версия алгоритма Сортировки Слиянием.

 template <typename Item>
void Merge(Item Mas[], int left, int right, int medium)
{
    int j = left;
    int k = medium + 1;
    int count = right - left + 1;
 
    if (count <= 1) return;
 
    Item *TmpMas = new Item[count];
 
    for (int i = 0; i < count; ++i) {
        if (j <= medium && k <= right) {
            if (Mas[j] < Mas[k])
                TmpMas[i] = Mas[j++];
            else
                TmpMas[i] = Mas[k++];
        } else {
            if (j <= medium)
                TmpMas[i] = Mas[j++];
            else
                TmpMas[i] = Mas[k++];
        }
    }
 
    j = 0;
    for (int i = left; i <= right; ++i) {
        Mas[i] = TmpMas[j++];
    }
    delete[] TmpMas;
}
 
template <typename Item>
void MergeSort(Item a[], int l, int r)
{
    int m;
 
    // Условие выхода из рекурсии
    if(l >= r) return;
 
    m = (l + r) / 2;
 
    // Рекурсивная сортировка полученных массивов
    MergeSort(a, l, m);
    MergeSort(a, m + 1, r);
    Merge(a, l, r, m);
}

 

C#

 static Int32[] Merge_Sort(Int32[] massive)
        {
            if (massive.Length == 1)
                return massive;
            Int32 mid_point = massive.Length / 2;
            return Merge(Merge_Sort(massive.Take(mid_point).ToArray()), Merge_Sort(massive.Skip(mid_point).ToArray()));
        }
 
        static Int32[] Merge(Int32[] mass1, Int32[] mass2)
        {
            Int32 a = 0, b = 0;
            Int32[] merged = new int[mass1.Length + mass2.Length];
            for (Int32 i = 0; i < mass1.Length + mass2.Length; i++)
            {
                if (b < mass2.Length && a < mass1.Length)
                    if (mass1[a] > mass2[b])
                        merged[i] = mass2[b++];
                    else //if int go for
                        merged[i] = mass1[a++];
                else
                    if (b < mass2.Length)
                        merged[i] = mass2[b++];
                    else
                        merged[i] = mass1[a++];
            }
            return merged;
        }
 
    static void Main(string[] args)
        {
              Int32[] arr = new Int32[100];
              //заполняем массив случайными числами
              Random rd = new Random();
              for(Int32 i = 0; i < arr.Length; ++i) {
                 arr[i] = rd.Next(1, 101);
              }
              System.Console.WriteLine("The array before sorting:");
              foreach (Int32 x in arr)
              {
                 System.Console.Write(x + " ");
              }
              //сортировка
 
              arr = Merge_Sort(arr);
 
              System.Console.WriteLine("\n\nThe array after sorting:");
              foreach (Int32 x in arr)
              {
                 System.Console.Write(x + " ");
              }
              System.Console.WriteLine("\n\nPress the <Enter> key");
              System.Console.ReadLine();
        }

 

C#

//предыдущий пример сортирует лишь целые числа. Следующий - работает со всеми типами данных. 
static IComparable[] Merge_Sort(IComparable[] massive)
        {
            if (massive.Length == 1)
                return massive;
            int mid_point = massive.Length / 2;
            return Merge(Merge_Sort(massive.Take(mid_point).ToArray()), Merge_Sort(massive.Skip(mid_point).ToArray()));
        }
        static IComparable[] Merge(IComparable[] mass1, IComparable[] mass2)
        {
            int a = 0, b = 0;
            IComparable[] merged = new IComparable[mass1.Length + mass2.Length];
            for (int i = 0; i < mass1.Length + mass2.Length; i++)
            {
                if (b.CompareTo(mass2.Length) < 0 && a.CompareTo(mass1.Length) < 0)
                    if (mass1[a].CompareTo(mass2[b]) > 0)
                        merged[i] = mass2[b++];
                    else
                        merged[i] = mass1[a++];
                else
                    if (b < mass2.Length)
                        merged[i] = mass2[b++];
                    else
                        merged[i] += mass1[a++];
            }
            return merged;
        }
        static void Main(string[] args)
        {
            IComparable[] arr = new IComparable[100];
            Random rd = new Random();
            for (int i = 0; i < arr.Length; ++i)
                arr[i] = rd.Next(1, 101);
            Console.WriteLine("Массив перед сортировкой:");
            foreach (int x in arr)
                System.Console.Write(x + " ");
            arr = Merge_Sort(arr);
            Console.WriteLine("\n\nМассив после сортировки:");
            foreach (int x in arr)
                System.Console.Write(x + " ");
            Console.WriteLine("\n\nДля выхода нажмите <Enter>.");
            Console.ReadKey();
        }

Perl

@out=(5,2,8,9,4,2,7,9,4,1,6,9,0);
sub sortM{
    my($array,$first,$last)=@_;
    if($last>$first){
	my$middle=int(($last+$first)/2);
	sortM($array,$first,$middle);
	sortM($array,$middle+1,$last);
	my$j=0;
	$work[$j++]=$$array[$_]for($first..$last);
	$middle=int(($first+$last)/2)if($middle>$last);
	my$n=$middle-$first+1;
	for($i=$first,$j=0,$k=$n;$i<=$last;$i++){
	    if(($j<$n)&&(($k==(($last-$first)+1))||($work[$j]lt$work[$k]))){
		$$array[$i]=$work[$j++]
	    }else{
		$$array[$i]=$work[$k++];
	    }
	}
    }
}
sortM(\@out,0,$#out+1);

 

Паскаль (сортировка текстовых файлов)

 

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

 

Procedure MergeSort(name: string; var f: text);
          Var a1,a2,s,i,j,kol,tmp: integer;
              f1,f2: text;
              b: boolean;
          Begin
             kol:=0;
 
             Assign(f,name);
             Reset(f);
             While not EOF(f) do
               begin
                 read(f,a1);
                 inc(kol);
               End;
             Close(f);
 
             Assign(f1,'{имя 1-го вспомогательного файла}');
             Assign(f2,'{имя 2-го вспомогательного файла}');
 
             s:=1;
             While (s<kol) do
               begin
 
                 Reset(f); Rewrite(f1); Rewrite(f2);
                 For i:=1 to kol div 2 do
                   begin
                     Read(f,a1);
                     Write(f1,a1,' ');
                   End;
                 If (kol div 2) mod s<>0 then
                   begin
                     tmp:=kol div 2;
                     While tmp mod s<>0 do
                       begin
                         Read(f,a1);
                         Write(f1,a1,' ');
                         inc(tmp);
                       End;
                   End;
                 While not EOF(f) do
                   begin
                     Read(f,a2);
                     Write(f2,a2,' ');
                   End;
                 Close(f); Close(f1); Close(f2);
 
 
                 Rewrite(f); Reset(f1); Reset(f2);
                 Read(f1,a1);
                 Read(f2,a2);
                 While (not EOF(f1)) and (not EOF(f2)) do
                   begin
                     i:=0; j:=0;
                     b:=true;
                     While (b) and (not EOF(f1)) and (not EOF(f2)) do
                       begin
                         If (a1<a2) then
                           begin
                             Write(f,a1,' ');
                             Read(f1,a1);
                             inc(i);
                           End
                         else
                           begin
                             Write(f,a2,' ');
                             Read(f2,a2);
                             inc(j);
                           End;
                         If (i=s) or (j=s) then b:=false;
                       End;
                     If not b then
                       begin
                         While (i<s) and (not EOF(f1)) do
                           begin
                             Write(f,a1,' ');
                             Read(f1,a1);
                             inc(i);
                           End;
                         While (j<s) and (not EOF(f2)) do
                           begin
                             Write(f,a2,' ');
                             Read(f2,a2);
                             inc(j);
                           End;
                       End;
                   End;
                 While not EOF(f1) do
                   begin
                     tmp:=a1;
                     Read(f1,a1);
                     If not EOF(f1) then
                       Write(f,tmp,' ')
                     else
                       Write(f,tmp);
                   End;
                 While not EOF(f2) do
                   begin
                     tmp:=a2;
                     Read(f2,a2);
                     If not EOF(f2) then
                       Write(f,tmp,' ')
                     else
                       Write(f,tmp);
                   End;
                 Close(f); Close(f1); Close(f2);
 
                 s:=s*2;
               End;
             Erase(f1);
             Erase(f2);
          End;

 

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

Procedure MergeSort(name: string; var f: text);
          Var s1,s2,a1,a2,where,tmp: integer;
              f1,f2: text;
          Begin
             s1:=5; s2:=5; {Можно задать любые числа, которые запустят цикл while}
             Assign(f,name);
             Assign(f1,'{имя 1-го вспомогательного файла}');
             Assign(f2,'{имя 2-го вспомогательного файла}');
             While (s1>1) and (s2>=1) do
               begin
                 where:=1;
                 s1:=0; s2:=0;
                 Reset(f); Rewrite(f1); Rewrite(f2);
                 Read(f,a1);
                 Write(f1,a1,' ');
                 While not EOF(f) do
                   begin
                     read(f,a2);
                     If (a2<a1) then
                       begin
                         Case where of
                            1: begin
                                 where:=2;
                                 inc(s1);
                               End;
                            2: begin
                                 where:=1;
                                 inc(s2);
                               End;
                         End;
                       End;
                     Case where of
                        1: write(f1,a2,' ');
                        2: write(f2,a2,' ');
                     End;
                     a1:=a2;
                   End;
                 If where=2 then
                   inc(s2)
                 else
                   inc(s1);
                 Close(f); Close(f1); Close(f2);
 
 
                 Rewrite(f); Reset(f1); Reset(f2);
                 Read(f1,a1);
                 Read(f2,a2);
                 While (not EOF(f1)) and (not EOF(f2)) do
                   begin
                     If (a1<=a2) then
                       begin
                         Write(f,a1,' ');
                         Read(f1,a1);
                       End
                     else
                       begin
                         Write(f,a2,' ');
                         Read(f2,a2);
                       End;
                   End;
                 While not EOF(f1) do
                   begin
                     tmp:=a1;
                     Read(f1,a1);
                     If not EOF(f1) then
                        Write(f,tmp,' ')
                     else
                        Write(f,tmp);
                   End;
                 While not EOF(f2) do
                   begin
                     tmp:=a2;
                     Read(f2,a2);
                     If not EOF(f2) then
                        Write(f,tmp,' ')
                     else
                        Write(f,tmp);
                   End;
                 Close(f); Close(f1); Close(f2);
               End;
             Erase(f1);
             Erase(f2);
          End;

 

Delphi (сортировка произвольных типов данных - простое слияние)

unit uMergeSort;
 
interface
type
  TItem = Integer;               //Здесь можно написать Ваш произвольный тип
  TArray = array of TItem;
 
  procedure MergeSort(var Arr: TArray);
 
implementation
 
function IsBigger(d1, d2 : TItem) : Boolean;
begin
  Result := (d1 > d2);     //Сравниваем d1 и d2. Не обязательно так. Зависит от Вашего типа.
  //Сюда можно добавить счетчик сравнений
end;
 
//Процедура сортировки слияниями
procedure MergeSort(var Arr: TArray);
var
  tmp : TArray; //Временный буфер
  //Слияние
  procedure merge(L, Spl, R : Integer);
  var
    i, j, k : Integer;
  begin
    i := L;
    j := Spl + 1;
    k := 0;
    //Выбираем меньший из первых и добавляем в tmp
    while (i <= Spl) and (j <=R) do
    begin
      if IsBigger(Arr[i], Arr[j]) then
      begin
        tmp[k] := Arr[j];
        Inc(j);
      end
      else
      begin
        tmp[k] := Arr[i];
        Inc(i);
      end;
      Inc(k);
    end;
    //Просто дописываем в tmp оставшиеся эл-ты
    if i <= Spl then      //Если первая часть не пуста
      for j := i to Spl do
      begin
        tmp[k] := Arr[j];
        Inc(k);
      end
    else                  //Если вторая часть не пуста
      for i := j to R do
      begin
        tmp[k] := Arr[i];
        Inc(k);
      end;
    //Перемещаем из tmp в arr
    Move(tmp[0], Arr[L], k*SizeOf(TItem));
  end;
 
  //Сортировка
  procedure sort(L, R : Integer);
  var
    splitter : Integer;
  begin
    //Массив из 1-го эл-та упорядочен по определению
    if L >= R then Exit;
    splitter := (L + R) div 2;  //Делим массив пополам
    sort(L, splitter);          //Сортируем каждую
    sort(splitter + 1, R);      //часть по отдельности
    merge(L, splitter, R);      //Производим слияние
  end;
 
  //Основная часть процедуры сортировки
begin
  SetLength(tmp, Length(Arr));
  sort(0, Length(Arr) - 1);
  SetLength(tmp, 0);
end;
 
end.

 

D

void mergeSort(int[] array) {
    static void merge(int[] array, int q) {
        int[] leftArray = array[0..q].dup ~ int.max;
        int[] rightArray = array[q..$].dup ~ int.max;
        int i = 0;
        int j = 0;
        int length = array.length;
        for (int k = 0; k < length; ++k) {
            array[k] = (leftArray[i] <= rightArray[j]) ? leftArray[i++] : rightArray[j++];
        }
    }
 
    if (array.length > 1) {
        int q = array.length / 2;
        mergeSort(array[0..q]);
        mergeSort(array[q..$]);
        merge(array, q);
    }
}

 

Python 2.7 (функциональная реализация)

def merge(right, left, result):
    result.append((left if left[0] < right[0] else right).pop(0))
    return merge(right=right, left=left, result=result) if left and right else result+left+right
 
merge_sort = (lambda arr: arr if len(arr) == 1 else merge(merge_sort(arr[len(arr)/2:]),
                                                          merge_sort(arr[:len(arr)/2]), []))

 

 

 Недостатком сортировки слиянием является использование дополнительной памяти. Но когда работать приходиться с файлами или списками, доступ к которым осуществляется только последовательно, то очень удобно применять именно этот метод. Также, к достоинствам алгоритма стоит отнести его устойчивость и неплохую скорость работы O(n*logn).

 

При написании статьи были использованы открытые источники сети интернет :

Wikipedia

Kvodo

Youtube 

 

 

 

 




Реклама



Ваше мнение

Видиотека

Рейтинг@Mail.ru

Яндекс.Метрика