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

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

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

Этот ал­го­ритм был пред­ло­жен Джо­ном фон Ней­ма­ном в 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. Ком­пакт­ная (не са­мая быст­рая) реа­ли­за­ция про­це­ду­ры слия­ния

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

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

  1. раз­бить имею­щие­ся эле­мен­ты мас­си­ва на па­ры и осу­ще­ствить слия­ние эле­мен­тов каж­дой па­ры, по­лу­чив от­сор­ти­ро­ван­ные це­поч­ки дли­ны 2 (кро­ме, быть мо­жет, од­но­го эле­мен­та, для ко­то­ро­го не на­шлось па­ры);
  2. раз­бить имею­щие­ся от­сор­ти­ро­ван­ные це­поч­ки на па­ры, и осу­ще­ствить слия­ние це­по­чек каж­дой па­ры;
  3. ес­ли чис­ло от­сор­ти­ро­ван­ных це­по­чек боль­ше еди­ни­цы, пе­рей­ти к ша­гу 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).
Крас­ный цвет — сор­ти­ров­ка слия­ни­ем,
се­рый цвет — пи­ра­ми­даль­ная сор­ти­ров­ка

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

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

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

Ана­лиз быст­ро­дей­ствия ал­го­рит­ма на­тал­ки­ва­ет нас на мысль объ­еди­нить пре­иму­ще­ства ал­го­рит­мов пи­ра­ми­даль­ной сор­ти­ров­ки и сор­ти­ров­ки слия­ни­ем. К сча­стью, сде­лать это очень про­сто: нуж­но раз­бить мас­сив сра­зу на боль­шие ку­соч­ки (на­при­мер, раз­ме­ром 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. Реа­ли­за­ция ги­брид­ной сор­ти­ров­ки

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

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

Рис. 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 эле­мен­тов:

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

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

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

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

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

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

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

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

Рис. 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% вре­ме­ни про­во­дит в по­ис­ке от­сор­ти­ро­ван­ных фраг­мен­тов для слия­ния (хо­тя этот по­иск до­ста­точ­но про­из­ве­сти толь­ко в на­ча­ле), она по­ка­зы­ва­ет не­пло­хие ре­зуль­та­ты для слу­чай­но­го на­бо­ра чи­сел:

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

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

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

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

Очень здо­ров­ская ста­тья! То что на­до. Спа­си­бо.
Ста­тья хо­ро­шая, толь­ко я ни­как не мо­гу най­ти реа­ли­за­цию двух­пу­те­во­го слия­ния
Спа­си­бо Вам огром­ное за со­дер­жа­тель­ные ста­тьи! Они мне очень по­мог­ли в на­пи­са­нии кур­со­вой ра­бо­ты!
Все до­ста­точ­но по­нят­но и чет­ко! И глав­ное вид­на об­щая кар­ти­на, что для очень важ­но при изу­че­нии че­го-то но­во­го У Вас хо­ро­ший стиль!
=)
Ин­те­рес­но, но очень важ­ный слу­чай ес­те­ствен­но­го слия­ния вы не рас­смот­ре­ли. Т.е. учи­ты­вать не толь­ко по­ря­док воз­рас­та­ния уже имею­щих­ся упо­ря­до­чен­ных под­по­сле­до­ва­тель­но­стей (УПП), но и по­ря­док убы­ва­ния. Ка­кая раз­ни­ца сли­вать УПП с на­ча­ла или с кон­ца? Та­ким об­ра­зом, убы­ваю­щая под­по­сле­до­ва­тель­ность бу­дет вы­яв­ле­на и вы­да­на за один про­ход. Да­лее, нет не­об­хо­ди­мо­сти ни де­лать опе­ра­цию рас­щеп­ле­ния (Split) не­сколь­ко раз, ни хра­нить дан­ные функ­ции Split в мас­си­ве ст­рук­тур раз­мер­но­стью бо­лее 32! Ес­ли ин­те­рес­но, то вот «Не­ли­ней­ная» demo реа­ли­за­ция сор­ти­ров­ки ес­те­ствен­ным слия­ни­ем (Natural Merge Sort) на Visual FoxPro» с кар­тин­ка­ми ( http://sql.ru/forum/actualthread.aspx?bid=24&tid=686605&pg=2 ) . Сей­час я на­пи­сал тот же са­мый (ра­бо­чий) ал­го­ритм на С++. И го­тов­лю ста­тью на эту те­му (по­то­му и смот­рю, че­го до­стиг­ли дру­гие в этой об­ла­сти ).
Да, дей­стви­тель­но. Об об­рат­но от­сор­ти­ро­ван­ных це­поч­ках я не по­ду­мал. Но это же учеб­ный ма­те­ри­ал, а не ис­сле­до­ватель­ский. Здесь да­но толь­ко по­ня­тие о раз­но­вид­но­стях ал­го­рит­мов сор­ти­ров­ки слия­ни­ем без до­ве­де­ния их до со­вер­шен­ства. Как на­пи­ше­те ста­тью — дай­те ссыл­ку.
Ду­маю, что и учеб­ный ма­те­ри­ал дол­жен быть до­ста­точ­но прак­тич­ный ибо ред­ко кто из про­грам­ми­стов мо­жет поз­во­лить се­бе ис­сле­до­ва­ния. Ко­гда у ме­ня воз­ник­ла не­об­хо­ди­мость во внеш­ней сор­ти­ров­ке, то учеб­ный ма­те­ри­ал мне ма­ло чем мог по­мочь кро­ме об­щих идей. То же ка­са­ет­ся и во­про­сов ин­дек­са­ции дан­ных. В учеб­ных ма­те­ри­а­лах ин­фор­ма­ции на эту те­му прак­ти­че­ски нет. На сай­те Май­к­ро­софт есть па­ра при­ми­тив­ных кар­ти­нок по­ка­зы­ваю­щих ст­рук­ту­ру ин­декс­ных фай­лов cdx, но нет ни ал­го­рит­ма встав­ки / уда­ле­ния ин­дек­са, ни да­же на­ме­ка на то что пред­став­ля­ет из се­бя эта ст­рук­ту­ра. По­ка я со­вер­шен­но слу­чай­но не до­га­дал­ся, что там речь идет о В+ де­ре­вьях, с ал­го­рит­мом упа­ков­ки дан­ных. При­чем сам этот ал­го­ритм упа­ков­ки при­хо­дит­ся ис­сле­до­вать ха­кер­ски­ми ме­то­да­ми . Вот та­кая у нас си­сте­ма обу­че­ния, че­го не нуж­но да­ют с лих­вой, а то, что нуж­но, тре­бу­ет­ся ис­кать днем с ог­нем . Ста­тья бу­дет го­то­ва на днях, ссыл­ку вы­ло­жу.
Ста­тья «Реа­ли­за­ция на С++ внеш­ней сор­ти­ров­ки «ес­те­ствен­ным слия­ни­ем» (Natural Merge Sort)» by Emery Emerald опуб­ли­ко­ва­на на http://sql.ru/forum/actualthread.aspx?tid=727034 . Пол­ное на­зва­ние: «Ра­бо­чий ал­го­ритм на С++ внеш­ней сор­ти­ров­ки «ес­те­ствен­ным слия­ни­ем» (Natural Merge Sort) с не­убы­ваю­щи­ми и убы­ваю­щи­ми упо­ря­до­чен­ны­ми под­по­сле­до­ва­тель­но­стя­ми» Крат­кое опи­са­ние: «Про­де­мон­стри­ро­ва­на воз­мож­ность из­вле­че­ния бло­ка стро­ко­вых дан­ных из би­нар­но­го фай­ла ти­па DBF с про­из­воль­ным до­сту­пом в па­мя­ти (MMF) и сор­ти­ров­ка этих дан­ных в один из двух вре­мен­ных бу­фе­ров. Ис­поль­зо­ва­на оп­ти­ми­за­ция по ско­ро­сти сор­ти­ров­ки и объ­е­му ис­поль­зу­е­мой бу­фер­ной па­мя­ти.»
Вер­ни­те ста­тью по­жа­луй­ста!
Спа­си­бо, что на­шли глюк. Сей­час бу­ду ис­прав­лять.
Спа­си­бо огром­ное! Про­сто не­ве­ро­ят­но по­мог­ло! Луч­ше и быть не мог­ло =^.^=
сде­лал MergeSort по­сле че­го не мо­гу сде­лать MergeLists. Под­ска­жи­те как это сде­лать.
PEDA el ves Naf bot piczki
Все грун­ты, со­дер­жа­щие гли­ну, под­вер­же­ны это­му не­га­тив­но­му яв­ле­нию, и чем боль­ше со­дер­жа­ние гли­ны, тем силь­нее про­яв­ля­ет­ся это свой­ство. По­ры гли­ни­сто­го грун­та на­столь­ко ма­лы, что ка­пил­ляр­ные си­лы при­тя­же­ние меж­ду ча­сти­ца­ми во­ды и гли­ны ока­зы­ва­ют­ся до­ста­точ­ны­ми, что­бы свя­зы­вать их. Ка­пил­ляр­ные си­лы при­тя­же­ния в со­во­куп­но­сти с пла­стич­но­стью ча­стиц гли­ны обес­пе­чи­ва­ют пла­стич­ность гли­ни­сто­го грун­та. И чем боль­ше со­дер­жа­ние гли­ны, тем пла­стич­нее бу­дет грунт. В за­ви­си­мо­сти от со­дер­жа­ния ча­стиц гли­ны их клас­сифи­ци­ру­ют на про­дам су­гли­нок су­песи, су­глин­ки и гли­ну. Клас­сифи­ка­ция гли­ни­сто­го грун­та Су­песь – это гли­ни­стый грунт, ко­то­рый со­дер­жит не бо­лее 10 % гли­ни­стых ча­стиц, остав­шу­ю­ся часть за­ни­ма­ет пе­сок. Су­песь на­и­ме­нее пла­стич­ная из всех гли­ни­стых грун­тов, при ее рас­ти­ра­нии меж­ду паль­ца­ми чув­ству­ют­ся пес­чин­ки, она пло­хо ска­ты­ва­ет­ся в шнур. Ска­тан­ный из су­песи шар рас­сы­па­ет­ся, ес­ли на не­го не­мно­го на­да­вить. Из-за вы­со­ко­го со­дер­жа­ния пес­ка су­песь име­ет срав­ни­тель­но низ­кую по­ри­стость – от 0,5 до 0,7. Со­от­вет­ствен­но она мо­жет со­дер­жать мень­ше вла­ги и, сле­до­ва­тель­но, быть мень­ше под­вер­же­на пу­че­нию.
Луч­шая ста­тья из всех мною пр­осмот­рен­ных на дан­ный мо­мент. Очень по­мог­ли. Спа­си­бо. Бу­ду ре­ко­мен­до­вать.
Бра­во, мне ка­жет­ся это ве­ли­ко­леп­ная идея —
Рик Ком­пью­терс http://pitsoft.weebly.com/blog/rik-kompiuters — здесь.
Что­бы не ска­зать боль­ше. — Ви­део Жен­ский раз­дел или рус­ские филь­мы 2014 го­да но­вин­ки
не­пло­хо — Ин­тер­нет ма­га­зин мат­ра­сов тут
Ка­зах­стан………….ыы­ы­ы­ы­ыы — Офор­мить КРЕДИТ сей­час а так­же займ до 10 ты­сяч руб­лей на кар­ту
КОРОЧЕ, ВСЁ ПОНЯТНО — Бо­лез­ни сфинк­сов а так­же как при­учить дон­ско­го сфинк­са к лот­ку
Мне ка­жет­ся, вы оши­ба­е­тесь — Из­де­лия из де­ре­ва на за­каз или бру­со­вая во­лог­да от­зы­вы
Ка­кие от­лич­ные сло­ва — Топ 10 луч­ших он­лайн игр или иг­рать он­лайн на рус­ском язы­ке
По мо­е­му мне­нию Вы оши­ба­е­тесь. Пи­ши­те мне в PM, по­го­во­рим. — Ко­лен­ный су­став, остео­по­роз или арт­роз ки­сти рук
Со­ста­вит ли Chery Arrizo 7 кон­ку­рен­цию Volkswagen Jetta? Смот­рим тест-драйв,
Оце­ни­те кра­со­ту и мощь Volvo XC70, посмот­рев ви­део тест-драй­ва! а так­же toyota rav4 тест драйв видео
За­ви­дую тем, кто досмот­рел до кон­ца. ин­цест пор­но,
Ис­по­ведь лю­бя­ще­го сы­на или пор­но­рас­ска­зы ху­тор
Я ду­маю, что Вы до­пус­ка­е­те ошиб­ку. Пред­ла­гаю это об­су­дить. Эро­ти­че­ский пор­но рас­сказ laquo Эро­ти­че­ские сны
,
Ин­цест,,Пор­но,и,секс,рас­ска­зы,эро­ти­че­ские,сек­са­пиль­ные,ис­то­рии,на,EroTales,Ин­цест Пор­но и секс рас­ска­зы эро­ти­че­ские сек­са­пиль­ные ис­то­рии на EroTales
fetish raskazi
Ста­тья хо­ро­шая… Но не од­ной ите­ра­тив­ной вер­сии. Кое что бы­ло по­лез­ным. А так ко­неч­но это слиш­ком ма­ло о сор­ти­ров­ках. Уни­вер­саль­ных ал­го­рит­мов не­ту… По сор­ти­ров­кам мож­но це­лую кни­гу на­пи­сать на­столь­ко она объ­ём­на. Для ме­ня лич­но сор­ти­ров­ки со схо­ди­мо­стью N log2N не­ин­те­рес­ны, Мне ин­те­рес­ны сор­ти­ров­ки со схо­ди­мо­стью ~ N. Про эти сор­ти­ров­ки ни сло­ва… Ну да лад­но. Про это во­об­ще ма­ло кто зна­ет. Я вот всё вре­мя за­даю се­бе во­прос… А ка­кая прак­ти­че­ская поль­за от сор­ти­ро­вок? Ну от­сор­ти­ро­вал ты дан­ные и че­го? От это­го они не ста­ли дру­ги­ми, не по­яви­лись не про­па­ли! Для ме­ня прак­ти­че­ская поль­за это на­уч­но-тех­ни­че­ские рас­чё­ты… Осталь­ное в боль­шин­стве слу­ча­ев стра­да­ние фиг­нёй вы­со­ко­го на­чаль­ства… Но к со­жа­ле­нию как раз для это­го и ис­поль­зу­ют ком­пы. Я ду­маю что ес­ли они вдруг про­па­дут, то мы да­же силь­но не по­стра­да­ем…
Зай­мы пен­сио­не­рам, без от­ка­зов <a href=" http://zaym-go.ru/zaymy-pensioneram.html» rel=»nofollow»> зай­мы пен­сио­не­рам
You lasix dosage little good out time for sale in australia the?

Оставить отзыв

Жёлтые поля обязательны к заполнению

   

Можете использовать теги <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre lang=""> <div class=""> <span class=""> <br>