Лекция № 6: Сортировка слиянием

Затвитить
эту лекцию
Опубликовано 26‑го октября 2008 г.
Обновлено 19‑го ноября 2011 г.

Сортировка слиянием — вероятно, один из самых простых алгоритмов сортировки (среди «быстрых» алгоритмов). Особенностью этого алгоритма является то, что он работает с элементами массива преимущественно последовательно, благодаря чему именно этот алгоритм используется при сортировке в системах с различными аппаратными ограничениями (например, при сортировке данных на жёстком диске, или даже на магнитной ленте). Кроме того, сортировка слиянием — чуть ли не единственный алгоритм, который может быть эффективно использован для сортировки таких структур данных, как связанные списки. Последовательная работа с элементами массива значительно увеличивает скорость сортировки в системах с кэшированием.

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

Этот алгоритм был предложен Джоном фон Нейманом в 1945 году

Везде в лекции элементы массивов нумеруются с нуля.

Процедура слияния

Допустим, у нас есть два отсортированных массива A и B размерами n_a и n_b соответственно, и мы хотим объединить их элементы в один большой отсортированный массив C размером n_a+n_b . Для этого можно применить процедуру слияния, суть которой заключается в повторяющемся «отделении» элемента, наименьшего из двух имеющихся в началах исходных массивов, и присоединении этого элемента к концу результирующего массива. Элементы мы переносим до тех пор, пока один из исходных массивов не закончится. После этого оставшийся «хвост» одного из входных массивов дописывается в конец результирующего массива. Пример работы процедуры показан на рисунке:

Рис. 1. Пример работы процедуры слияния

Алгоритм слияния формально можно записать следующим образом:

$\begin{array}{l} a \leftarrow 0;\ b \leftarrow 0;\\ \text{While }a < n_a\text{ and }b < n_b\\ \left|\quad\begin{array}{l} \text{If }A[a]\leqslant B[b]\\ \left|\quad\begin{array}{l} C[a+b] \leftarrow A[a];\\ a \leftarrow a+1; \end{array}\right.\\ \text{Else}\\ \left|\quad\begin{array}{l} C[a+b] \leftarrow B[b];\\ b \leftarrow b+1; \end{array}\right.\\ \text{End;} \end{array}\right.\\ \text{End;}\\ \text{If }a < n_a\\ \left|\quad\text{Copy remain part of A}\right.\\ \text{Else}\\ \left|\quad\text{Copy remain part of B}\right.\\ \text{End;} \end{array}$

(1)

Для обеспечения стабильности алгоритма сортировки нужно, чтобы в случае равенства элементов тот элемент, что идёт раньше во входном массиве, попадал в результирующий массив в первую очередь. Мы увидим далее, что если два элемента попали в разные массивы (A и B), то тот элемент, что шёл раньше, попадёт в массив A. Следовательно, в случае равенства элемент из массива A должен иметь приоритет. Поэтому в алгоритме стои́т знак $\leqslant$ вместо < при сравнении элементов.

Недостатком представленного алгоритма является необходимость дописывать оставшийся кусок, из-за чего при дальнейших модификациях алгоритма нам придётся писать много повторяющегося кода. Чтобы этого избежать, будем использовать чуть менее эффективный, но более короткий алгоритм, в котором копирование «хвоста» встроено в основной цикл:

$\begin{array}{l} a \leftarrow 0;\ b \leftarrow 0;\\ \text{While }a+b < n_a+n_b\\ \left|\quad\begin{array}{l} \text{If }b\geqslant n_b\text{ or }\left(a<n_a\text{ and }A[a]\leqslant B[b]\right)\\ \left|\quad\begin{array}{l} C[a+b] \leftarrow A[a];\\ a \leftarrow a+1; \end{array}\right.\\ \text{Else}\\ \left|\quad\begin{array}{l} C[a+b] \leftarrow B[b];\\ b \leftarrow b+1; \end{array}\right.\\ \text{End;} \end{array}\right.\\ \text{End;} \end{array}$

(2)

Очевидно, время работы процедуры слияния составляет $O\left(n_a+n_b\right)$ .

Реализация процедуры слияния на языке программирования C++ представлена в листинге 1.

