Перейти к содержанию

Реализации алгоритмов/Сортировка/Слиянием

Материал из Викиучебника — открытых книг для открытого мира
/**
* @brief         Сортировка элементов от left до right массива buf
* @param[in/out] buf - сортируемый массив
* @param[in]     left - левая граница. При первой итерации left = 0
* @param[in]     right - правая граница. При первой итерации right = buf.size() - 1
*
* В результате сортируются все элементы массива buf от left до right включительно.
*/
template<typename Type>
void MergeSort(vector<Type>& buf, size_t left, size_t right)
{
    //! Условие выхода из рекурсии
    if(left >= right) return;

    size_t middle = left + (right - left) / 2;

    //! Рекурсивная сортировка полученных массивов
    MergeSort(buf, left, middle);
    MergeSort(buf, middle + 1, right);
    merge(buf, left, right, middle);
}

/**
 * @brief Слияние элементов.
 * @param[in/out] buf - массив
 * @param[in]     left - левая граница. При певой итерации left = 0
 * @param[in]     right - правая граница. При первой итерации right = buf.size() - 1
 * @param[in]     middle - граница подмассивов.
 *
 * Массив buf содержит два отсортированных подмассива:
 * - [left; middle] - первый отсортированный подмассив.
 * - [middle+1; right] - второй отсортированный подмассив.
 * В результате получаем отсортированный массив, полученный из двух подмассивов,
 * который сохраняется в buf[left; right].
 */
template<typename Type>
static void merge(vector<Type>& buf, size_t left, size_t right, size_t middle)
{
    if (left >= right || middle < left || middle > right) return;
    if (right == left + 1 && buf[left] > buf[right]) {
        swap(buf[left], buf[right]);
        return;
    }

    vector<Type> tmp(&buf[left], &buf[right] + 1));

    for (size_t i = left, j = 0, k = middle - left + 1; i <= right; ++i) {
        if (j > middle - left) {      
            buf[i] = tmp[k++];
        } else if(k > right - left) {
            buf[i] = tmp[j++];
        } else {
            buf[i] = (tmp[j] < tmp[k]) ? tmp[j++] : tmp[k++];
        }
    }
}

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

/*
* Слияние двух упорядоченных массивов
* m1 - Первый массив
* m2 - Второй массив
* len_1 - Длина первого массива
* len_2 - Длина второго массива
* Возвращает объединённый массив
*/
template <class T>
T* merge(T *m1, T* m2, int len_1, int len_2)
{
    T* ret = new T[len_1+len_2];
    int n = 0;
    // Сливаем массивы, пока один не закончится
    while (len_1 && len_2) {
        if (*m1 < *m2) {
            ret[n] = *m1;
            m1++;
            --len_1;
        } else {
            ret[n] = *m2;
            ++m2;
            --len_2;
        }
        ++n;
    }
    // Если закончился первый массив
    if (len_1 == 0) {
        for (int i = 0; i < len_2; ++i) {
            ret[n++] = *m2++;
        }
    } else { // Если закончился второй массив
        for (int i = 0; i < len_1; ++i) {
            ret[n++] = *m1++;
        }
    }
    return ret;
}

// Функция восходящего слияния
template <class T>
void mergeSort(T * mas, int len)
{
    int n = 1, k, ost;
    T * mas1;
    while (n < len) {
        k = 0;
        while (k < len) {
            if (k + n >= len) break;
            ost = (k + n * 2 > len) ? (len - (k + n)) : n;
            mas1 = merge(mas + k, mas + k + n, n, ost);
            for (int i = 0; i < n + ost; ++i)
                mas[k+i] = mas1[i];//тут нужно что-то поменять, потому что это лишнее копирование, и оно увеличивает время работы алгоритма в два раза
            delete [] mas1;
            k += 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 left, int right)
{
    int middle;

    // Условие выхода из рекурсии
    if(left >= right) return;

    middle = left + (right - left) / 2;

    // Рекурсивная сортировка полученных массивов
    MergeSort(a, left, middle);
    MergeSort(a, middle + 1, right);
    Merge(a, left, right, middle);
}
static Int32[] MergeSort(Int32[] array)
{
	if (array.Length == 1)
	{
		return array;
	}

	Int32 middle = array.Length / 2;
	return Merge(MergeSort(array.Take(middle).ToArray()), MergeSort(array.Skip(middle).ToArray()));
}

static Int32[] Merge(Int32[] arr1, Int32[] arr2)
{
	Int32 ptr1 = 0, ptr2 = 0;
	Int32[] merged = new Int32[arr1.Length + arr2.Length];

	for (Int32 i = 0; i < merged.Length; ++i)
	{
		if (ptr1 < arr1.Length && ptr2 < arr2.Length)
		{
			merged[i] = arr1[ptr1] > arr2[ptr2] ? arr2[ptr2++] : arr1[ptr1++];
		}
		else
		{
			merged[i] = ptr2 < arr2.Length ? arr2[ptr2++] : arr1[ptr1++];
		}
	}
		
	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 = MergeSort(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();
}
//предыдущий пример сортирует лишь целые числа. Следующий - работает со всеми типами данных. 
class Class1
{
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 = Class1.Merge_Sort(arr);
    Console.WriteLine("\n\nМассив после сортировки:");
    foreach (int x in arr)
        System.Console.Write(x + " ");
    Console.WriteLine("\n\nДля выхода нажмите <Enter>.");
    Console.ReadKey();
}

Реализация на языке Clojure

(defn merge-sort
  "sorting the given collection with merge-sort"
  [coll]
  (if (or (empty? coll) (= 1 (count coll)))
    coll
    (let [[l1 l2] (split-at (/ (count coll) 2) coll)]
      ;recursive call
      (loop [r [] l1 (merge-sort l1) l2 (merge-sort l2)]
        ;merging
        (cond (empty? l1) (into r l2) ;when l1 is exhausted
              (empty? l2) (into r l1) ;when l2 is exhausted
              :else (if (> 0 (compare (first l1) (first l2))) ;comparison
                      (recur (conj r (first l1)) (rest l1) l2)
                      (recur (conj r (first l2)) l1 (rest l2))))))))
@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.
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);
    }
}

