Реализации алгоритмов/Сортировка/Слиянием
(перенаправлено с «Примеры реализации сортировки слиянием»)
/**
* @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;
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);
}
}
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]), []))
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;
----------------------------------------------------------------------------------------------