template<class T> void Merge(T const *const A, int const nA,

                             T const *const B, int const nB,

                             T *const C)

{ //Выполнить слияние массива A, содержащего nA элементов,

  //  и массива B, содержащего nB элементов.

  //  Результат записать в массив C.

    int a(0), b(0); //Номера текущих элементов в массивах A и B

    while( a+b < nA+nB ) //Пока остались элементы в массивах

    {

        if( (b>=nB) || ( (a<nA) && (A[a]<=B[b]) ) )

        { //Копирую элемент из массива A

            C[a+b] = A[a];

            ++a;

        } else { //Копирую элемент из массива B

            C[a+b] = B[b];

            ++b;

        }

    }

}

Листинг 1. Компактная (не самая быстрая) реализация процедуры слияния

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

Процедура слияния требует два отсортированных массива. Заметив, что массив из одного элемента по определению является отсортированным, мы можем осуществить сортировку следующим образом:

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

Проще всего формализовать этот алгоритм рекурсивным способом (в следующем разделе мы реализуем этот алгоритм итерационным способом). Функция $\text{MergeSort}$ сортирует участок массива от элемента с номером a до элемента с номером b:

$\begin{array}{l} \text{Function MergeSort}\left(a,b\right)\\ \left|\quad\begin{array}{l} \text{If }b=a\text{ then Exit;}\\ c \leftarrow \left\lfloor\left(a+b\right)/2\right\rfloor;\\ \text{MergeSort}\left(a,c\right);\\ \text{MergeSort}\left(c+1,b\right);\\ \text{Merge fragments }\left(a,c\right)\text{ and }\left(c+1,b\right); \end{array}\right.\\ \text{End} \end{array}$

(3)

Поскольку функция $\text{MergeSort}$ сортирует лишь часть массива, то при слиянии двух фрагментов ей не остаётся ничего, кроме как выделять временный буфер для результата слияния, а затем копировать данные обратно:

template<class T> void MergeSort(T *const A, int const n)

{ //Отсортировать массив A, содержащий n элементов

    if( n < 2 ) return; //Сортировка не нужна

    if( n == 2 ) //Два элемента проще поменять местами,

    {            //  если нужно, чем делать слияние

        if( A[0] > A[1] ) { T const t(A[0]); A[0]=A[1]; A[1]=t; }

        return;

    }

    MergeSort(A    , n/2  ); //Сортируем первую половину

    MergeSort(A+n/2, n-n/2); //Сортируем вторую половину

    T *const B( new T[n] ); //Сюда запишем результат слияния

    Merge(A,n/2, A+n/2,n-n/2, B); //Слияние половин

    //Копирование результата слияния в исходный массив:

    for(int i(0); i<n; ++i) A[i]=B[i];

    delete[n] B; //Удаляем временный буфер

}

Листинг 2. Реализация сортировки слиянием

Время работы сортировки слиянием составляет $O\left(n\cdot\ln\left(n\right)\right)$ . Пример работы процедуры показан на рисунке:

Рис. 2. Пример работы рекурсивного алгоритма сортировки слиянием

Восходящая сортировка слиянием

Программа, представленная в листинге 2, имеет серьёзные недостатки: она выделяет и освобождает много буферов памяти, и делает копирование результатов слияния в исходный массив вместо того, чтобы вернуть новый массив в качестве результата (она не может вернуть новый массив в качестве результата, т.к. на входе получает зачастую лишь часть большого массива).

Чтобы избавиться от этих недостатков, откажемся от рекурсивной реализации, и сделаем сортировку следующим образом:

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

Такой алгоритм называется восходящей сортировкой слиянием. Реализация его на языке программирования C++ приведена в листинге 3.

template<class T> void MergeSortIterative(T *&A, int const n)