Java (Рекурсивная и нерекурсивная реализации)

[править]
private static int[] sortMerge(int[] arr) {
	int len = arr.length;
	if (len < 2) return arr;
	int middle = len / 2;
	return merge(sortMerge(Arrays.copyOfRange(arr, 0, middle)),
	             sortMerge(Arrays.copyOfRange(arr, middle, len)));
}

private static void sortMergeNoRecursive(int[] arr) {
	int len = arr.length;
	int n = 1; // кратность сравнений (сравнивать по 1-му элем., 2-м ...)
	int shift; // сдвиг в перебираемом массиве
	int two_size; // количество элементов для 2-го массива
	int[] arr2;
	while (n < len) {
		shift = 0;
		while (shift < len) {
			if (shift + n >= len) break;
			two_size = (shift + n * 2 > len) ? (len - (shift + n)) : n;
			arr2 = merge(Arrays.copyOfRange(arr, shift, shift + n),
			             Arrays.copyOfRange(arr, shift + n, shift + n + two_size));
			for (int i = 0; i < n + two_size; ++i)
			arr[shift + i] = arr2[i]; // замена на отсортированное
			shift += n * 2;
		}
		n *= 2;
	}
}

private static int[] merge(int[] arr_1, int[] arr_2) {
	int len_1 = arr_1.length, len_2 = arr_2.length;
	int a = 0, b = 0, len = len_1 + len_2; // a, b - счетчики в массивах
	int[] result = new int[len];
	for (int i = 0; i < len; i++) {
		if (b < len_2 && a < len_1) {
			if (arr_1[a] > arr_2[b]) result[i] = arr_2[b++];
			else result[i] = arr_1[a++];
		} else if (b < len_2) {
			result[i] = arr_2[b++];
		} else {
			result[i] = arr_1[a++];
		}
	}
	return result;
}

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]), []))

PL/SQL (процедурная реализация)

[править]
type sort_lst is table of integer;
---------------------------сортировка слиянием---------------------------------------
Function mergesort (in_list IN sort_lst) return sort_lst
  IS
    l_left sort_lst := sort_lst();
    l_right sort_lst := sort_lst();
    l_middle pls_integer;
    l_res sort_lst;
begin
    if in_list.count <= 1 then 
        l_res:=in_list;
    else
        l_middle := in_list.count/2;
        
        for i in in_list.first..in_list.last loop
            if i <= l_middle then
                l_left.extend;
                l_left(l_left.last):=in_list(i);
            else
                l_right.extend;
                l_right(l_right.last):=in_list(i);
            end if;
        end loop;

        l_left:=mergesort(l_left);
        l_right:=mergesort(l_right);
        l_res:=merge2(l_left, l_right);
            
    end if;
    return l_res;     
       
end mergesort;
-----------------------------------------------------------------------------------
function merge2(in_left IN sort_lst, in_right IN sort_lst) return sort_lst
  IS
   l_left sort_lst:=sort_lst();
   l_right sort_lst:=sort_lst();
   l_res sort_lst:=sort_lst();
  begin 
     l_left:= in_left; l_right:=in_right;
     
  while ((l_left.count > 0) and (l_right.count > 0)) loop
        if l_left(l_left.first) <= l_right(l_right.first) then
            l_res.extend;
            l_res(l_res.last):= l_left(l_left.first);
            l_left.delete(l_left.first);
        else
            l_res.extend;
            l_res(l_res.last):= l_right(l_right.first);
            l_right.delete(l_right.first);     
        end if;         
  end loop;
  
  if (l_left.count > 0) then --если левый подмассив не пуст, весь дописываем в результат
     for i in l_left.first..l_left.last loop
        l_res.extend;
        l_res(l_res.last):= l_left(i); 
     end loop;     
  end if;
  
  if (l_right.count > 0) then --если правый подмассив не пуст, весь дописываем в результат
      for i in l_right.first..l_right.last loop
       l_res.extend;
       l_res(l_res.last):= l_right(i);
      end loop;
  end if;

    return l_res;
          
end merge2;
----------------------------------------------------------------------------------------------