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

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

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

Очень здо­ров­ская ста­тья! То что на­до. Спа­си­бо.
Ста­тья хо­ро­шая, толь­ко я ни­как не мо­гу най­ти реа­ли­за­цию двух­пу­те­во­го слия­ния
Спа­си­бо Вам огром­ное за со­дер­жа­тель­ные ста­тьи! Они мне очень по­мог­ли в на­пи­са­нии кур­со­вой ра­бо­ты!
Все до­ста­точ­но по­нят­но и чет­ко! И глав­ное вид­на об­щая кар­ти­на, что для очень важ­но при изу­че­нии че­го-то но­во­го У Вас хо­ро­ший стиль!
=)
Ин­те­рес­но, но очень важ­ный слу­чай ес­те­ствен­но­го слия­ния вы не рас­смот­ре­ли. Т.е. учи­ты­вать не толь­ко по­ря­док воз­рас­та­ния уже имею­щих­ся упо­ря­до­чен­ных под­по­сле­до­ва­тель­но­стей (УПП), но и по­ря­док убы­ва­ния. Ка­кая раз­ни­ца сли­вать УПП с на­ча­ла или с кон­ца? Та­ким об­ра­зом, убы­ваю­щая под­по­сле­до­ва­тель­ность бу­дет вы­яв­ле­на и вы­да­на за один про­ход. Да­лее, нет не­об­хо­ди­мо­сти ни де­лать опе­ра­цию рас­щеп­ле­ния (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.
Thanks for the good writeup. It actually was a leisure account it.
Glance complex to more added agreeable from you! However, how could we keep in touch?
Thanks a lot for sharing this with all folks you actually understand what you’re speaking approximately!
Bookmarked. Kindly also consult with my web site =). We will have a link exchange agreement among us
I’m not sure exactly why but this web site is loading incredibly slow for me.
Is anyone else having this problem or is it a problem on my
end? I’ll check back later on and see if the problem still exists.
This design is wicked! You certainly know how to keep a reader entertained.
Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!) Great job.
I really loved what you had to say, and more than that,
how you presented it. Too cool!
Informative article, just what I needed.
I couldn’t refrain from commenting. Exceptionally well written!
excellent publish, very informative. I’m wondering why the opposite specialists of this sector don’t realize this.
You must continue your writing. I’m sure, you’ve a huge readers’ base already!
Very soon this site will be famous amid all blogging viewers, due to it’s fastidious content
Hi, yes this post is really nice and I have learned lot of things from it concerning blogging.
thanks.
Thanks for another wonderful post. Where
else may anybody get that type of info in such an ideal manner of writing?
I’ve a presentation next week, and I am at the search for such info.
Do you have any video of that? I’d want to find out some additional information.
I blog often and I genuinely thank you for your information. Your article has really peaked my interest.
I am going to take a note of your site and keep checking for new information about once a
week. I subscribed to your Feed as well.
Hi there would you mind letting me know which web host you’re working with?
I’ve loaded your blog in 3 different internet browsers and I must
say this blog loads a lot quicker then most. Can you suggest a good web
hosting provider at a fair price? Many thanks, I appreciate it!
Currently it appears like Movable Type is the best blogging platform out there right now. (from what I’ve read) Is that what you’re using on your blog?
Appreciate this post. Will try it out.
I see your site needs some fresh articles. Writing manually is
time consuming, but there is solution for this. Just search for; Masquro’s strategies
I do not even know how I stopped up here, however
I believed this publish was once great. I don’t recognize who you are however
definitely you are going to a famous blogger if you aren’t
already. Cheers!
You made some decent points there. I looked
on the net for more information about the issue
and found most people will go along with
your views on this web site.
Every weekend i used to pay a visit this web page, because i want enjoyment, for the reason that this this
site conations in fact fastidious funny data too.
Asking questions are truly fastidious thinhg if you are not understanding anything completely,
except this article offers nice understanding yet. My site αστρολογια πανοπουλοσ
Excellent blog you have got here.. It’s hard to
find quality writing like yours nowadays. I seriously appreciate individuals like you!
Take care!!
Great article. I am dealing with some of these issues as
well..
I used to be able to find good information from your blog articles.
Hey there, You’ve done a great job. I will definitely
digg it and personally suggest to my friends.
I’m sure they’ll be benefited from this site.
I got this website from my pal who informed me regarding this website and now this time
I am visiting this web page and reading very informative articles or reviews at this time.
I have read so many content concerning the blogger lovers except this article is truly a pleasant piece of writing, keep
it up. my blog … silk lashes for sale
If you are going for best contents like I do, only pay a quick visit this
website daily since it provides quality contents,
thanks My page :: cs go skins price checker (83.169.35.180)
It is in point of fact a great and helpful piece of information. I am happy that you shared this
useful information with us. Please stay us informed like
this. Thank you for sharing. Review my web page; silk lash extensions adelaide [Alfredo]
It’s amazing to pay a visit this web page and reading the views of all colleagues concerning this piece of writing, while I am also keen of getting experience. My web page: game strategies today (glawpc.com)
Hi there, of course this piece of writing is in fact good and I have learned lot of things from it regarding blogging. thanks. Feel free to visit my web blog :: madden mobile coins no survey
It’s enormous that you are getting ideas from this post as well as from our discussion made here.
You ought to be a part of a contest for one of the best sites on the net.
I most certainly will highly recommend this website! Check out my site :: fifa 17 coins generator xbox one
I do not even know the way I stopped up here, however I assumed this
put up was once great. I do not recognise who
you’re but certainly you are going to a well-known blogger if you are not already. Cheers! Feel free to surf to my website :: cs go skins for sale ebay
If some one needs to be updated with newest technologies then he must be go to see this web site and be up to date all the time. Here is my web site — silk eyelashes vs mink
Very nice article. I absolutely love this site. Keep writing! Here is my page csgo skins betting sites
Hi, I do think your web site might be having browser
compatibility issues. When I look at your blog in Safari, it looks fine however, if opening in Internet Explorer, it’s got some overlapping issues.
I just wanted to give you a quick heads up! Aside from that, great blog! Here is my web site — fifa 17 coins xbox one uk
Very good post. I will be experiencing some of these issues as well.. Here is my blog: individual mink lashes for sale (Sonya)
My coder is trying to convince me to move to .net from PHP.
I have always disliked the idea because of the expenses.
But he’s tryiong none the less. I’ve been using WordPress on a
number of websites for about a year and am concerned about switching to another platform.
I have heard fantastic things about blogengine.net.
Is there a way I can transfer all my wordpress content into it?
Any help would be greatly appreciated!
For newest information you have to pay a quick visit web and on world-wide-web I found this website as a best
web site for newest updates.
Wow, incredible weblog structure! How lengthy have you ever been running a blog for?
you made blogging look easy. The whole glance of your web
site is wonderful, let alone the content material!
Excellent way of explaining, and good article to obtain data on the topic of my presentation subject matter, which i am going to convey in university. Review my web site mink lashes wholesale
When I initially left a comment I seem to have clicked on the -Notify me when new comments are added- checkbox and now whenever
a comment is added I receive 4 emails with the same
comment. Perhaps there is an easy method you can remove me from that service?
Cheers! my web-site fifa coins cheap fifa 17 — http://mydisworld.com/blogs_post.php?id=26582,
This is really interesting, You are a very skilled blogger.
I have joined your rss feed and look forward to seeking more
of your great post. Also, I have shared your web site in my social networks!
Hey There. I found your blog using msn. This is
a really well written article. I will make sure
to bookmark it and return to read more of your useful info.
Thanks for the post. I will certainly return.
With havin so much content and articles do you
ever run into any issues of plagorism or copyright infringement?
My website has a lot of unique content I’ve either written myself or outsourced but it seems a lot
of it is popping it up all over the web without my authorization. Do you know any ways to help reduce content from being stolen? I’d truly appreciate it.
I used to be recommended this website via my cousin. I’m
no longer sure whether this post is written by way of him as nobody
else understand such distinct approximately my difficulty.
You’re incredible! Thanks!
Hello, i think that i noticed you visited my weblog thus i got
here to go back the favor?.I am attempting to in finding things to improve my website!I guess its ok to use
a few of your ideas!!
I have been surfing online more than three hours today,
yet I never found any interesting article like yours. It is pretty worth enough for me. In my view, if all site owners and bloggers made good content
as you did, the web will be much more useful than ever before.
Hello there! This post could not be written much better!
Looking through this post reminds me of my previous roommate!
He constantly kept talking about this. I will forward this post to him.
Pretty sure he will have a good read. I appreciate you for sharing!
you are truly a good webmaster. The website loading pace is amazing.
It sort of feels that you’re doing any unique trick.
Moreover, The contents are masterwork. you have
performed a great process on this topic! Also visit my weblog: cs go skins for money
wonderful post, very informative. I ponder why
the other specialists of this sector do not understand this.
You must continue your writing. I’m confident,
you have a great readers’ base already! Also visit my site … mink eyelash extensions cruelty free
Terrific post however , I was wondering if you could write a litte more on this topic?
I’d be very grateful if you could elaborate a little bit more.
Thank you! Also visit my blog — madden mobile coins for sale amazon
No matter if some one searches for his vital thing, so he/she wishes to be
available that in detail, thus that thing is maintained over here.
constantly i used to read smaller posts which as well clear their motive,
and that is also happening with this piece of
writing which I am reading now.
I read this post completely on the topic of the comparison of
most recent and previous technologies, it’s
awesome article. Here is my web-site — synthetic mink lashes for sale
Howdy! I know this is kinda off topic but I’d
figured I’d ask. Would you be interested in trading links or maybe guest writing a blog article or vice-versa?
My site goes over a lot of the same topics as yours and I think we could greatly benefit from each other.
If you might be interested feel free to shoot me an e-mail.
I look forward to hearing from you! Superb blog by the way! My site: madden mobile coins buy (Elsie)

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

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

   

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