{ //Отсортировать массив A, содержащий n элементов.

  //  При работе указатель на A, возможно, меняется.

  //  (Функция получает ссылку на указатель на A)

    T *B( new T[n] ); //Временный буфер памяти

    for(int size(1); size<n; size*=2)

    { //Перебираем все размеры кусочков для слияния: 1,2,4,8...

        int start(0); //Начало первого кусочка пары

        for(; (start+size)<n; start+=size*2)

        { //Перебираем все пары кусочков, и выполняем попарное

          //  слияние. (start+size)<n означает, что начало

          //  следующего кусочка лежит внутри массива

            Merge(A+start     , size,

                  A+start+size, min(size,n-start-size),

                  B+start                               );

        }

        //Если последний кусочек остался без пары, просто копи-

        //  руем его из A в B:

        for(; start<n; ++start) B[start]=A[start];

        T *temp(B); B=A; A=temp; //Меняем местами указатели

    }

    delete[n] B; //Удаляем временный буфер

}

Листинг 3. Реализация восходящей сортировки слиянием

К сожалению, в этот алгоритм не так просто вписать оптимизацию для случая слияния двух элементов (если нужно, можно вписать эту оптимизацию в процедуру Merge).

Пример работы программы листинга 3 показан на рисунке:

Рис. 3. Пример работы восходящего алгоритма сортировки слиянием

Если требуется выполнять восходящую сортировку для части массива, или в других случаях, когда указатель на массив менять нельзя, то будет полезной модификация программы, которая, если нужно, копирует результат в исходный массив в конце работы:

template<class T> void MergeSortIter2(T *const A, int const n)

{ //Отсортировать массив A, содержащий n элементов.

    T *B( A        ); //Буфер памяти №1

    T *C( new T[n] ); //Буфер памяти №2

    for(int size(1); size<n; size*=2)

    { //Перебираем все размеры кусочков для слияния: 1,2,4,8...

        int start(0); //Начало первого кусочка пары

        for(; (start+size)<n; start+=size*2)

        { //Перебираем все пары кусочков, и выполняем попарное

          //  слияние. (start+size)<n означает, что начало

          //  следующего кусочка лежит внутри массива

            Merge(B+start     , size,

                  B+start+size, min(size,n-start-size),

                  C+start                               );

        }

        //Если последний кусочек остался без пары, просто копи-

        //  руем его из B в C:

        for(; start<n; ++start) C[start]=B[start];

        T *temp(B); B=C; C=temp; //Меняем местами указатели

    }

    //В данный момент результат работы находится в массиве B.

    if( C == A )

    {  //  Если массив C является массивом A, то нужно

       //  скопировать результат работы из B в A.

        for(int i(0); i<n; ++i) A[i]=B[i];

        delete[n] B; //Удаляем временный буфер

    } else {

        delete[n] C; //Удаляем временный буфер

    }

}

Листинг 4. Реализация восходящей сортировки слиянием
с сохранением результата работы в исходном массиве

Измерение быстродействия алгоритма

Измерим быстродействие программы из листинга 3. Условия измерения — те же, что для алгоритма пирамидальной сортировки (см. лекцию 5).

На рис. 4 показан график величины $k\left(n\right)$ , определяемой выражением:

$k\left(n\right)=10^9\cdot\frac{T\left(n\right)}{n\cdot\ln\left(n+1\right)},$

(4)

где n — количество сортируемых псевдослучайных четырёхбайтовых целых чисел, $T\left(n\right)$ — время сортировки на моём компьютере.

Отношение времени сортировки к n∙ln(n+1)

Рис. 4. Отношение времени сортировки к $n\cdot\ln\left(n+1\right)$ .
Красный цвет — сортировка слиянием,
серый цвет — пирамидальная сортировка

На графике проявляются две важные особенности алгоритма:

Сортировка слиянием работает в полтора-два раза медленнее, чем пирамидальная сортировка, когда число сортируемых элементов меньше 500. Так как алгоритм сортировки слиянием рекурсивный, эта потеря быстродействия на сортировке малых массивов отражается на всём остальном графике. Если мы сможем ускорить алгоритм для сортировки малых объёмов данных — мы сможем ускорить его для сортировки любых объёмов данных.
Скорость сортировки не падает, когда количество сортируемых данных становится больше размера кеша! Это означает, что именно сортировку слиянием следует использовать для сортировки больших объёмов данных.

Гибридная сортировка

