Метод сортировки массива слиянием трех. Алгоритмы и структуры данных для начинающих: сортировка
Было подсчитано, что до четверти времени централизованных компьютеров уделяется сортировке данных. Это потому, что намного легче найти значение в массиве, который был заранее отсортирован. В противном случае поиск немного походит на поиск иголки в стоге сена.
Есть программисты, которые всё рабочее время проводят в изучении и внедрении алгоритмов сортировки. Это потому, что подавляющее большинство программ в бизнесе включает в себя управление базами данных. Люди ищут информацию в базах данных всё время. Это означает, что поисковые алгоритмы очень востребованы.
Но есть одно "но". Поисковые алгоритмы работают намного быстрее с базами данных, которые уже отсортированы. В этом случае требуется только линейный поиск.
В то время как компьютеры находятся без пользователей в некоторые моменты времени, алгоритмы сортировки продолжают работать с базами данных. Снова приходят пользователи, осуществляющие поиск, а база данных уже отсортирована, исходя из той или иной цели поиска.
В этой статье приведены примеры реализации стандартных алгоритмов сортировки.
Сортировка выбором (Selection sort)
Для того, чтобы отсортировать массив в порядке возрастания, следует на каждой итерации найти элемент с наибольшим значением. С ним нужно поменять местами последний элемент. Следующий элемент с наибольшим значением становится уже на предпоследнее место. Так должно происходить, пока элементы, находящиеся на первых местах в массивe, не окажутся в надлежащем порядке.
Код C++
void
SortAlgo::selectionSort(int
data, int
lenD)
{
int
j = 0;
int
tmp = 0;
for
(int
i=0; i
Пузырьковая сортировка (Bubble sort)
При пузырьковой сортировке сравниваются соседние элементы и меняются местами, если следующий элемент меньше предыдущего. Требуется несколько проходов по данным. Во время первого прохода сраваются первые два элемента в массиве. Если они не в порядке, они меняются местами и затем сравнивается элементы в следующей паре. При том же условии они так же меняются местами. Таким образом сортировка происходит в каждом цикле пока не будет достигнут конец массива.
Код C++
void
SortAlgo::bubbleSort(int
data, int
lenD)
{
int
tmp = 0;
for
(int
i = 0;i При сортировке вставками массив разбивается на две области: упорядоченную и
и неупорядоченную. Изначально весь массив является неупорядоченной областью.
При первом проходе первый элемент из неупорядоченной области изымается и помещается
в правильном положении в упорядоченной области. На каждом проходе размер упорядоченной области возрастает на 1, а размер неупорядоченной
области сокращается на 1. Основной цикл работает в интервале от 1 до N-1. На j-й итерации элемент [i] вставлен в
правильное положение в упорядоченной области. Это сделано путем сдвига всех
элементов упорядоченной области, которые больше, чем [i], на одну позицию вправо. [i]
вставляется в интервал между теми элементами, которые меньше [i], и теми, которые больше [i]. Код C++
void
SortAlgo::insertionSort(int
data, int
lenD)
{
int
key = 0;
int
i = 0;
for
(int
j = 1;j Код C++
void
SortAlgo::mergeSort(int
data, int
lenD)
{
if
(lenD>1){
int
middle = lenD/2;
int
rem = lenD-middle;
int
* L = new int
;
int
* R = new int
;
for
(int
i=0;i Быстрая сортировка использует алгоритм "разделяй и властвуй". Она начинается с разбиения
исходного массива на две области. Эти части находятся слева и справа от отмеченного
элемента, называемого опорным. В конце процесса одна часть будет
содержать элементы меньшие, чем опорный, а другая часть будет содержать элементы больше
опорного. Код C++
void
SortAlgo::quickSort(int
* data, int const
len)
{
int const
lenD = len;
int
pivot = 0;
int
ind = lenD/2;
int
i,j = 0,k = 0;
if
(lenD>1){
int
* L = new int
;
int
* R = new int
;
pivot = data;
for
(i=0;i Сортировка слиянием (англ. merge sort
) - алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например - потоки) в определённом порядке. Эта сортировка - хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
Реализация алгоритма на различных языках программирования:
Существует также итеративный алгоритм сортировки, избавленный от рекурсивных вызовов. Такой алгоритм называют «Восходящей сортировкой слиянием». // Слияние двух упорядоченных массивов
// m1 - Первый массив
// m2 - Второй массив
// l1 - Длина первого массива
// l2 - Длина второго массива
// Возвращает объединённый массив
template Пример: char a = "ASORTINGEXAMPLE"; mergeSort(a, 16); Альтернативная версия алгоритма Сортировки Слиянием. Template 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;
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;
else //if int go for
merged[i] = mass1;
else
if (b < mass2.Length)
merged[i] = mass2;
else
merged[i] = mass1;
}
return merged;
}
static void Main(string args)
{
Int32 arr = new Int32;
//заполняем массив случайными числами
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 @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 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 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, 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.dup ~ int.max;
int rightArray = array.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 : rightArray;
}
}
if (array.length > 1) {
int q = array.length / 2;
mergeSort(array);
mergeSort(array);
merge(array, q);
}
} Def merge(right, left, result):
result.append((left if left < right 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),
merge_sort(arr[:len(arr)/2]), )) Недостатком сортировки слиянием является использование дополнительной памяти. Но когда работать приходиться с файлами или списками, доступ к которым осуществляется только последовательно, то очень удобно применять именно этот метод. Также, к достоинствам алгоритма стоит отнести его устойчивость и неплохую скорость работы O(n*logn).
При написании статьи были использованы открытые источники сети интернет:
Алгоритм сортировки слиянием
был предложен праотцом современных компьютеров – Джоном фон Нейманом. Сам метод является устойчивым, т. е. он не меняет одинаковые по значению элементы в списке. В основе сортировки слиянием лежит принцип «разделяй и властвуй». Список разделяется на равные или практически равные части, каждая из которых сортируется отдельно. После чего уже упорядоченные части сливаются воедино. Несколько детально этот процесс можно расписать так: 1. массив рекурсивно разбивается пополам, и каждая из половин делиться до тех пор, пока размер очередного подмассива не станет равным единице; 2. далее, выполняется операция алгоритма, называемая слиянием. Два единичных массива сливаются в общий результирующий массив, при этом из каждого выбирается меньший элемент (сортировка по возрастанию) и записывается в свободную левую ячейку результирующего массива. После чего из двух результирующих массивов собирается третий общий отсортированный массив, и так далее. В случае если один из массивов закончиться, элементы другого дописываются в собираемый массив; 3. в конце операции слияния, элементы перезаписываются из результирующего массива в исходный. Подпрограмма MergeSort
рекурсивно разбивает и сортирует массив, а Merge
отвечает за его слияние. Так можно записать псевдокод основной подпрограммы: Подпрограмма MergeSort
(A
, first
, last
) A
– массив first
, last
– номера первого и последнего элементов соответственно Если first
<last
то Вызов MergeSort
(A
, first
, (first
+last
)/2) //сортировка левой части Вызов MergeSort
(A
, (first
+last
)/2+1, last
) //сортировка правой части Вызов Merge
(A
, first
, last
) //слияние двух частей Эта подпрограмма выполняется только в том случае, если номер первого элемента меньше номера последнего. Как уже говорилось, из подпрограммы MergeSort
вызывается подпрограмма Merge
, которая выполняет операцию слияния. Перейдем к рассмотрению последней. Работа Merge
заключается в образовании упорядоченного результирующего массива путем слияния двух также отсортированных массивов меньших размеров. Вот псевдокод этой подпрограммы: Подпрограмма Merge
(A
, first
, last
) start
, final
– номера первых элементов левой и правой частей mas
– массив, middle
- хранит номер среднего элемента middle
=(first+last)/2 //вычисление среднего элемента start
=first
//начало левой части final
=middle
+1 //начало правой части Цикл j
=first
до last
выполнять //выполнять от начала до конца Если ((start
<=middle
) и ((final
>last
) или (A
[start
]<A
[final
]))) то mas
[j
]=A
[start
] увеличить start
на 1 mas
[j
]=A
[final
] увеличить final
на 1 Цикл j
=first
до last
выполнять //возвращение результата в список A
[j
]=mas
[j
] Разберем алгоритм сортировки слиянием на следующем примере (рис. 6.10). Имеется неупорядоченная последовательность чисел: 2, 6, 7, 1, 3, 5, 0, 4. После разбивки данной последовательности на единичные массивы, процесс сортирующего слияния (по возрастанию) будет выглядеть так: Рисунок 6.10 – Пример сортировки слиянием Массив был разделен на единичные массивы, которые алгоритм сливает попарно до тех пор, пока не получится один массив, все элементы которого стоят на своих позициях. Код программы на C++: void Merge(int *A, int first, int last) //функция, сливающая массивы int middle, start, final, j; int *mas=new int; middle=(first+last)/2; //вычисление среднего элемента start=first; //начало левой части final=middle+1; //начало правой части for(j=first; j<=last; j++) //выполнять от начала до конца if ((start<=middle) && ((final>last) || (A
mas[j]=A; mas[j]=A; for (j=first; j<=last; j++) A[j]=mas[j]; //возвращение результата в список void MergeSort(int *A, int first, int last) //рекурсивная процедура сортировки if (first MergeSort(A, first, (first+last)/2); //сортировка левой части MergeSort(A, (first+last)/2+1, last); //сортировка правой части Merge(A, first, last); //слияние двух частей void main() //главная функция cout<<"Размер массива > "; cin>>n; for (i=1; i<=n; i++) cout< "; MergeSort(A, 1, n); //вызов сортирующей процедуры cout<<"Упорядоченный массив: "; //вывод упорядоченного массиваСортировка вставками (Insertion sort)
Сортировка слиянием (Merge sort)
Быстрая сортировка (Quick sort)
C++
/**
* @brief Сортировка элементов от l до r массива buf
* @param buf - сортируемый массив
* @param l - левая граница. При первой итерации l = 0
* @param r - правая граница. При первой итерации r = buf.size() - 1
*
* В результате сортируются все элементы массива buf от l до r включительно.
*/
templateC#
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;
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;
else
merged[i] = mass1;
else
if (b < mass2.Length)
merged[i] = mass2;
else
merged[i] += mass1;
}
return merged;
}
static void Main(string args)
{
IComparable arr = new IComparable;
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Для выхода нажмите Perl
Паскаль (сортировка текстовых файлов)
Сортировка простым слиянием
Сортировка естественным слиянием
Delphi (сортировка произвольных типов данных - простое слияние)
D
Python 2.7 (функциональная реализация)