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

1 23

Алгоритм сортировки слиянием был предложен праотцом современных компьютеров – Джоном фон Нейманом. Сам метод является устойчивым, т. е. он не меняет одинаковые по значению элементы в списке.

В основе сортировки слиянием лежит принцип «разделяй и властвуй». Список разделяется на равные или практически равные части, каждая из которых сортируется отдельно. После чего уже упорядоченные части сливаются воедино. Несколько детально этот процесс можно расписать так:

1. массив рекурсивно разбивается пополам, и каждая из половин делиться до тех пор, пока размер очередного подмассива не станет равным единице;

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

3. в конце операции слияния, элементы перезаписываются из результирующего массива в исходный.

Основная подпрограмма MergeSort рекурсивно разбивает и сортирует массив, а Merge отвечает за его слияние. Так можно записать псевдокод основной подпрограммы:

1 2 3 4 5 6 7 8 9 10 11

Подпрограмма 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 заключается в образовании упорядоченного результирующего массива путем слияния двух также отсортированных массивов меньших размеров. Вот псевдокод этой подпрограммы:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

Подпрограмма 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] }

Разберем алгоритм сортировки слиянием на следующем примере. Имеется неупорядоченная последовательность чисел: 2, 6, 7, 1, 3, 5, 0, 4. После разбивки данной последовательности на единичные массивы, процесс сортирующего слияния (по возрастанию) будет выглядеть так:

Массив был разделен на единичные массивы, которые алгоритм сливает попарно до тех пор, пока не получится один массив, все элементы которого стоят на своих позициях.

Код программы на C++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

#include "stdafx.h" #include <iostream> using namespace std; //функция, сливающая массивы void Merge(int *A, int first, int last) { int middle, start, final, j; int *mas=new int[100]; middle=(first+last)/2; //вычисление среднего элемента start=first; //начало левой части final=middle+1; //начало правой части for(j=first; j<=last; j++) //выполнять от начала до конца if ((start<=middle) && ((final>last) || (A[start]<A[final]))) { mas[j]=A[start]; start++; } else { mas[j]=A[final]; final++; } //возвращение результата в список for (j=first; j<=last; j++) A[j]=mas[j]; delete[]mas; }; //рекурсивная процедура сортировки void MergeSort(int *A, int first, int last) { { if (first<last) { MergeSort(A, first, (first+last)/2); //сортировка левой части MergeSort(A, (first+last)/2+1, last); //сортировка правой части Merge(A, first, last); //слияние двух частей } } }; //главная функция void main() { setlocale(LC_ALL, "Rus"); int i, n; int *A=new int[100]; cout<<"Размер массива > "; cin>>n; for (i=1; i<=n; i++) { cout<<i<<" элемент > "; cin>>A[i];} MergeSort(A, 1, n); //вызов сортирующей процедуры cout<<"Упорядоченный массив: "; //вывод упорядоченного массива for (i=1; i<=n; i++) cout<<A[i]<<" "; delete []A; system("pause>>void"); }

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

1 23

Дата добавления: 2017-05-02; просмотров: 1377;