Анализ быстродействия алгоритма наталкивает нас на мысль объединить преимущества алгоритмов пирамидальной сортировки и сортировки слиянием. К счастью, сделать это очень просто: нужно разбить массив сразу на большие кусочки (например, размером 512 элементов), и применить к ним алгоритм пирамидальной сортировки. Полученные отсортированные кусочки затем можно «досортировать» слиянием. Используя функции из лекции 5, требуемые изменения в алгоритме минимальны (за основу взята функция из листинга 3):

template<class T> void HybridSort(T *&A, int const n)

{ //Отсортировать массив A, содержащий n элементов.

  //  При работе указатель на A, возможно, меняется.

  //  (Функция получает ссылку на указатель на A)

    //Размер кусочка для сортировки пирамидой:

    //  (нужно подбирать для максимального ускорения)

    int const tileSize( 4096 );

    for(int start(0); start<n; start+=tileSize)

        HeapSort(A+start, min(tileSize,n-start) );

    if( n <= tileSize ) return; //Больше сортировать не нужно

    T *B( new T[n] ); //Временный буфер памяти

    for(int size(tileSize); size<n; size*=2)

    { //Перебираем размеры кусочков для слияния,

      //  начиная с tileSize элементов

        int start(0); //Начало первого кусочка пары

        for(; (start+size)<n; start+=size*2)

        { //Перебираем все пары кусочков, и выполняем попарное

          //  слияние. (start+size)<n означает, что начало

          //  следующего кусочка лежит внутри массива

            Merge(A+start     , size,

                  A+start+size, min(size,n-start-size),

                  B+start                               );

        }

        //Если последний кусочек остался без пары, просто копи-

        //  руем его из A в B:

        for(; start<n; ++start) B[start]=A[start];

        T *temp(B); B=A; A=temp; //Меняем местами указатели

    }

    delete[n] B; //Удаляем временный буфер

}

Листинг 5. Реализация гибридной сортировки

Быстродействие гибридной сортировки показано на графике:

Рис. 5. Отношение времени сортировки к $n\cdot\ln\left(n+1\right)$ .
Красный цвет — гибридная сортировка,
синий цвет — сортировка слиянием,
серый цвет — пирамидальная сортировка

Из графика видно, что гибридная сортировка имеет время работы, как у пирамидальной сортировки при малом числе элементов, и незначительно быстрее сортировки слиянием при большом их числе.

Tiled-версия

Tile переводится, как «черепица», «плитка». Приём программирования, при котором большие объёмы данных разделяются для обработки и хранения на части меньшего размера («tiles»), называется «tiling». Вместо «tile» мы будем говорить «блок».

Основным недостатком представленных до сих пор реализаций сортировки слиянием является необходимость иметь $2\cdot N$ байт оперативной памяти для сортировки N байт данных. Самый простой способ справиться с этим — работать со связанными списками элементов. При слиянии двух списков нужно переносить элементы из начала исходных списков в конец результирующего списка. При этом дополнительная память для хранения промежуточных результатов не потребуется.

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

Связанные списки не позволяют быстро обращаться к произвольным элементам, поэтому мы пойдём немного другим путём: будем хранить массив указателей на блоки памяти большого размера (но умещающиеся в кэш процессора). Такая структура данных была описана в лекции 4 (раздел «Программная реализация алгоритма Гаусса»).

Процедура слияния будет освобождать обработанные блоки памяти, и выделять новые по мере записи результата. В этом случае максимальный дополнительный объём памяти, который понадобится, равен двукратному размеру блока памяти. Кроме того, указатели на результирующие блоки памяти после слияния можно легко перенести в исходный буфер. Для простоты будем считать, что все блоки, на которые разбит исходный массив имеют одинаковый размер: tileSize элементов.

template<class T> template<class T> void MergeTiled(T **const Array,

    int const numTiles1, int const numTiles2, int const tileSize)

