Лек­ция № 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).
Крас­ный цвет — ес­те­ствен­ная сор­ти­ров­ка,
се­рый цвет — вос­хо­дя­щая сор­ти­ров­ка слия­ни­ем

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

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

Очень здо­ров­ская ста­тья! То что на­до. Спа­си­бо.
Ста­тья хо­ро­шая, толь­ко я ни­как не мо­гу най­ти реа­ли­за­цию двух­пу­те­во­го слия­ния
Спа­си­бо Вам огром­ное за со­дер­жа­тель­ные ста­тьи! Они мне очень по­мог­ли в на­пи­са­нии кур­со­вой ра­бо­ты!
Все до­ста­точ­но по­нят­но и чет­ко! И глав­ное вид­на об­щая кар­ти­на, что для очень важ­но при изу­че­нии че­го-то но­во­го У Вас хо­ро­ший стиль!
=)
Ин­те­рес­но, но очень важ­ный слу­чай ес­те­ствен­но­го слия­ния вы не рас­смот­ре­ли. Т.е. учи­ты­вать не толь­ко по­ря­док воз­рас­та­ния уже имею­щих­ся упо­ря­до­чен­ных под­по­сле­до­ва­тель­но­стей (УПП), но и по­ря­док убы­ва­ния. Ка­кая раз­ни­ца сли­вать УПП с на­ча­ла или с кон­ца? Та­ким об­ра­зом, убы­ваю­щая под­по­сле­до­ва­тель­ность бу­дет вы­яв­ле­на и вы­да­на за один про­ход. Да­лее, нет не­об­хо­ди­мо­сти ни де­лать опе­ра­цию рас­щеп­ле­ния (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?
I must say you have very interesting posts here. Your page should go viral.
You need initial traffic only. How to get it? Search for; Etorofer’s
strategies
I see your website needs some unique articles. Writing manually is time consuming, but there is tool for this task. Just search for — Digitalpoilo’s tools
Great website you have here but I was wanting to
know if you knew of any forums that covr thee same topics talked about in this article?
I’d reaply love to be a part off grlup where I can get feed-back from other experienced pekple that share thhe
same interest. If yyou have any recommendations, please let
me know. Thank you! Alsoo visit my site … ασθενεια ικα (Brigitte)
Hi, I think your site might be having browser compatibility issues.
When I look at your blog site in Opera, it looks fie bbut when opening in Internet Explorer, it has some overlapping.
I just wanted to give yyou a quick heads up! Other then that, superb blog! my blog post σεξυ video
http://iproc.ru is very informative, bookmarked
http://iproc.ru is my favorite now
Keep on writing, great job!
http://iproc.ru is very informative, bookmarked
Howdy! This article could not be written much
better! Looking through this article reminds me of my previous roommate!
He continually kept talking about this. I am going
to forward this article to him. Fairly certain he’s going to have a
very good read. Thank you for sharing!
What’s up, after reading this awesome post i am too happy to share my familiarity here with friends.
Hello everyone, it’s my first visit at this website, and piece of writing is in fact fruitful in support of me, keep up posting such content.
Your method of describing all in this piece of writing
is actually good, every one be able to effortlessly be aware of it,
Thanks a lot.

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

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

   

Можете использовать теги <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>