Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Сортировка слиянием. Алгоритм сортировки слиянием был предложен праотцом современных компьютеров – Джоном фон Нейманом
|
|
Алгоритм сортировки слиянием был предложен праотцом современных компьютеров – Джоном фон Нейманом. Сам метод является устойчивым, т. е. он не меняет одинаковые по значению элементы в списке.
В основе сортировки слиянием лежит принцип «разделяй и властвуй». Список разделяется на равные или практически равные части, каждая из которых сортируется отдельно. После чего уже упорядоченные части сливаются воедино. Несколько детально этот процесс можно расписать так:
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).
|
|