{ //Выполнить слияние двух цепочек из массива Array. Первая

  //  цепочка состоит из numTiles1 блоков, вторая цепочка

  //  состоит из numTiles2 блоков и идёт сразу за первой.

  //  Каждый блок имеет размер tileSize

    //Массив для записи указателей на результирующие блоки:

    T **Result = new T *[numTiles1+numTiles2]; 

    Result[0] = new T[tileSize]; //Пока создаём один блок

    //Номера текущих блоков в первой и второй исходных

    //  цепочках и в результирующей цепочке соответственно:

    int tN1(0), tN2(0), tNR(0);

    //Указатели на текущие блоки:

    T *t1( Array[0] ), *t2( Array[numTiles1] ), *tR( Result[0] );

    //Номера текущих элементов в соответствующих цепочках:

    int n1(0), n2(0), nR(0);

    while( true ) 

    {

        if( (tN2>=numTiles2) ||

            ( (tN1<numTiles1) && (t1[n1]<=t2[n2]) ) )

        {

            tR[nR] = t1[n1];

            ++n1; //Переходим к след. элементу в первой цепочке

            if( n1>=tileSize )

            { //Текущий блок в первой цепочке закончился

                //Удаляем текущий блок первой цепочки:

                delete[tileSize] t1;

                ++tN1; //Увеличиваем номер текущего блока

                //Переходим к следующему блоку первой цепочки:

                if( tN1 < numTiles1 ) t1 = Array[tN1];

                n1 = 0; //Перешли к началу следующего блока

            }

        } else {

            tR[nR] = t2[n2];

            ++n2; //Переходим к след. элементу во второй цепочке

            if( n2>=tileSize )

            { //Текущий блок во второй цепочке закончился

                //Удаляем текущий блок второй цепочки:

                delete[tileSize] t2;

                ++tN2; //Увеличиваем номер текущего блока

                //Переходим к следующему блоку второй цепочки:

                if( tN2 < numTiles2 ) t2 = Array[numTiles1+tN2];

                n2 = 0; //Перешли к началу следующего блока

            }

        }

        ++nR;

        if( nR>=tileSize )

        { //Текущий блок в результирующей цепочке закончился

            //Увеличиваем номер текущего блока результата:

            ++tNR;

            //Место для записи результата закончилось.

            //  Значит, закончились и исходные данные:

            if( tNR >= numTiles1+numTiles2 ) break;

            //Выделяем память под следующий блок результата:

            Result[tNR] = tR = new T[tileSize];

            nR = 0; //Перешли к началу следующего блока

        }

    }

    //Исходные блоки удалены. Записываем указатели на результи-

    //  рующие блоки на место указателей на исходные блоки:

    for(int tN(0); tN<numTiles1+numTiles2; ++tN)

        Array[tN] = Result[tN];

    //Удаляем массив указателей на результирующие блоки:

    delete[numTiles1+numTiles2] Result;

}

Листинг 6. Tiled-версия процедуры слияния

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

template<class T> void MergeSortTiled(T **const Array,

    int const numTiles, int const tileSize)

{ //Отсортировать массив Array, содержащий numTiles блоков

  //  по tileSize элементов

    //Вначале сортирую элементы каждого блока каким-нибудь из

    //  описанных ранее алгоритмов:

    for(int tN(0); tN<numTiles; ++tN)

        HeapSort(Array[tN], tileSize);

    for(int size(1); size<numTiles; size*=2)

    { //Перебираем все размеры цепочек блоков

      //  для слияния: 1,2,4,8...

        for(int start(0); (start+size)<numTiles; start+=size*2)

        { //Перебираем все пары цепочек, и выполняем попарное

          //  слияние. (start+size)<numTiles означает, что начало

          //  следующей цепочки лежит внутри массива

            MergeTiled(Array+start,

                       size,

                       min(size,numTiles-start-size),

                       tileSize);

        }

    }

}

Листинг 7. Tiled-версия сортировки слиянием

Чем больше по размерам будет каждый блок памяти, тем меньше будут накладные расходы на работу с блоками. Однако, при большом размере блоков возрастают требования к дополнительному объёму памяти, требуемому программой. График скорости работы программы представлен на рисунке 6. Объём одного блока был выбран равным одному мегабайту, поэтому график начинается с 262144 элементов:

Рис. 6. Отношение времени сортировки к $n\cdot\ln\left(n+1\right)$ .
Красный цвет — tiled-версия сортировки слиянием,
серый цвет — гибридная сортировка

