Pull to refresh

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

Reading time 4 min
Views 205K
Кто-то сказал однажды, что
...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[a1.length + a2.length];

Это задача для сортировки слиянием.

Что это такое? В интернете есть ответ, есть описание алгоритма, но я его не понял с одного присеста и решил разобраться сам. Для этого необходимо понять базовый принцип алгоритма, чтобы можно было по памяти воссоздать алгоритм применительно к своей задаче.

Начали за здравие


Давайте пойдем постепенно и воспользуемся тем, что лежит на поверхности: будем брать поочередно по одному элементу из каждого массива, сравнивать их и «сливать» в один массив. Меньший элемент будем ставить первым, больший – вторым. Тогда после первого прохода все нормально:

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[a1.length + a2.length];

    int i=0, j=0;
    for (int k=0; k<a3.length; k++) {

        if (i > a1.length-1) {
            int a = a2[j];
            a3[k] = a;
            j++;
        }
        else if (j > a2.length-1) {
            int a = a1[i];
            a3[k] = a;
            i++;
        }
        else if (a1[i] < a2[j]) {
            int a = a1[i]; 
            a3[k] = a;
            i++;
        }
        else {
            int b = a2[j];
            a3[k] = b;
            j++;
        }
    }


Здесь:

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).

Ссылки


Алгоритмы на Java
Cat's Cradle Quotes
Tags:
Hubs:
-6
Comments 11
Comments Comments 11

Articles