Сортировка слиянием c реализация. Слияние и сортировка слиянием
Кто-то сказал однажды, что
...any scientist who couldn"t explain to an eight-year-old what he was doing was a charlatan.
Оказывается, это был Курт Воннегут.
Я не стремился доказать это высказывание. Я стремился опровергнуть свою тупость.
Допустим у нас есть два массива чисел, отсортированных по возрастанию.
Int a1 = new int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500};
int a2 = new int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000};
Необходимо слить их в один упорядоченный массив.
Int a3 = new int;
Это задача для сортировки слиянием.
Что это такое? В интернете есть ответ, есть описание алгоритма, но я его не понял с одного присеста и решил разобраться сам. Для этого необходимо понять базовый принцип алгоритма, чтобы можно было по памяти воссоздать алгоритм применительно к своей задаче.
Начали за здравие
Давайте пойдем постепенно и воспользуемся тем, что лежит на поверхности: будем брать поочередно по одному элементу из каждого массива, сравнивать их и «сливать» в один массив. Меньший элемент будем ставить первым, больший – вторым. Тогда после первого прохода все нормально:10, 21
А после второго прохода уже не очень:
10, 21, 11, 23
Понятно, что надо сравнивать элементы еще и с уже добавленными.
Начнем еще раз
Пусть у нас будет некий временный буфер из сравниваемых на каждом шаге элементов. После первого прохода в него попадут 21 и 10. После сравнения мы переместим из буфера в результирующий массив меньший элемент 10 и оставим больший элемент 21, потому что не знаем, что будет за ним.После второго прохода в буфере будет 21, 23 и 11. Что с ними делать – непонятно, сравнить более двух элементов можно, но уже не так просто.
Давайте тогда условимся, что будем брать в этот буфер по одному элементу от каждого массива. Так как проще сравнивать два элемента между собой, да и вообще у нас две сущности – два массива. Тогда после второго прохода в буфере будет 21 и 11, потому что «представитель» первого массива в буфере уже есть – это 21. Сравниваем их и меньший отправляем в результирующий массив. Тогда после второго прохода будем иметь в результирующем массиве:
10, 11
А в буфере – 21.
На третьем проходе берем в буфер из второго массива 41, потому что «представитель» первого массива в буфере так и остался. Сравниваем 21 и 41, и наконец-то убираем из буфера 21.
После третьего прохода будем иметь в результирующем массиве:
10, 11, 21
На четвертом проходе будем сравнивать два значения из буфера - 41 и 23. В результирующем массиве будет:
10, 11, 21, 23
То есть только сейчас – на четвертом, а не на втором проходе - результат получился правильным. Получается, что в цикле надо помнить текущий индекс для каждого массива, а сам цикл может быть длиной равной сумме длин массивов.
Подходим к концу, но вдруг
Что будем делать, когда результирующий массив будет состоять из:10, 11, 21, 23, 24, 40, 41, 50, 65, 75, 76, 78, 77, 86, 98, 101, 190, 900, 1100, 1200, 2100, 2200, 2300, 2400, 2500,
В буфере будет 3000 из второго массива, а в первом - все элементы кончатся? Так как массивы у нас отсортированы, то просто берем 3000 из буфера и оставшееся 5000. То есть нужно для каждого индекса выполнять проверку – не превысили ли мы количество элементов в каждом из массивов.
Усложним задачу
А если у нас не отсортированные массивы? Обычно задача сводится к тому, чтобы отсортировать один массив. Тогда сортировка слиянием тоже может быть использована.Пусть первый массив (для примера возьмем из него несколько элементов) имеет следующее расположение элементов:
2100, 23, 40, 24, 2, 1.
Будем его сортировать. Раз легче сравнивать по два элемента, то разобьем поровну массив на два:
2150, 23, 40
и
24, 2, 1.
Получится по три элемента. Много! Разобьем поровну каждый массив, получится четыре массива:
2100, 23
40
24, 2
1
Отсортируем теперь каждый из массивов простым сравнением первого и второго элементов (там где они есть):
23, 2100
40
2, 24
1
И будем сливать обратно по предыдущему алгоритму – через буфер. После первого слияния получим два массива:
23, 40, 2100
1, 2, 24
И снова сливаем – уже в один массив:
1, 2, 23, 24, 40, 2100
Так мы отсортировали слиянием массив.
В сухом остатке
Таким образом, сортировка слиянием подразумевает разбиение массива поровну до тех пор пока из одного массива не получится несколько мелких - размером не более двух элементов. Два элемента легко сравнить между собой и упорядочить в зависимости от требования: по возрастанию или убыванию.После разбиения следует обратное слияние, при котором в один момент времени (или за проход цикла) выбираются по одному элементу от каждого массива и сравниваются между собой. Наименьший (или наибольший) элемент отправляется в результирующий массив, оставшийся элемент остается актуальным для сравнения с элементом из другого массива на следующем шаге.
Выразим в коде (Java)
Пример сортировки по возрастанию двух отсортированных массивов:Int a1 = new int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500};
int a2 = new int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000};
int a3 = new int;
int i=0, j=0;
for (int k=0; k
Здесь:
A1 и a2 – массивы, которые надо слить;
a3 – результирующий массив;
i и j – индексы для массивов a1 и a2 соответственно, которые указывают на текущие элементы на каждом шаге и образуют тот самый буфер.
Первые два условия проверяют, что бы индексы не вышли за переделы количества элементов в массивах. Третье и четвертое условия обеспечивают перемещение в массив наименьшего элемента из первого массива и из второго соответственно.
Функция сортировки слиянием
Оформим приведенный код как рекурсивную функцию, которая станет разделять массивы до тех пор, пока это возможно, с параметрами, соответствующими целому массиву при первом вызове, его половинам при втором и третьем вызовах и т. д.Private void SortUnsorted(int a, int lo, int hi) {
if (hi <= lo)
return;
int mid = lo + (hi - lo) / 2;
SortUnsorted(a, lo, mid);
SortUnsorted(a, mid + 1, hi);
int buf = Arrays.copyOf(a, a.length);
for (int k = lo; k <= hi; k++)
buf[k] = a[k];
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) {
a[k] = buf[j];
j++;
} else if (j > hi) {
a[k] = buf[i];
i++;
} else if (buf[j] < buf[i]) {
a[k] = buf[j];
j++;
} else {
a[k] = buf[i];
i++;
}
}
}
Здесь:
A – массив;
lo – позиция первого элемента в массиве (для первой итерации = 0);
hi – позиция последнего элемента в массиве (для первой итерации = a.length - 1).
Алгоритм сортировки слиянием был предложен праотцом современных компьютеров – Джоном фон Нейманом. Сам метод является устойчивым, т. е. он не меняет одинаковые по значению элементы в списке.
В основе сортировки слиянием лежит принцип «разделяй и властвуй». Список разделяется на равные или практически равные части, каждая из которых сортируется отдельно. После чего уже упорядоченные части сливаются воедино. Несколько детально этот процесс можно расписать так:
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<<"Упорядоченный массив: "; //вывод упорядоченного массива