Из графика видно, что накладные расходы по работе с блоками совсем невелики, но они, к сожалению, растут по мере увеличения количества блоков. Зато у нас появляется возможность быстро сортировать данные, занимающие почти всю оперативную память компьютера.

Естественная сортировка

До сих пор мы рассматривали алгоритмы сортировки, которые никак не учитывают то, что данные (или их часть) могут быть уже отсортированы. Для алгоритма сортировки слиянием есть очень простая и эффективная модификация, которая называется «естественная сортировка» («Natural Sort»). Суть её в том, что нужно образовывать цепочки, и производить их слияние не в заранее определённом и фиксированном порядке, а анализировать имеющиеся в массиве данные. Алгоритм следующий:

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

Пример работы этого алгоритма показан на рисунке:

Рис. 7. Пример работы естественного алгоритма сортировки слиянием

В отличие от ранее рассмотренных вариантов алгоритма слияния, естественная сортировка справилась с задачей за 3, а не за 4 итерации.

Обратите внимание, что во время работы алгоритма не могут образоваться новые отсортированные цепочки кроме получившихся в результате слияний (докажите!), поэтому поиск отсортированных цепочек должен проводиться только на первом этапе. Но как хранить найденные цепочки? Выделять для них память — очень неэффективно. Самый простой способ — вообще их не хранить, а искать каждый раз заново. Это неэффективно, зато просто:

template<class T> void NaturalSort(T *&A, int const n)

{ //Отсортировать массив A, содержащий n элементов.

  //  При работе указатель на A, возможно, меняется.

  //  (Функция получает ссылку на указатель на A)

    T *B( new T[n] ); //Временный буфер памяти

    while(true) //Выполняем слияния, пока не останется один

    {           //  отсортированный участокк. Выход из цикла

                //  находится дальше

        int start1    ,end1    ; //Первый отсортированный участок

        int start2(-1),end2(-1); //Второй отсортированный участок

        while(true)

        { //Цикл по всем парам отсортированных участков в массиве

            //Начало первого участка для слияния находится после

            //  конца второго участка предыдущей пары:

            start1 = end2+1; end1 = start1;

            //Двигаемся вправо до нарушения сортировки:

            while( (end1<n-1) && (A[end1]<=A[end1+1]) ) ++end1;

            //Первый участок пары простирается до конца массива:

            if( end1 == n-1 ) break;

            //Начало второго участка для слияния находится после

            //  конца первого участка текущей пары:

            start2 = end1+1, end2 = start2;

            //Двигаемся вправо до нарушения сортировки:

            while( (end2<n-1) && (A[end2]<=A[end2+1]) ) ++end2;

            //Выполняем слияние двух отсортированных участков

            Merge(A+start1, end1-start1+1,

                  A+start2, end2-start2+1,

                  B+start1                );

            //Второй участок пары простирается до конца массива:

            if( end2 == n-1 ) break;

        }

        //Данные полностью отсортированы и находятся в массиве A:

        if( (start1==0) && (end1==n-1) ) break;

        //Если последний кусочек остался без пары, просто копи-

        //  руем его из A в B:

        if( end1 == n-1 )

        {

            for(; start1<n; ++start1) B[start1]=A[start1];

        }

        T *temp(B); B=A; A=temp; //Меняем местами указатели

    }

    delete[n] B; //Удаляем временный буфер

}

Листинг 8. Исходный код алгоритма естественной сортировки слиянием

Несмотря на то, что представленная реализация на каждой итерации примерно 25% времени проводит в поиске отсортированных фрагментов для слияния (хотя этот поиск достаточно произвести только в начале), она показывает неплохие результаты для случайного набора чисел:

Рис. 8. Отношение времени сортировки к $n\cdot\ln\left(n+1\right)$ .
Красный цвет — естественная сортировка,
серый цвет — восходящая сортировка слиянием

Если же исходные данные будут не случайны, а уже частично отсортированы, алгоритм естественной сортировки может ускориться в несколько раз!

Затвитить
эту лекцию

Девять отзывов на «сортировку слиянием»

Отзыв № 1
Автор: Тюй Кикэн. Дата: 26-го марта 2009 г. Время: 11:50.

Очень здоровская статья! То что надо. Спасибо.

