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

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

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

Несколько детально этот процесс можно расписать так:

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

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

Так можно записать псевдокод основной подпрограммы:

Эта подпрограмма выполняется только в том случае, если номер первого элемента меньше номера последнего. Как уже говорилось, из подпрограммы MergeSort вызывается подпрограмма Merge, которая выполняет операцию слияния. Перейдем к рассмотрению последней.

Работа Merge заключается в образовании упорядоченного результирующего массива путем слияния двух также отсортированных массивов меньших размеров. Вот псевдокод этой подпрограммы:

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

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

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

Код программы на Pascal:

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


Похожие записи:
8 Comments
  • · Edit

    В тексте на С++ ошибка. Строка 48 MergeSort( A, 1, n); //вызов сортирующей процедуры.
    Надо исправить на MergeSort( A, 0, n); //вызов сортирующей процедуры
    Именно с нуля должна проводиться сортировка, при 1-це первый элемент массива пропускается и не сортируется.

    Reply
    • При 1-це все сортируется правильно, ничего не пропускается. Приведите последовательность, которая при 1-це у Вас не сортируется.

      Reply
  • · Edit

    Добрый вечер!
    Подскажите, почему в условии сортировки стоит (last>final), если оно по идее никогда не будет истинным. Начало правой части всегда больше конца.

    Reply
  • · Edit

    Тут для массивов размером меньше 100 память неэкономно используется, а для n > 100 крашится за счет 8 строчки:
    int *mas=new int[100];
    вот с исправлением:
    void Merge(int *A, int first, int last){
    int middle, start, final, j;
    middle = (first + last) / 2;
    start = first;
    final = middle + 1;
    int *mas = new int[last — first + 1];
    for (j = first; j <= last; j++)
    if ((start last) || (A[start] < A[final]))){
    mas[j — first] = A[start];
    start++;
    }
    else{
    mas[j — first] = A[final];
    final++;
    }
    for (j = first; j <= last; j++) A[j] = mas[j — first];
    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);
    }
    }

    и еще за счет исправление нужно поменять обращение mas[j] на mas[j — first]

    Reply
  • · Edit

    Аналогично. Сортировка начинает работать правильно только если first = 0. При 1 — пропускается элемент и сортирует только со второго элемента.

    Reply
  • · Edit

    вы оба правы, но так, как в коде не делается, у вас массив заполняется с «1-ой клетки» , то бишь только со второго элемента.

    Reply
  • Что будет если , n будет равно нечётному числу ? массив же не получиться разделить пополам.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *