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

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

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

Очень здо­ров­ская ста­тья! То что на­до. Спа­си­бо.
Ста­тья хо­ро­шая, толь­ко я ни­как не мо­гу най­ти реа­ли­за­цию двух­пу­те­во­го слия­ния
Спа­си­бо Вам огром­ное за со­дер­жа­тель­ные ста­тьи! Они мне очень по­мог­ли в на­пи­са­нии кур­со­вой ра­бо­ты!
Все до­ста­точ­но по­нят­но и чет­ко! И глав­ное вид­на об­щая кар­ти­на, что для очень важ­но при изу­че­нии че­го-то но­во­го У Вас хо­ро­ший стиль!
=)
Ин­те­рес­но, но очень важ­ный слу­чай ес­те­ствен­но­го слия­ния вы не рас­смот­ре­ли. Т.е. учи­ты­вать не толь­ко по­ря­док воз­рас­та­ния уже имею­щих­ся упо­ря­до­чен­ных под­по­сле­до­ва­тель­но­стей (УПП), но и по­ря­док убы­ва­ния. Ка­кая раз­ни­ца сли­вать УПП с на­ча­ла или с кон­ца? Та­ким об­ра­зом, убы­ваю­щая под­по­сле­до­ва­тель­ность бу­дет вы­яв­ле­на и вы­да­на за один про­ход. Да­лее, нет не­об­хо­ди­мо­сти ни де­лать опе­ра­цию рас­щеп­ле­ния (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)
Thanks for your personal marvelous posting! I certainly enjoyed reading it,
you are a great author.I will remember to bookmark
your blog and may come back at some point. I want to encourage continue your great work, have a nice day! Also visit my web blog; mink eyelash extensions near me
This design is wicked! You definitely 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!) Excellent job. I really enjoyed what you had to say, and more than that, how you
presented it. Too cool! My blog — nba live coins generator
Thanks for your personal marvelous posting! I actually enjoyed reading it,
you may be a great author. I will remember to bookmark your blog and definitely will come back sometime
soon. I want to encourage yourself to continue your great posts,
have a nice day! My blog post — cs go skin betting websites
This is a topic that’s near to my heart… Best wishes!
Exactly where are your contact details though? Visit my webpage; csgo skins free hack
Ainsi cet emule des Flourens, qui tantot nous effrayait
de sa science lorsqu’il comprimait le cerveau pour obtenir la lethargie, est d’une incroyable ineptie pour le fait
le plus simple en dehors de ses habitudes. Feel free to surf to my webpage … salon massage lyon
magnificent submit, very informative. I wonder why the opposite experts of this sector don’t understand
this. You must proceed your writing. I am sure, you’ve a huge readers’ base already! my webpage :: fifa coins cheapest ps4
Hi to all, the contents present at this web site are in fact awesome for people experience, well, keep
up the nice work fellows. my homepage: mink strip lashes ebay
I do not even know the way I finished up right here, however
I believed this submit used to be great. I do not understand who you might be but certainly you’re going to a famous
blogger in case you are not already. Cheers! Feel free to visit my weblog; csgo skins free
each time i used to read smaller articles or reviews that
also clear their motive, and that is also happening with this
article which I am reading at this time. Take a look at my web blog — madden mobile coin cheat no download no survey
Good way of telling, and nice paragraph to take facts regarding my presentation subject matter, which
i am going to present in institution of higher education. my weblog; csgo skins steam
Hello there, I discovered your web site by way of Google at
the same time as searching for a similar topic,
your site got here up, it seems to be good. I’ve bookmarked it
in my google bookmarks.
Hi there, simply changed into alert to your blog thru Google,
and found that it’s really informative. I am gonna be careful for brussels.
I will appreciate in the event you proceed this in future.
Many other folks will likely be benefited from your writing.
Cheers! Also visit my page :: csgo skins sites (Edward)
I for all time emailed this web site post page to all my associates, as if like
to read it after that my contacts will too. Feel free to surf to my web site diamond silk
lashes wholesale (http://www.grandmadragonproductions.com/UserProfile/tabid/296/userId/172530/Default.aspx)
Hi there, You have done a fantastic job. I will certainly digg it and personally recommend to my friends. I am confident they will be benefited from this web
site. Feel free to visit my web page … margueri.simplesite.com (e-autotechnika24.pl)
It’s perfect time to make a few plans for the future and it is time to be happy.
I’ve read this submit and if I may just I desire to counsel you some attention-grabbing things or
suggestions. Maybe you can write next articles regarding this article. I wish to learn more issues about it! Feel free to surf to my weblog … csgo skins for sale
At this time it sounds like Expression Engine is the top blogging platform out there
right now. (from what I’ve read) Is that what you’re using on your blog? Review my webpage; silk lash extensions sydney
hello!,I love your writing so much! percentage we keep in touch more about your post on AOL?
I require an expert in this space to solve my problem.
Maybe that is you! Looking ahead to look you. Also visit my web-site; pro flight simulator bonus (http://thuthuvan.net/)
I think this is among the most vital info for me. And i’m glad
reading your article. But want to remark on some general things, The website
style is wonderful, the articles is really great : D. Good job,
cheers my blog — nba live coins and cash, http://www.earth-sheltered-garden.com,
До­бро­го вре­ме­ни су­ток!мое имяДмитрий.Я хо­чу­по­де­лить­ся с ва­ми блог об твор­че­стве http://www.russian-artist.ru. Раз­но­об­раз­ный вы­бор изоб­ра­же­ний на лю­бой
вкус. Всем со­ве­тую по­се­тить дан­ный пор­тал.
I’ll immediately seize your rss as I can’t in finding your email subscription link or
e-newsletter service. Do you have any? Kindly allow me recognize so that I
may just subscribe. Thanks. Feel free to surf to my web blog :: ncaa football 09 (Matilda)
bookmarked!!, I love your site! Feel free to visit my blog … christinaister.website-ondemand.com/2017/04/05/counter-strike-global-offensive-is-a-5v5-team-base…
(http://tehran-vst.com/)
Hello would you mind sharing which blog platform you’re using? I’m looking to start my own blog in the near future
but I’m having a difficult time deciding between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your layout seems different then most blogs and I’m looking for something completely unique.
P.S Sorry for getting off-topic but I had to ask! Look at my homepage mink strip eyelashes australia (latincraft.ga)
Nice post. I learn something new and challenging on blogs I stumbleupon every day.
It will always be interesting to read through content from other writers and practice something from other sites. Look at my web site … mink strip eyelashes wholesale (Cassie)
I am sure this article has touched all the internet users, its
really really pleasant post on building up new web site. my web page cs go skins price guide — Rhea,
You can certainly see your enthusiasm within the work you write.
The world hopes for more passionate writers such as
you who aren’t afraid to mention how they believe.
Always go after your heart. my site; mink lash extensions wholesale [Emilio]
One of the most impressive things about Go — Daddy domain promo codes is they are
available to direct you towards all situations. Unlimited space for storing and file transfer might not seem like that big of an deal if all you’re hoping
to do is conserve a personal blog. Use the tips in this article
to find out how you can identify the projects you and also manage by yourself and escape some time
to money.
Link exchange is nothing else but it is just
placing the other person’s weblog link on your page at appropriate place and
other person will also do same in support of you. Check out my web blog: fifa coins for sale xbox
I believe this is one of the most vital information for me.
And i am glad reading your article. However want to remark on few
basic issues, The web site style is ideal, the articles is
truly nice : D. Just right task, cheers Also visit my web site: mink lash extensions nyc (Mohamed)
I do accept as true with all of the concepts you’ve offered
for your post. They’re very convincing and will definitely work. Still, the posts are too short for beginners. May just you please lengthen them a little from next time?
Thanks for the post. Here is my weblog … cs go trade skins for money (http://www.willemsenstagemanagement.nl)
fantastic issues altogether, you simply won a logo new reader.
What may you suggest in regards to your publish that you simply made a few days
in the past? Any certain? my blog: madden mobile coins glitch 2017 (Gwendolyn)
Quality posts is the crucial to interest the people to go to see the web site, that’s what this web site is providing. Here is my web blog — madden mobile coin generator no survey no
download; Yetta,
Hi there, just became aware of your blog through Google, and found that it’s truly informative.
I am gonna watch out for brussels. I will be grateful if you continue
this in future. Many people will be benefited from your writing.
Cheers! my blog post csgo skins free code
Right away I am going away to do my breakfast, later
than having my breakfast coming again to read further news. my weblog … mink lashes near me [Bridgett]
Right now it sounds like Expression Engine is the preferred blogging platform out there right now.
(from what I’ve read) Is that what you are using on your blog? Review my web-site buy cheap nba live coins — Ashleigh -
Hi, yup this article is in fact pleasant and I have
learned lot of things from it regarding blogging. thanks. My blog :: siberian mink lashes nyc (Austin)
Fantastic website you have here but I was curious about if you knew of any community forums that cover the
same topics discussed here? I’d really like to be a part of community where I can get feedback from other knowledgeable individuals
that share the same interest. If you have any suggestions, please
let me know. Thanks! Here is my web blog — nba live coins generator
Very nice write-up. I certainly appreciate this site.
Continue the good work! Feel free to visit my webpage :: perfect silk lashes review — americanrentall.com
-
This piece of writing is truly a pleasant one it assists new web users, who are wishing
in favor of blogging. my weblog … nba live coins and cash (Jefferson)
I don’t even know how I ended up here, but I thought this
post was good. I don’t know who you are but certainly you’re going to
a famous blogger if you aren’t already
Cheers!
Good post but I was wanting to know if you could
write a litte more on this subject? I’d be very
grateful if you could elaborate a little bit further. Many thanks! My web blog … fifa coins reddit (http://freeonlinecasino.co.za/groups/three-best-sports-games-for-microsoft-xbox-360)
These are actually fantastic ideas in concerning blogging.
You have touched some nice things here. Any way keep up wrinting. Also visit my web-site csgo skins free 2017
With havin so much content do you ever run into any problems of plagorism or copyright
violation? My site 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 agreement.
Do you know any methods to help protect against content from
being stolen? I’d really appreciate it. Here is my web-site — madden mobile free coins no download no survey
Wow, incredible weblog structure! How lengthy have you been running a blog for?
you made running a blog look easy. The total
look of your web site is great, let alone the content material! My site: fifa coins cheapest 17
Excellent post. I was checking constantly this blog and I am impressed!
Very useful info particularly the last part I care for such info much.
I was looking for this particular info for a long time.
Thank you and good luck. Here is my homepage … mink strip eyelashes australia (dectro.ro)
We’re a group of volunteers and starting a brand new scheme in our community.
Your site provided us with useful information to work on. You have performed an impressive task and our whole neighborhood might be grateful
to you. My blog post — buy pubg skins (healthcare.randstadusa.com)
You really make it seem so easy with your presentation however I in finding this topic
to be really something which I believe I would by no means
understand. It sort of feels too complex and
very extensive for me. I’m looking forward on your next publish, I will
attempt to get the dangle of it! my webpage — mink lashes extensions (totalmaskin.no)
I see your blog needs some unique & fresh articles. Writing manually is time consuming,
but there is solution for this hard task. Just search for — Miftolo’s tools rewriter
Very good website — bookmarked
It is perfect time to make a few plans for the longer term and it’s time to be happy.
I’ve learn this put up and if I may just I desire to recommend you few attention-grabbing issues or advice.
Maybe you could write subsequent articles referring to this article.
I desire to learn more things approximately it! Here is my web blog: buy hut 17 coins
Incredible! This blog looks exactly like my
old one! It’s on a entirely different topic but it has pretty much the same layout and design.
Excellent choice of colors! Also visit my weblog; cs go skin trade hack
This is a topic that’s near to my heart… Many thanks!
Exactly where are your contact details though?
Hello, i read your blog occasionally and i own a similar one and
i was just curious if you get a lot of spam responses?
If so how do you reduce it, any plugin or anything you can suggest?
I get so much lately it’s driving me mad so any
support is very much appreciated.
Hi there, constantly i used to check blog posts here early in the break of day, as i enjoy
to find out more and more. My web page: buy nhl 17 coins — http://sewingmachinerepair.com.au/,
I have been exploring for a little bit for any high-quality articles or weblog posts on this kind of house .
Exploring in Yahoo I ultimately stumbled upon this website.
Studying this info So i’m happy to express that I’ve an incredibly good uncanny feeling I discovered exactly what I needed.
I so much unquestionably will make sure to do not forget this
site and provides it a glance regularly. Also visit my webpage … cheap csgo skins (tofiqnurmohammadi.com)
Hi there! Someone in my Myspace group shared this site with us
so I came to take a look. I’m definitely enjoying the information. I’m bookmarking and will be tweeting this to
my followers! Terrific blog and fantastic design.
We’re a group of volunteers and starting a brand new
scheme in our community. Your site offered us with
useful information to work on. You have done an impressive task and our entire community can be
grateful to you. Also visit my website :: nba live coins cheap
ブログアフィリを実践するのにキーワード選定は必須です。
キーワード分析をするのに重宝するツールがこちら!
Nice respond in return of this issue with solid arguments
and telling the whole thing concerning that.
Hey superb blog! Does running a blog like this take a lot of work? I have very little understanding of computer programming
however I had been hoping to start my own blog in the near
future. Anyway, should you have any ideas or tips for new
blog owners please share. I know this is off topic however I simply had to ask.
Appreciate it!
I loved as much as you will receive carried out right here.
The sketch is attractive, your authored subject matter
stylish. nonetheless, you command get bought an nervousness over that you wish be delivering
the following. unwell unquestionably come further formerly
again as exactly the same nearly very often inside case you shield this increase.
After I originally commented I appear to have clicked the -Notify me when new comments are added- checkbox and
now whenever a comment is added I get 4 emails with the exact same comment.
There has to be an easy method you are able to remove me from that service?
Appreciate it!

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

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

   

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