Отзыв № 2
Автор: Денис. Дата: 22-го апреля 2009 г. Время: 18:02.

Статья хорошая, только я никак не могу найти реализацию двухпутевого слияния

Отзыв № 3
Автор: Кирилл Козлов. Дата: 10-го января 2010 г. Время: 05:15.

Спасибо Вам огромное за содержательные статьи! Они мне очень помогли в написании курсовой работы!
Все достаточно понятно и четко! И главное видна общая картина, что для очень важно при изучении чего-то нового У Вас хороший стиль!
=)

Отзыв № 4
Автор: Emery Emerald. Дата: 11-го января 2010 г. Время: 11:41.

Интересно, но очень важный случай естественного слияния вы не рассмотрели. Т.е. учитывать не только порядок возрастания уже имеющихся упорядоченных подпоследовательностей (УПП), но и порядок убывания. Какая разница сливать УПП с начала или с конца? Таким образом, убывающая подпоследовательность будет выявлена и выдана за один проход. Далее, нет необходимости ни делать операцию расщепления (Split) несколько раз, ни хранить данные функции Split в массиве структур размерностью более 32!

Если интересно, то вот «Нелинейная» demo реализация сортировки естественным слиянием (Natural Merge Sort) на Visual FoxPro» с картинками ( http://sql.ru/forum/actualthread.aspx?bid=24&tid=686605&pg=2 ) . Сейчас я написал тот же самый (рабочий) алгоритм на С++. И готовлю статью на эту тему (потому и смотрю, чего достигли другие в этой области ).

Отзыв № 5 (ответ на отзыв № 4).
Автор: Антон. Дата: 11-го января 2010 г. Время: 12:28.

Да, действительно. Об обратно отсортированных цепочках я не подумал.

Но это же учебный материал, а не исследовательский. Здесь дано только понятие о разновидностях алгоритмов сортировки слиянием без доведения их до совершенства.

Как напишете статью — дайте ссылку.

Отзыв № 6 (ответ на отзыв № 5).
Автор: Emery Emerald. Дата: 12-го января 2010 г. Время: 07:46.

Думаю, что и учебный материал должен быть достаточно практичный ибо редко кто из программистов может позволить себе исследования. Когда у меня возникла необходимость во внешней сортировке, то учебный материал мне мало чем мог помочь кроме общих идей. То же касается и вопросов индексации данных. В учебных материалах информации на эту тему практически нет. На сайте Майкрософт есть пара примитивных картинок показывающих структуру индексных файлов cdx, но нет ни алгоритма вставки / удаления индекса, ни даже намека на то что представляет из себя эта структура. Пока я совершенно случайно не догадался, что там речь идет о В+ деревьях, с алгоритмом упаковки данных. Причем сам этот алгоритм упаковки приходится исследовать хакерскими методами . Вот такая у нас система обучения, чего не нужно дают с лихвой, а то, что нужно, требуется искать днем с огнем .

Статья будет готова на днях, ссылку выложу.

Отзыв № 7
Автор: Emery Emerald. Дата: 14-го января 2010 г. Время: 22:41.

Статья «Реализация на С++ внешней сортировки «естественным слиянием» (Natural Merge Sort)» by Emery Emerald опубликована на http://sql.ru/forum/actualthread.aspx?tid=727034 .

Полное название:

«Рабочий алгоритм на С++ внешней сортировки «естественным слиянием» (Natural Merge Sort) с неубывающими и убывающими упорядоченными подпоследовательностями»

Краткое описание:

«Продемонстрирована возможность извлечения блока строковых данных из бинарного файла типа DBF с произвольным доступом в памяти (MMF) и сортировка этих данных в один из двух временных буферов. Использована оптимизация по скорости сортировки и объему используемой буферной памяти.»

Отзыв № 8
Автор: Alexandr. Дата: 19-го ноября 2011 г. Время: 14:45.

Верните статью пожалуйста!

Отзыв № 9 (ответ на отзыв № 8).
Автор: Антон. Дата: 19-го ноября 2011 г. Время: 21:14.

Спасибо, что нашли глюк. Сейчас буду исправлять.

Image Processing

Лицензия

Реклама