Лек­ция № 5: Пи­ра­ми­даль­ная сор­ти­ров­ка

Ста­тья на­пи­са­но дав­но, и на дан­ный мо­мент тре­бу­ет се­рьёз­ной пе­ре­ра­бот­ки.

Оста­вим в сто­ро­не ре­ли­ги­оз­ные спо­ры о пре­иму­ще­ствах и не­до­стат­ках ал­го­рит­ма Quick Sort (ко­то­рый хо­рош в сред­нем, но тре­бу­ет услож­не­ния для удо­вле­тво­ри­тель­ной ра­бо­ты в худ­шем слу­чае), и бу­дем рас­смат­ри­вать пи­ра­ми­даль­ную сор­ти­ров­ку, как са­мый быст­рый ал­го­ритм из до­ступ­ных (смот­ри­те Лек­цию № 3) для сор­ти­ров­ки не­боль­ших объ­ё­мов дан­ных, уме­щаю­щих­ся в кэш про­цес­со­ра.

Ал­го­ритм пи­ра­ми­даль­ной сор­ти­ров­ки по-ан­глий­ски на­зы­ва­ет­ся «Heap Sort». «Heap» пе­ре­во­дит­ся, как «ку­ча». В свя­зи с этим пи­ра­ми­даль­ную сор­ти­ров­ку ещё на­зы­ва­ют «сор­ти­ров­ка ку­чей»

Пи­ра­ми­даль­ная сор­ти­ров­ка бы­ла пред­ло­же­на Дж. Уи­льям­сом в 1964 го­ду. Это ал­го­ритм сор­ти­ров­ки мас­си­ва про­из­воль­ных эле­мен­тов; тре­буе­мый им до­пол­ни­тель­ный объ­ём па­мя­ти не за­ви­сит от ко­ли­че­ства ис­ход­ных дан­ных. Вре­мя ра­бо­ты ал­го­рит­ма — O\left(n\cdot\ln n\right) в сред­нем, а так­же в луч­шем и худ­шем слу­ча­ях.

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

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

В дан­ной лек­ции бу­дет рас­смот­рен ба­зо­вый ва­ри­ант это­го ал­го­рит­ма, не от­ли­чаю­щий­ся боль­шой ско­ро­стью (в част­но­сти, ра­бо­таю­щий не­су­ще­ствен­но быст­рее сор­ти­ров­ки слия­ни­ем). Бо­лее быст­рые (и слож­ные) ва­ри­ан­ты ал­го­рит­ма вы мо­же­те най­ти в Ин­тер­не­те с по­мо­щью по­ис­ко­вых за­про­сов ти­па «Heap sort modification».

Вез­де да­лее бу­дем счи­тать, что пер­вый эле­мент мас­си­ва име­ет ин­декс 0.

Идея ал­го­рит­ма

Для то­го, что­бы про­яс­нить всё даль­ней­шее из­ло­же­ние, в двух сло­вах опи­шу идею ал­го­рит­ма.

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

Ещё од­но объ­яс­не­ние идеи ал­го­рит­ма мо­же­те посмот­реть в этом ком­мен­та­рии.

Дво­ич­ное де­ре­во

Дво­ич­ное де­ре­во — ст­рук­ту­ра дан­ных, в ко­то­рой каж­дый эле­мент име­ет ле­во­го и/или пра­во­го по­том­ка, ли­бо во­об­ще не име­ет по­том­ков. В по­след­нем слу­чае эле­мент на­зы­ва­ет­ся ли­сто­вым.

Ес­ли эле­мент A име­ет по­том­ка B, то эле­мент A на­зы­ва­ет­ся ро­ди­те­лем эле­мен­та B. В дво­ич­ном де­ре­ве су­ще­ству­ет един­ствен­ный эле­мент, ко­то­рый не име­ет ро­ди­те­лей; та­кой эле­мент на­зы­ва­ет­ся кор­не­вым.

При­мер дво­ич­но­го де­ре­ва по­ка­зан на ри­сун­ке 1:

При­мер дво­ич­но­го де­ре­ва

Ри­су­нок 1. При­мер дво­ич­но­го де­ре­ва

По­чти за­пол­нен­ным дво­ич­ным де­ре­вом на­зы­ва­ет­ся дво­ич­ное де­ре­во, об­ла­даю­щее тре­мя свой­ства­ми:

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

Де­ре­во на ри­сун­ке 1 не яв­ля­ет­ся по­чти за­пол­нен­ным, так как уро­вень 4 не за­пол­нен сле­ва (эле­мент g «ме­ша­ет»), и тре­тий уро­вень (не яв­ляю­щий­ся по­след­ним), не за­пол­нен пол­но­стью.

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

Ну­ме­ра­ция эле­мен­тов по­чти за­пол­нен­но­го де­ре­ва

Ри­су­нок 2. При­мер ну­ме­ра­ции эле­мен­тов по­чти за­пол­нен­но­го де­ре­ва

Не­труд­но ви­деть, что при та­кой ну­ме­ра­ции по­том­ки уз­ла с но­ме­ром i име­ют но­ме­ра 2i+1 и 2i+2 (ес­ли они есть). Ро­ди­тель уз­ла име­ет но­мер \left\lfloor\left(i-1\right)/2\right\rfloor:

На­хож­де­ние по­том­ков и ро­ди­те­ля в мас­си­ве

Ри­су­нок 3. При­мер на­хож­де­ния по­том­ков и ро­ди­те­ля в мас­си­ве

Пи­ра­ми­да

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

При­мер воз­рас­таю­щей пи­ра­ми­ды по­ка­зан на ри­сун­ке:

При­мер воз­рас­таю­щей пи­ра­ми­ды

Ри­су­нок 4. При­мер воз­рас­таю­щей пи­ра­ми­ды

Оче­вид­но, са­мое боль­шое зна­че­ние в воз­рас­таю­щей пи­ра­ми­де име­ет кор­не­вой эле­мент. Од­на­ко, из свойств пи­ра­ми­ды не сле­ду­ет, что зна­че­ния эле­мен­тов умень­ша­ют­ся с уве­ли­че­ни­ем уров­ня. В част­но­сти, на ри­сун­ке 4 эле­мент со зна­че­ни­ем 3 на чет­вёр­том уров­не боль­ше зна­че­ний всех эле­мен­тов, кро­ме од­но­го, на­хо­дя­щих­ся на тре­тьем уров­не.

Важ­ной опе­ра­ци­ей яв­ля­ет­ся от­де­ле­ние по­след­не­го (в смыс­ле ну­ме­ра­ции) эле­мен­та от пи­ра­ми­ды. Не­труд­но до­ка­зать, что в этом слу­чае дво­ич­ное де­ре­во оста­ёт­ся по­чти за­пол­нен­ным, и все свой­ства пи­ра­ми­ды со­хра­ня­ют­ся.

Про­сеи­ва­ние вверх

Рас­смот­рим те­перь за­да­чу при­со­еди­не­ния эле­мен­та с про­из­воль­ным зна­че­ни­ем к воз­рас­таю­щей пи­ра­ми­де. Ес­ли про­сто до­ба­вить эле­мент в ко­нец мас­си­ва, то свой­ство пи­ра­ми­ды (зна­че­ние лю­бо­го эле­мен­та \leqslant зна­че­ния его ро­ди­те­ля) мо­жет быть на­ру­ше­но. Для вос­ста­нов­ле­ния свой­ства пи­ра­ми­ды к до­бав­лен­но­му эле­мен­ту при­ме­ня­ет­ся про­це­ду­ра про­сеи­ва­ния вверх, ко­то­рая опи­сы­ва­ет­ся сле­дую­щим ал­го­рит­мом:

  1. ес­ли эле­мент кор­не­вой, или его зна­че­ние \leqslant зна­че­ния ро­ди­те­ля, то ко­нец;
  2. ме­ня­ем ме­ста­ми зна­че­ния эле­мен­та и его ро­ди­те­ля;
  3. пе­ре­хо­дим к ро­ди­те­лю, и вы­пол­ня­ем для не­го этот же ал­го­ритм, на­чи­ная с пунк­та 1.

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

Про­цесс про­сеи­ва­ния вверх

Ри­су­нок 5. Про­цесс про­сеи­ва­ния вверх до­бав­лен­но­го эле­мен­та

По­сле вы­пол­не­ния дан­ной про­це­ду­ры свой­ство пи­ра­ми­ды бу­дет вос­ста­нов­ле­но, так как:

  • Ес­ли вновь до­бав­лен­ный эле­мент боль­ше ро­ди­те­ля, то он боль­ше и вто­ро­го по­том­ка ро­ди­те­ля (ес­ли вто­рой по­то­мок есть), так как до до­бав­ле­ния но­во­го эле­мен­та бы­ло вы­пол­не­но свой­ство пи­ра­ми­ды, и ро­ди­тель был не мень­ше сво­е­го по­том­ка (на ри­сун­ке 5 сле­ва: се­мёр­ка боль­ше сво­е­го ро­ди­те­ля — чет­вёр­ки, — по­это­му она боль­ше и вто­ро­го по­том­ка чет­вёр­ки — трой­ки). По­сле об­ме­на зна­че­ний эле­мен­та и ро­ди­те­ля свой­ство пи­ра­ми­ды бу­дет вос­ста­нов­ле­но в под­де­ре­ве, кор­нем ко­то­ро­го яв­ля­ет­ся ро­ди­тель с но­вым зна­че­ни­ем (на­при­мер, по­сле об­ме­на ме­ста­ми се­мёр­ки и чет­вёр­ки, се­мёр­ка трой­ка и чет­вёр­ка бу­дут об­ра­зо­вы­вать пра­виль­ное под­де­ре­во).
  • В ре­зуль­та­те об­ме­на свой­ство пи­ра­ми­ды мо­жет быть на­ру­ше­но в от­но­ше­нии ро­ди­те­ля и ро­ди­те­ля ро­ди­те­ля (так как зна­че­ние ро­ди­те­ля ста­ло боль­ше). Про­це­ду­ра вы­зы­ва­ет­ся для ро­ди­тель­ско­го уз­ла, что­бы вос­ста­но­вить это свой­ство.

Ис­ход­ный код про­це­ду­ры про­сеи­ва­ния вверх я не при­во­жу, так как он нам не по­на­до­бит­ся.

Про­сеи­ва­ние вниз

Что де­лать, ес­ли нам нуж­но за­ме­нить кор­не­вой эле­мент на ка­кой-ли­бо дру­гой? В этом слу­чае пи­ра­ми­даль­ную ст­рук­ту­ру дво­ич­но­го де­ре­ва мож­но вос­ста­но­вить с по­мо­щью про­це­ду­ры про­сеи­ва­ния вниз:

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

При­мер про­сеи­ва­ния вниз по­ка­зан на ри­сун­ке:

Про­цесс про­сеи­ва­ния вниз

Ри­су­нок 6. Про­цесс про­сеи­ва­ния вниз из­ме­нён­но­го кор­не­во­го эле­мен­та.
Крас­ным цве­том по­ка­зан те­ку­щий эле­мент

Ис­ход­ный код про­це­ду­ры про­сеи­ва­ния вниз при­ве­дён в ли­стин­ге 1:

template<class T> void SiftDown(T* const heap, int i, int const n)
{   //Просеивает элемент номер i вниз в пирамиде heap.
    //n -- размер пирамиды

    //Идея в том, что вычисляется максимальный элемент из трёх:
    //  1) текущий элемент
    //  2) левый потомок
    //  3) правый потомок
    //Если индекс текущего элемента не равен индексу максималь-
    //  ного, то меняю их местами, и перехожу к максимальному

    //Индекс максимального элемента в текущей тройке элементов:
    int nMax( i );
    //Значение текущего элемента (не меняется):
    T const value( heap[i] );
     
    while ( true )
    { //Рассматривается элемент i и его потомки i*2+1 и i*2+2
      //В начале каждой итерации nMax == i и value == heap[i]

        int childN( i*2+1 ); //Индекс левого потомка
        //Если есть левый потомок и он больше текущего элемента,
        if ( ( childN < n ) && ( heap[childN] > value      ) )
            nMax = childN; //  то он считается максимальным
           
        ++childN; //Индекс правого потомка
        //Если есть правый потомок и он больше максимального,
        if ( ( childN < n ) && ( heap[childN] > heap[nMax] ) )
            nMax = childN; //  то он считается максимальным

        //Если текущий элемент является максимальным из трёх
        //  (т.е. если он больше своих детей), то конец:
        if ( nMax == i ) break;
       
        //Меняю местами текущий элемент с максимальным:
        heap[i] = heap[nMax]; heap[nMax] = value;
        //  при этом значение value будет в ячейке nMax,
        //  поэтому в начале следующей итерации значение value
        //  правильно, т.к. мы переходим именно к этой ячейке

        //Переходим к изменившемуся потомку
        i = nMax;

    };
}

Ли­стинг 1. Функ­ция про­сеи­ва­ния вниз в воз­рас­таю­щей пи­ра­ми­де

Внут­ри цик­ла while име­ют­ся 5 услов­ных опе­ра­то­ров (опе­ра­то­ры && по су­ти то­же яв­ля­ют­ся услов­ны­ми). Эти опе­ра­то­ры яв­ля­ют­ся мед­лен­ны­ми. Их ко­ли­че­ство мож­но со­кра­тить, но то­гда код бу­дет слож­но чи­та­ем.

Кор­рект­ность про­це­ду­ры про­сеи­ва­ния вниз пред­ла­гаю вам до­ка­зать са­мо­сто­я­тель­но.

По­строе­ние пи­ра­ми­ды

До­пу­стим, у нас есть про­из­воль­ный на­бор из n эле­мен­тов, и мы хо­тим по­стро­ить из не­го пи­ра­ми­ду. Са­мый про­стой спо­соб это­го до­бить­ся — на­чать с пу­стой пи­ра­ми­ды, и до­бав­лять в неё эле­мен­ты один за дру­гим, каж­дый раз вы­зы­вая про­це­ду­ру про­сеи­ва­ния вверх для но­во­го эле­мен­та. На­зо­вём этот ме­тод по­строе­ния пи­ра­ми­ды «ме­то­дом про­сеи­ва­ния вверх». При­мер ра­бо­ты ал­го­рит­ма по­ка­зан на ри­сун­ке:

Ани­ма­ция про­сто­го ал­го­рит­ма по­строе­ния пи­ра­ми­ды

Ри­су­нок 7. Ани­ма­ция про­сто­го ал­го­рит­ма по­строе­ния пи­ра­ми­ды

Рас­счи­та­ем быст­ро­дей­ствие это­го ме­то­да в са­мом пло­хом слу­чае. Пусть мас­сив уже от­сор­ти­ро­ван по воз­рас­та­нию, и каж­дый до­бав­ляе­мый эле­мент вы­нуж­ден про­сеи­вать­ся вверх до са­мо­го кор­ня. То­гда при до­бав­ле­нии эле­мен­та но­мер i нам по­тре­бу­ет­ся O\left(\ln\left(i+1\right)\right) опе­ра­ций. Мы де­ла­ем эту про­це­ду­ру для всех i от 0 до n-1:

T_1\left(n\right)=\sum_{i=0}^{n-1}{O\left(\ln\left(i+1\right)\right)}=O\left(\sum_{i=2}^n{\ln i}\right).
(1)

Оце­ним сум­му в вы­ра­же­нии (1) с по­мо­щью опре­де­лён­но­го ин­тег­ра­ла:

\int\limits_2^{n+1}{\ln\left(x-1\right)dx} < \sum_{i=2}^n{\ln i} < \int\limits_2^{n+1}{\ln x dx}.
(2)

Вы­чис­ляя ин­тег­ра­лы, по­лу­ча­ем:

n\ln n -n+1 < \sum_{i=2}^n{\ln i} < \left(n+1\right)\cdot\ln \left(n+1\right) -n-2\ln2+1.
(3)

Это озна­ча­ет, что:

T_1\left(n\right)=O\left(n\cdot\ln n\right).
(4)

На са­мом де­ле пи­ра­ми­ду мож­но по­стро­ить быст­рее. Для это­го за­пол­ним де­ре­во эле­мен­та­ми в про­из­воль­ном по­ряд­ке (на­при­мер так, как они идут в мас­си­ве из­на­чаль­но), и бу­дем его ис­прав­лять.

За­ме­тим, что ес­ли у нас есть две пи­ра­ми­ды, то, ес­ли их со­еди­нить об­щим кор­нем, а за­тем про­се­ять ко­рень вниз, то мы по­лу­чим но­вую боль­шую пи­ра­ми­ду. Де­ре­вья, со­сто­я­щие из од­но­го эле­мен­та, за­ве­до­мо яв­ля­ют­ся пи­ра­ми­да­ми, по­это­му нач­нём с на­бо­ра ли­сто­вых эле­мен­тов, и бу­дем со­еди­нять имею­щие­ся пи­ра­ми­ды по­пар­но до тех пор, по­ка не по­лу­чим од­ну боль­шую пи­ра­ми­ду. Пер­вый до­бав­ляе­мый ко­рень име­ет ин­декс n_0=\left\lfloor n/2 \right\rfloor-1. Ал­го­ритм сле­дую­щий: «для всех i от n_0 до 0 вы­зы­ва­ем про­це­ду­ру про­сеи­ва­ния эле­мен­та вниз». На­зо­вём этот ме­тод по­строе­ния пи­ра­ми­ды «ме­то­дом про­сеи­ва­ния вниз».

Вы­чис­лим быст­ро­дей­ствие это­го ал­го­рит­ма в худ­шем слу­чае. Пусть мас­сив от­сор­ти­ро­ван по воз­рас­та­нию, и каж­дый до­бав­ляе­мый ко­рень дол­жен быть про­се­ян в са­мый низ стро­я­щей­ся пи­ра­ми­ды. Вы­со­та де­ре­ва при­мер­но рав­на \log_2n, глу­би­на за­ле­га­ния эле­мен­та но­мер i в де­ре­ве рав­на \log_2i, по­это­му он бу­дет про­сеи­вать­ся вниз \log_2n-\log_2i ша­гов. То­гда об­щее вре­мя по­строе­ния пи­ра­ми­ды бу­дет рав­но:

T_2\left(n\right)=O\left(\sum_{i=n/2}^1{\left(\ln n-\ln i\right)}\right).
(5)

Оце­ни­вая сум­му ин­тег­ра­ла­ми ана­ло­гич­но (2), (3), по­лу­чим:

T_2\left(n\right)=O\left(n\right).
(6)

От­сю­да сле­ду­ет, что для боль­шо­го чис­ла эле­мен­тов T_2\left(n\right) бу­дет мень­ше, чем T_1\left(n\right). Бо­лее точ­ные оцен­ки да­дут, что T_2\left(n\right) < T_1\left(n\right) для лю­бых n, так как, во пер­вых, при по­строе­нии пи­ра­ми­ды ме­то­дом про­сеи­ва­ния вверх про­це­ду­ра про­сеи­ва­ния вы­зы­ва­ет­ся в 2 ра­за боль­ше раз, чем при по­строе­нии ме­то­дом про­сеи­ва­ния вниз, и, во вто­рых, эле­мен­ты с но­ме­ра­ми от n/2 до n про­сеи­ва­ют­ся вверх на боль­шее рас­стоя­ние, чем рас­стоя­ние, на ко­то­рое про­сеи­ва­ют­ся вниз эле­мен­ты от n/2 до 0. По­это­му в даль­ней­шем бу­дем стро­ить пи­ра­ми­ду ме­то­дом про­сеи­ва­ния вниз.

Сор­ти­ров­ка

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

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

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

На са­мом де­ле пред­ло­жен­ный спо­соб — са­мый про­стой и быст­рый (в том смыс­ле, что ни­че­го луч­ше по­ка не при­ду­ма­но) из всех воз­мож­ных спо­со­бов вос­ста­но­вить пи­ра­ми­ду с от­сут­ствую­щим кор­не­вым эле­мен­том

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

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

По ме­ре ра­бо­ты ал­го­рит­ма, часть мас­си­ва, за­ня­тая де­ре­вом, умень­ша­ет­ся, а в кон­це мас­си­ва на­кап­ли­ва­ет­ся от­сор­ти­ро­ван­ный ре­зуль­тат.

Реа­ли­за­ция пи­ра­ми­даль­ной сор­ти­ров­ки на язы­ке про­грам­ми­ро­ва­ния C++ при­ве­де­на в ли­стин­ге 2 (ис­поль­зу­ет­ся про­це­ду­ра про­сеи­ва­ния вниз из ли­стин­га 1):

template<class T> void HeapSort(T* const heap, int n)
{   //Пирамидальная сортировка массива heap.
    //  n -- размер массива
 
    //Этап 1: построение пирамиды из массива
    for(int i(n/2-1); i>=0; --i) SiftDown(heap, i, n);
   
    //Этап 2: сортировка с помощью пирамиды.
    //  Здесь под «n» понимается размер пирамиды
    while( n > 1 ) //Пока в пирамиде больше одного элемента
    {
        --n; //Отделяю последний элемент

        //Меняю местами корневой элемент и отделённый:
        T const firstElem( heap[0] );
        heap[0] = heap[n];
        heap[n] = firstElem;
       
        //Просеиваю новый корневой элемент:
        SiftDown(heap, 0, n);
    }
}

Ли­стинг 2. Пи­ра­ми­даль­ная сор­ти­ров­ка

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

T_3\left(n\right)=O\left(n\cdot\ln n\right).
(7)

То­гда об­щее вре­мя сор­ти­ров­ки (с учё­том по­строе­ния пи­ра­ми­ды) бу­дет рав­но:

T\left(n\right) = T_2\left(n\right)+T_3\left(n\right) = O\left(n\right)+O\left(n\cdot\ln n\right) = O\left(n\cdot\ln n\right).
(8)

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

Мы уже вы­яс­ни­ли с по­мо­щью тео­ре­ти­че­ских оце­нок, что вре­мя ра­бо­ты ал­го­рит­ма пи­ра­ми­даль­ной сор­ти­ров­ки рав­но: T\left(n\right) = O\left(n\cdot\ln\left(n\right)\right). По­лез­но так­же знать, че­му ра­вен не­из­ве­ст­ный ко­эф­фи­ци­ент пе­ред n\cdot\ln\left(n\right) при вы­пол­не­нии сор­ти­ров­ки на ре­аль­ной вы­чис­ли­тель­ной си­сте­ме.

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

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

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

Мой про­цес­сор: Intel Mobile Core 2 Duo T7500 (во вре­мя те­стов про­грам­ма ра­бо­та­ла на од­ном яд­ре). Так­то­вая ча­сто­та: 2.2 ГГц. Кэш L2: 4 МБ, 16-ас­со­ци­а­тив­ный, 64 бай­та на стро­ку.

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

От­но­ше­ние вре­ме­ни пи­ра­ми­даль­ной сор­ти­ров­ки к n∙ln(n)

Ри­су­нок 8. От­но­ше­ние вре­ме­ни пи­ра­ми­даль­ной сор­ти­ров­ки к n\cdot\ln\left(n+1\right)

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

  1. Ал­го­ритм от­но­си­тель­но мед­лен­но ра­бо­та­ет, ко­гда чис­ло сор­ти­руе­мых эле­мен­тов мень­ше сот­ни. Для ма­ло­го чис­ла эле­мен­тов же­ла­тель­но ис­поль­зо­вать сор­ти­ро­воч­ные се­ти; об этом я рас­ска­жу в од­ной из сле­дую­щих лек­ций.
  2. Ко­гда ко­ли­че­ство сор­ти­руе­мых дан­ных на­чи­на­ет пре­вы­шать раз­мер кэ­ша про­цес­со­ра (в на­шем слу­чае мил­ли­он чи­сел по 4 бай­та), ско­рость сор­ти­ров­ки па­да­ет. Это вы­зва­но тем, что ал­го­ритм об­ра­ща­ет­ся к эле­мен­там мас­си­ва до­воль­но слу­чай­ным об­ра­зом (с точ­ки зре­ния ал­го­рит­ма ра­бо­ты кэ­ша). По ме­ре то­го, как всё мень­шая часть дан­ных умень­ша­ет­ся в кэ­ше, ско­рость ра­бо­ты ал­го­рит­ма всё бо­лее опре­де­ля­ет­ся ско­ро­стью ра­бо­ты опе­ра­тив­ной па­мя­ти, а не ско­ро­стью ра­бо­ты кэ­ша. В од­ной из сле­дую­щих лек­ций мы устра­ним этот не­до­ста­ток.

355 отзывов на запись «Лек­ция № 5: Пи­ра­ми­даль­ная сор­ти­ров­ка»

Спа­си­бо Вам огром­ное за лек­цию. Очень мне по­мог­ла.
Те­перь все по­нят­но! Спо­си­бо!
Спа­си­бо
Чё-то я нихуя не по­нял.
Очень жаль
Все по­нят­но, но сту­ден­там ко­то­рые не зна­ют С++ слож­но­ва­то его чи­тать. ИМХО луч­ше па­ра­л­лель­но (ря­дом с имею­щи­ми­ся) сде­лать при­ме­ры на Java или псев­до­ко­де ка­ком ни­будь. Так бу­дет удоб­нее.
>> сде­лать при­ме­ры на Java
уж, ес­ли зна­ешь джа­ву, то си не­слож­но по­нять бу­дет..
Ни­хе­ра не по­нял, так как всё-та­ки со­став­лять пи­ра­ми­ду? Как её по­том сор­ти­ро­вать, мож­но по­по­нят­нее???
В пол­но­стью от­сор­ти­ро­ван­ном мас­си­ве каж­дый сле­дую­щий эле­мент боль­ше преды­ду­ще­го (и, зна­чит, боль­ше всех преды­ду­щих). Пи­ра­ми­да же — это ча­стич­но от­сор­ти­ро­ван­ный мас­сив. В ней эле­мент но­мер i боль­ше эле­мен­тов с но­ме­ра­ми и (эле­мен­ты ну­ме­ру­ют­ся с ну­ля). Со­от­вет­ствен­но, по­строе­ние пи­ра­ми­ды сво­дит­ся к осо­бой сор­ти­ров­ке мас­си­ва, что­бы вы­пол­ня­лось это свой­ство. При этом та­кая «не­пол­ная» сор­ти­ров­ка де­ла­ет­ся го­раз­до быст­рее, чем пол­ная сор­ти­ров­ка мас­си­ва, так как от­сор­ти­ро­ван­ные це­поч­ки ко­рот­кие. До­пу­стим, у нас име­ет­ся по­сле­до­ва­тель­ность чи­сел: 1, 4, 2, 7, 8, 0, 5, 2, 6. Что­бы по­стро­ить пи­ра­ми­ду, нуж­но до­бить­ся, что­бы все эле­мен­ты но­мер i бы­ли боль­ше эле­мен­тов но­мер и . На­при­мер, ну­ле­вой эле­мент дол­жен быть боль­ше пер­во­го и вто­ро­го. В на­шем при­ме­ре это не так, по­это­му по­ме­ня­ем ну­ле­вой эле­мент и пер­вый: 4, 1, 2, 7, 8, 0, 5, 2, 6. Пер­вый эле­мент (еди­ни­ца) дол­жен быть боль­ше тре­тье­го (се­мёр­ки) и чет­вёр­то­го (вось­мёр­ки). Для это­го по­ме­ня­ем ме­ста­ми еди­ни­цу и вось­мёр­ку: 4, 8, 2, 7, 1, 0, 5, 2, 6. По­ме­ня­ем ме­ста­ми ну­ле­вой и пер­вый эле­мен­ты, что­бы вос­ста­но­вить по­ря­док в на­ча­ле: 8, 4, 2, 7, 1, 0, 5, 2, 6. Сно­ва пер­вый и тре­тий не в по­ряд­ке. По­ме­ня­ем ме­ста­ми чет­вёр­ку и се­мёр­ку: 8, 7, 2, 4, 1, 0, 5, 2, 6. Вто­рой эле­мент (двой­ка) дол­жен быть боль­ше пя­то­го (ну­ля) и ше­сто­го (пя­тёр­ки). Это не так. По­ме­ня­ем ме­ста­ми двой­ку и пя­тёр­ку: 8, 7, 5, 4, 1, 0, 2, 2, 6. Ана­ло­гич­но, чет­вёр­ка долж­на быть боль­ше по­след­них двой­ки и ше­с­тёр­ки. По­ме­ня­ем ме­ста­ми чет­вёр­ку и ше­с­тёр­ку: 8, 7, 5, 6, 1, 0, 2, 2, 4. По­след­ние пять эле­мен­тов не с чем срав­ни­вать; их мы не тро­га­ем. Те­перь свой­ство пи­ра­ми­ды вы­пол­не­но для всех эле­мен­тов. Пи­ра­ми­да по­строе­на. Об­ра­ти вни­ма­ние, что пя­тёр­ка ни­как не свя­за­на с ше­с­тёр­кой, по­это­му они оста­ют­ся в «не­пра­виль­ном» по­ряд­ке (по воз­рас­та­нию, а не по убы­ва­нию, как мы сей­час хо­тим). По­сле то­го, как пи­ра­ми­да по­строе­на, из неё мож­но по­лу­чить пол­но­стью от­сор­ти­ро­ван­ный мас­сив. Осо­бен­ность пи­ра­ми­ды в том, что в её вер­ши­не (ну­ле­вой эле­мент) на­хо­дит­ся мак­си­маль­ный эле­мент сре­ди всех эле­мен­тов пи­ра­ми­ды. Но мак­си­маль­ный эле­мент дол­жен быть в кон­це мас­си­ва. По­ме­ня­ем ме­ста­ми ну­ле­вой и по­след­ний эле­мен­ты, и боль­ше не бу­дем по­след­ний эле­мент счи­тать ча­стью пи­ра­ми­ды: 4, 7, 5, 6, 1, 0, 2, 2 | 8. Пи­ра­ми­да при этом на­ру­ша­ет­ся. Вос­ста­нав­ли­ва­ем её так, как стро­и­ли вна­ча­ле (вось­мёр­ку при этом не учи­ты­ва­ем): 7, 6, 5, 4, 1, 0, 2, 2 | 8. Сно­ва са­мый боль­шой эле­мент пи­ра­ми­ды на­хо­дит­ся вна­ча­ле. Этот эле­мент — са­мый боль­шой из остав­ших­ся сле­ва от вось­мёр­ки. По­это­му он дол­жен быть пе­ред ней. Ме­ня­ем ме­ста­ми ну­ле­вой эле­мент и по­след­ний эле­мент пи­ра­ми­ды, и от­де­ля­ем по­след­ний эле­мент от пи­ра­ми­ды: 2, 6, 5, 4, 1, 0, 2 | 7, 8. Вос­ста­нав­ли­ва­ем пи­ра­ми­ду: 6, 4, 5, 2, 1, 0, 2 | 7, 8. Ме­ня­ем ме­ста­ми на­чаль­ный и по­след­ний эле­мен­ты пи­ра­ми­ды, от­де­ля­ем по­след­ний эле­мент: 2, 4, 5, 2, 1, 0 | 6, 7, 8. Вос­ста­нав­ли­ва­ем пи­ра­ми­ду: 5, 4, 2, 2, 1, 0 | 6, 7, 8. Ме­ня­ем ме­ста­ми на­чаль­ный и по­след­ний эле­мен­ты пи­ра­ми­ды, от­де­ля­ем по­след­ний эле­мент: 0, 4, 2, 2, 1 | 5, 6, 7, 8. Вос­ста­нав­ли­ва­ем пи­ра­ми­ду: 4, 2, 2, 0, 1 | 5, 6, 7, 8. Ме­ня­ем ме­ста­ми на­чаль­ный и по­след­ний эле­мен­ты пи­ра­ми­ды, от­де­ля­ем по­след­ний эле­мент: 1, 2, 2, 0 | 4, 5, 6, 7, 8. Вос­ста­нав­ли­ва­ем пи­ра­ми­ду: 2, 1, 2, 0 | 4, 5, 6, 7, 8. Ме­ня­ем ме­ста­ми на­чаль­ный и по­след­ний эле­мен­ты пи­ра­ми­ды, от­де­ля­ем по­след­ний эле­мент: 0, 1, 2 | 2, 4, 5, 6, 7, 8. Вос­ста­нав­ли­ва­ем пи­ра­ми­ду: 2, 1, 0 | 2, 4, 5, 6, 7, 8. Ме­ня­ем ме­ста­ми на­чаль­ный и по­след­ний эле­мен­ты пи­ра­ми­ды, от­де­ля­ем по­след­ний эле­мент: 0, 1 | 2, 2, 4, 5, 6, 7, 8. Вос­ста­нав­ли­ва­ем пи­ра­ми­ду: 1, 0 | 2, 2, 4, 5, 6, 7, 8. Ме­ня­ем ме­ста­ми на­чаль­ный и по­след­ний эле­мен­ты пи­ра­ми­ды, от­де­ля­ем по­след­ний эле­мент: 0 | 1, 2, 2, 4, 5, 6, 7, 8. В пи­ра­ми­де остал­ся един­ствен­ный эле­мент. Он са­мый ма­лень­кий из всех. Про­сто при­со­еди­ня­ем его к мас­си­ву: 0, 1, 2, 2, 4, 5, 6, 7, 8. Вот и всё! Мы лег­ко и быст­ро от­сор­ти­ро­ва­ли мас­сив из де­вя­ти чи­сел.
Я счи­таю, что пи­ра­ми­даль­ная сор­ти­ров­ка — са­мый быст­рый из всех ко­гда-ли­бо при­ду­ман­ных ал­го­рит­мов сор­ти­ров­ки про­из­воль­ных чи­сел. Од­на­ко че­ло­ве­ку свой­ствен­но сор­ти­ро­вать чис­ла по-дру­го­му. Ес­ли дать ко­му-ни­будь чис­ла на сор­ти­ров­ку, то он обыч­но де­ла­ет так: про­смат­ри­ва­ет все имею­щие­ся чис­ла, на­хо­дит ми­ни­маль­ное, впи­сы­ва­ет его на пер­вое ме­сто ре­зуль­ти­рую­ще­го спис­ка, а в ис­ход­ном спис­ке вы­чёр­ки­ва­ет. Сно­ва про­смат­ри­ва­ет ис­ход­ный спи­сок, на­хо­дит ми­ни­маль­ное чис­ло из остав­ших­ся, вы­чёр­ки­ва­ет его и за­пи­сы­ва­ет на вто­рое ме­сто ре­зуль­та­та. И так да­лее. Та­ким спо­со­бом удоб­но сор­ти­ро­вать не­боль­шое ко­ли­че­ство чи­сел (до пя­ти­де­ся­ти). Ес­ли же дать че­ло­ве­ку от­сор­ти­ро­вать, на­при­мер, ты­ся­чу чи­сел, то этот про­цесс мо­жет от­нять у не­го не­де­лю, в то вре­мя как на сор­ти­ров­ку пи­ра­ми­дой уй­дёт око­ло трёх ча­сов (ес­ли на­пи­сать все чис­ла на бу­маж­ках и рас­по­ло­жить их в ви­де пи­ра­ми­ды).
Это не са­мый быст­рый спо­соб сор­тирв­ки, есть ал­го­ритм сор­ти­ров­ки ско­рость ко­то­ро­го оце­ни­ва­ет­ся как О(nLogLognLogLogLogn)
Да мож­но и за ли­ней­ное вре­мя сор­ти­ро­вать, под­сче­том.
Од­на­ко на прак­ти­ке (с уче­том до­пол­ни­тель­ной па­мя­ти) быст­рая сор­ти­ров­ка + пи­ра­ми­даль­ная — са­мое оп­ти­маль­ное.
О как! Вро­де ра­бо­та­ет.
template void HeapSort(T* const heap, int n)
{   //Пирамидальная сортировка массива heap.
    //  n — размер массива
n — по-мо­е­му это не раз­мер, а раз­мер-1. И зна­чит, ес­ли я за­хо­чу сор­ти­ро­вать по убы­ва­нию, мне до­ста­точ­но ли­бо не ме­нять ме­ста­ми ну­ле­вой эле­мент и по­след­ний эле­мент пи­ра­ми­ды, ли­бо что­бы эле­мент но­мер i был мень­ше эле­мен­тов с но­ме­ра­ми 2*i+1 и 2*i+2?
Ы! Не ме­нять ме­ста­ми ну­ле­вой эле­мент и по­след­ний эле­мент пи­ра­ми­ды нель­зя, ина­че фиг­ня по­лу­ча­ет­ся! { 8, 7, 5, 6, 4, 0, 2, 2, 1 }
:O
template void SiftDown(T* const heap, int i, int const n)
{  

        if ( ( childN < n ) && ( heap[childN] < value) ) nMax = childN;

        if ( ( childN < n ) && ( heap[childN] < heap[nMax] ) ) nMax = childN;

}
Так вро­де сор­ти­ру­ет по убы­ва­нию.
Х-м, хо­тя ме­няя зна­ки срав­не­ния мож­но из­бе­жать пе­ре­ста­нов­ки ну­ле­во­го эле­мен­та и по­след­не­го эле­мент пи­ра­ми­ды, тем са­мым не­мно­го уско­рив ал­го­ритм.
Со­ри, с n всё нор­маль­но, это раз­мер.
Ха! Не ме­нять ну­ле­вой эле­мент и по­след­ний эле­мент пи­ра­ми­ды то­же мож­но. Из-за этой ду­рац­кой n всё ко­ря­во ра­бо­та­ло Так и удоб­ней — до­ста­точ­но три функ­ции (2 сор­ти­ров­ки и од­на по по­строе­нию пи­ра­ми­ды).
Не, всё-та­ки чушь — не ме­няю эле­мен­ты ме­ста­ми во что по­лу­ча­ет­ся:
1,2,4,10 -> 10,2,4,1
Ме­няю зна­ки (при этом остав­ляя сме­ну ме­ста эле­мен­тов) — всё норм.
Не ме­нять ме­ста­ми пер­вый и по­след­ний эле­мен­ты пи­ра­ми­ды нель­зя, так как пер­вый эле­мент — мак­си­маль­ный, но по­след­ний — не обя­за­тель­но ми­ни­маль­ный. Пи­ра­ми­да по­то­му так быст­ро и стро­ит­ся: она в ка­ком-то смыс­ле яв­ля­ет­ся «не­до­сор­ти­ро­ван­ным» мас­си­вом. Об­мен эле­мен­тов ме­ста­ми поз­во­ля­ет вы­нуть из пи­ра­ми­ды мак­си­маль­ный эле­мент, и ис­клю­чить его из об­ра­бот­ки умень­ше­ни­ем раз­ме­ра пи­ра­ми­ды на еди­ни­цу. Вы пра­виль­но со­об­ра­зи­ли, что из­ме­не­ние зна­ков «боль­ше» на «мень­ше» поз­во­ля­ет из­ме­нить по­ря­док сор­ти­ров­ки на про­ти­во­по­лож­ный.
Что за хуй­на во­об­ще, у нас та­ко­го ни­где нэту, Бор­жом­ская сор­ти­ров­ка са­мая луч­шая!
Из­де­ва­е­тесь? Я урав­но­ве­шен­ный че­ло­век, ме­ня так про­сто не вы­ве­дешь
Иде­аль­но. Ан­тон, вы мо­ло­дец!
Бра­во!
Сла­ва бо­гу ,един­ствен­ное нор­маль­ное опи­са­ние в рунэте)))
Боль­шое спа­си­бо за опи­са­ние сор­ти­ро­вок и их реа­ли­за­цию по­мог­ло быст­ро и с ми­ни­маль­ны­ми тру­до­за­тра­та­ми во всем разо­брать­ся)
Heapsort ру­лит!!! Все­гда ис­поль­зую его ко­гда о мас­си­ве ни­че­го за­ран­нее не из­вест­но, так как у не­го нет худ­ших слу­ча­ев…
Та­гил ру­лит, раз­ру­ли­ва­ет Та­гил!! =)
Спа­си­бо огром­ное!)На­пи­са­но очень до­ступ­но.Чёт­ко рас­пи­са­но.Осо­бен­но мне по­нра­ви­лась ани­ма­ция.С удо­воль­стви­ем бу­ду в даль­ней­шем за­хо­дить на ваш сайт.
Бра­во!
Учеб­ник Никлау­са Вир­та и ви­ки­пе­дия по пи­ра­ми­даль­ной сор­ти­ров­ке — нерв­но ку­рят в сто­рон­ке!
По­нра­ви­лось, боль­шое спа­си­бо. Хо­чет­ся ви­деть про­дол­же­ние!
Спа­си­бо, опи­са­но на­мно­го луч­ше чем в дру­гих ис­точ­ни­ках!
Спа­си­бо боль­шое. Дей­стви­тель­но до­ступ­но на­пи­са­но. И ещё! вы под­твер­ди­ли мою тео­рию о том, что мож­но сор­ти­ро­вать сра­зу за­дан­ный мас­сив, а не каж­дый эле­мент от­дель­но за­но­сить и про­сеи­вать.
Мо­ло­ток!
Спа­си­бо! На­ко­нец, разо­бра­лась с сор­ти­ров­кой этой!
Боль­шое спа­си­бо за ста­тью.
Есть во­прос: «Верх­няя гра­ни­ца» ко­ли­че­ства эле­мен­тов мас­си­ва, с ко­то­ры­ми наи­бо­лее эф­фек­тив­но ра­бо­та­ет ал­го­ритм за­ви­сит, как по­ка­за­но, от раз­ме­ра кэ­ша про­цес­со­ра. А чем обос­но­ва­на ниж­няя гра­ни­ца в 100 эле­мен­тов и мож­но ли ее то­же при­вя­зать к ап­па­рат­но­му обес­пе­че­нию?
Ду­маю, «ниж­няя гра­ни­ца» в ос­нов­ном опре­де­ля­ет­ся внут­рен­ни­ми свой­ства­ми са­мо­го ал­го­рит­ма, а не ха­рак­те­ри­сти­ка­ми обо­ру­до­ва­ния. Воз­мож­но, мо­дифи­ци­ро­ван­ные вер­сии пи­ра­ми­даль­ной сор­ти­ров­ки ра­бо­та­ют луч­ше для ма­ло­го ко­ли­че­ства чи­сел.
Боль­шое спа­си­бо
я чёт не пол­ня­ла эт на ка­ком язы­ке ли­стинг на­пи­сан?!!!??????
Это C++.
Боль­шое спа­си­бо за опи­са­ние!)
Очень до­ступ­но рас­ска­за­но) Воз­ник та­кой во­прос:
А вот что­бы сор­ти­ро­вать по убы­ва­нию.. да мож­но по­ме­нять знак на про­ти­во­по­лож­ный;
а мож­но ли про­сто «сдви­гать» ле­вую гра­ни­цу пи­ра­ми­ды(т.е. мы про­сто от­се­чём пер­вый эле­мент вме­сто по­след­не­го) и де­лать про­сеи­ва­ние вверх?? Долж­но же по­лу­чить­ся
Да, долж­но по­лу­чить­ся.
Огром­ное спа­си­бо, рас­пи­са­но про­сто и по­нят­но.
Мож­но дан­ным ме­то­дом от­сор­ти­ро­вать спи­сок эле­мен­тов сим­воль­но­го ти­па?
Да, спа­си­бо, ко­неч­но, бо­лее-ме­нее об­щие чер­ты ста­ли по­нят­ны. Как по­же­ла­ние — по­лез­но бы­ло бы про­ве­сти па­ра­л­лель с ме­то­дом сор­ти­ров­ки пу­зырь­ком — ведь фак­ти­че­ски тут та­кая же идея ис­поль­зу­ет­ся, толь­ко «всплы­ва­ние» про­из­во­дит­ся в ча­стич­но упо­ря­до­чен­ном мно­же­стве. То­гда сра­зу ста­но­вят­ся по­нят­ны все дей­ствия, в том чис­ле, по­че­му кор­не­вой эле­мент в ре­зуль­та­те бу­дет яв­лять­ся наи­боль­шим/наи­мень­шим эле­мен­том мно­же­ства. И еще. Вы ис­поль­зу­е­те для по­строе­ния де­ре­ва ме­тод про­се­ва вниз, но по­че­му-то о нем (имен­но о ме­то­де по­строе­ния де­ре­ва, а не са­мо­го про­се­ва) толь­ко об­щи­ми фра­за­ми го­во­ри­те, то­гда как о ме­то­де по­строе­ния про­се­вом вверх, ко­то­рый на­хо­ди­те бо­лее за­трат­ным, на­об­рот по­дроб­но (да­же ани­ма­цию для не­го сде­ла­ли). Мне, чест­но го­во­ря, так и оста­лось не­по­нят­но, по­че­му по­строе­ние про­сеи­ва­ни­ем вниз шло не по всем уз­лам, а толь­ко по i = n/2 — 1 до 0.
Все за­ме­ча­ния вер­ные. По­ста­ра­юсь учесть при об­нов­ле­нии ста­тьи.
Пи­ши­те вы от­лич­но толь­ко лю­дям изу­чаю­щим не си++ а про­сто си слож­но разо­б­рат­ся.
Ес­ли воз­мож­но в бу­дую­щем пи­ши­те хо­тя бы на ал­го­рит­ми­че­ском.Но за ста­тью все рав­но спа­си­бо
Боль­шое спа­си­бо за по­дроб­ное объ­яс­не­ние! Все по­нят­но. Во­про­сы толь­ко в оцен­ке слож­но­сти и быст­ро­дей­ствии ал­го­рит­ма. У ме­ня для чи­сел мень­ше 100 ра­бо­та­ет быст­ро, 0 мил­ли­се­кунд, ес­ли быть точ­ной. По­это­му я не мо­гу ни­как оце­нить и по­нять по­че­му же у вас по те­стам по­лу­чи­лось вот так…
Не со­всем по­нят­но по по­во­ду про­сеи­ва­ния вниз:
«1. ес­ли эле­мент ли­сто­вой, или его зна­че­ние >= зна­че­ний по­том­ков, то ко­нец;»
на­сколь­ко я по­нял, дан­ное усло­вие вы­пол­нит­ся для всех эле­мен­тов — то есть каж­дый эле­мент ли­бо ли­сто­вой, ли­бо >= сво­их по­том­ков, зна­чит даль­ше ал­го­ритм не пой­дет?
Про­сеи­ва­ние вниз за­пус­ка­ет­ся для «не­вер­но­го» эле­мен­та — та­ко­го, ко­то­рый на­ру­ша­ет по­ря­док ку­чи. Со­от­вет­ствен­но, для не­го этот ал­го­ритм вы­пол­ня­ет не­ко­то­рые дей­ствия.
В це­лом как ра­бо­та­ет по­нят­но, толь­ко все рав­но не­яс­но как все это де­ло пе­ре­ве­сти в код((
На сло­вах вро­де по­ни­маю как сде­лать, но что­бы по­стро­ить пи­ра­ми­ду на­до каж­дый раз срав­ни­вать зна­че­ние с ро­ди­тель­ским — а как узнать ка­кой эле­мент яв­ля­ет­ся ро­ди­тель­ским для но­во­го?
http://trubetskoy1.narod.ru/alg/pyramidsort.html
на­шел при­мер для C#, но не до­го­няю, что на­до пе­ре­да­вать в па­ра­мет­ре i для ме­то­да add2pyramid — са­мо зна­че­ние но­во­го эле­мен­та или но­мер это­го эле­мен­та? Что­бы по­стро­ить пи­ра­ми­ду, нуж­но до­бить­ся, что­бы все эле­мен­ты но­мер i бы­ли боль­ше эле­мен­тов но­мер 2i+1 и 2i+2 . На­при­мер, ну­ле­вой эле­мент дол­жен быть боль­ше пер­во­го и вто­ро­го.
А как в ко­де ука­зать что­бы опре­де­лен­ный эле­мент рас­по­зна­вал­ся как ли­сто­вой и для не­го дан­ная про­вер­ка не про­хо­ди­ла?
Жаль, что я рань­ше не на­шел эту ста­тью, на­до бы и со всем кур­сом озна­ко­мить­ся, по­жа­луй. На­столь­ко по­нят­но что и как с де­ре­вья­ми — мне еще не бы­ло
Боль­ше спа­си­бо! Дей­стви­тель­но, един­ствен­ное до­ступ­ное опи­са­ние в ин­тер­не­те!
1. ln n — на­ту­раль­ный ло­га­рифм? На­вер­ное log2 n?
2. Рас­суж­де­ния о ско­ро­сти, ко­гда пи­ше­те на лю­бом язы­ке вы­со­ко­го уров­ня, не­кор­рект­ны. От­сле­ди­те на уров­не ко­манд про­цес­со­ра, сколь мно­го лиш­не­го де­ла­ет­ся. Для ско­ро­сти — ас­сем­блер.
3. Су­ще­ству­ет ал­го­ритм, сор­ти­рую­щий ров­но за n * log2 n срав­не­ний. За­тра­ты па­мя­ти рав­ны двой­но­му раз­ме­ру мас­си­ва клю­чей.
Боль­шое спа­си­бо!!! Слож­ный ма­те­ри­ал объ­яс­нен очень про­стым и до­ступ­ным язы­ком.Бра­во!!!

При­мер ал­го­рит­ма на С, сор­ти­ров­ка по убы­ва­нию

до сор­ти­ров­ки : [4 3 5 2 6 1 7 0 9 8 6 5 4 3 2 3 4 5 6 7 6 5 4 3 2 1]
по­сле: [9 8 7 7 6 6 6 6 5 5 5 5 4 4 4 4 3 3 3 3 2 2 2 1 1 0]

struct MyType { // integer array
    int data[255];
    int count;
};

struct MyType ShiftUp(struct MyType data, int i, int n){
       // i ,i*2+1 , i*2+2
        int nMin = i;
        const int value = data.data[i];

        while ( 1==1 )
        {
            int childN = i*2+1;
            if ( ( childN < n ) && ( data.data[childN] < value  ) )
                {nMin = childN;}
            ++childN;
            if ( ( childN < n ) && ( data.data[childN] < data.data[nMin] ) )
                {nMin = childN;}
            if ( nMin == i ) break;
            data.data[i] = data.data[nMin]; data.data[nMin] = value;
            i = nMin;
        };
    return data;
}

struct MyType sortDOWNtree(struct MyType data){
           int i;
           int n;
           int firstElem;
           n = data.count;
           for( i = n/2-1; i>=0 ; i--) {
               data=ShiftUp(data, i , data.count);
           }

           while( n > 1 )
                   {
                       n--;
                       firstElem = data.data[0] ;
                       data.data[0] = data.data[n];
                       data.data[n] = firstElem;
                       data = ShiftUp(data,0, n);
                   }

    return data;
}

без ком­мен­та­ри­ев

Спа­си­бо!Все из­ло­же­но по­дроб­но и про­стым язы­ком!
не под­ска­жи­те как на­пи­сать вве­де­ние на эту те­му в кур­со­вой
Это луч­шая по­мощь при освое­нии пи­ра­ми­даль­ной сор­ти­ров­ки! Луч­ше вас ни­кто не объ­яс­ня­ет прин­цип. Спа­си­бо боль­шое, очень по­мог­ло!
Не со­всем по­нят­но как про­изо­шел пе­ре­ход от пунк­та 1 к 2 и от 3 к 4. На ос­но­ве ка­ко­го свой­ства или тео­ре­мы?
Hello!
Hello!
Hello!
Hello!
Hello!
Hello!
Hello!
Hello!
Hello!
Hello!
Hello!
Hello!
Hello!
Hello!
Hello!
Hello!
Hello!
Hello!
Hello!
Hello!
Hello!
Hello!
Hello!
Hello!
>alert() Hello
alert()«
<b alert() >
Hello!
Hello!
Hello!
Hello!
Generic of cialis levitra cialis com for full information on this drug-free solution.
reverse lookup cell phone free Your positions constantly have a decent amount of really
Greate post. Keep posting such kind of info on your
page. Im really impressed by your site.
Hey there, You’ve done an excellent job. I will definitely digg it and
individually recommend to my friends. I’m confident
they will be benefited from this web site.
Heya i’m for the primary time here. I came across this board and I to find It truly useful & it helped me out much.
I hope to offer one thing again and aid others
such as you aided me.
I every time used to read post in news papers but now as I
am a user of web therefore from now I am using net for content, thanks to web.
bookmarked!!, I like your site!
First off I want to say terrific blog! I had a quick
question in which I’d like to ask if you
do not mind. I was interested to find out how you center yourself and clear your mind before writing.
I have had a difficult time clearing my thoughts in getting my ideas out.
I do take pleasure in writing however it just seems like the first 10
to 15 minutes are usually lost just trying to figure out how to begin. Any ideas
or tips? Appreciate it!
This page really has all the information and facts I needed concerning this subject and didn’t know who to ask.
I just could not leave your website before suggesting that I extremely enjoyed the usual information an individual
provide in your visitors? Is going to be back ceaselessly to check up on new posts
Spot on with this write-up, I seriously believe that this web site needs a great deal more attention. I’ll probably
be back again to read more, thanks for the info!
Хо­ро­шо, тол­ко­во, по­нят­но опи­сан ал­го­ритм. Спа­си­бо.
I have read so many posts regarding the blogger lovers except this paragraph is in fact a pleasant post, keep it up.
It’s very trouble-free to find out any matter on net as compared to books, as I found this paragraph at this web site.
I visited several blogs except the audio quality for
audio songs present at this web site is actually wonderful.
Admiring the hard work you put into your website and in depth information you provide.
It’s nice to come across a blog every once in a while that isn’t the same out of
date rehashed material. Great read! I’ve bookmarked your site and I’m
adding your RSS feeds to my Google account.
Thanks for finally writing about > Лек­ция № 5:
Пи­ра­ми­даль­ная сор­ти­ров­ка | Image Processing < Liked it!
Hi there to every one, it’s actually a nice for me to visit this
web site, it includes precious Information.
Hi there to all, the contents existing at this web site are really
remarkable for people experience, well, keep up the nice work fellows.
Hello to every one, it’s in fact a nice for me to visit this web site, it includes priceless Information.
Heya i am for the first time here. I came across this board and
I find It really useful & it helped me out a lot. I hope to give something back and help others like you helped me.
Ahaa, its good discussion concerning this piece of writing at
this place at this webpage, I have read all that, so at this time me also commenting
at this place.
Great post.
Now I am ready to do my breakfast, later than having my breakfast coming yet
again to read more news.
I am really happy to read this website posts which consists of plenty of valuable
facts, thanks for providing these statistics.
I read this post completely regarding the resemblance of latest and previous technologies,
it’s remarkable article.
Excellent post. I used to be checking constantly
this blog and I am impressed! Extremely useful information specially the
last section I maintain such info a lot. I was looking for this particular info for a very long time.
Thanks and good luck.
Hi to all, how is everything, I think every one is
getting more from this website, and your views are
fastidious for new viewers. Look at my site :: mink lashes extensions near me (http://www.inca.lombardia.it/)
Hi to all, how is everything, I think every one is getting
more from this website, and your views are good for new viewers. Here is my website; csgo skins free 2016
Hi there, I enjoy reading through your article. I like to write a little comment
to support you. Stop by my weblog silk lashes for sale (ryanthomas645.co.uk)
Hi it’s me, I am also visiting this site daily, this website
is truly nice and the viewers are actually sharing fastidious
thoughts. Here is my homepage :: madden mobile free coins no survey no download
What’s Taking place i’m new to this, I stumbled upon this I have found It positively useful and it has aided me out loads. I hope to give a contribution & aid different customers like its helped me.
Good job. Feel free to surf to my web site; finally game [http://www.ascandi.ch]
I was curious if you ever considered changing
the page layout of your site? Its very well written; I love what youve
got to say. But maybe you could a little more in the way of content so
people could connect with it better. Youve got an awful lot of text for only having one or two images.
Maybe you could space it out better?
We stumbled over here coming from a different web page and thought I may as well check things out.
I like what I see so now i am following you. Look forward to exploring your web page for a second
time.
Very nice article, just what I was looking for. Feel free to visit my web page — cs go weapon skins steam
Fine way of describing, and fastidious piece of writing
to get data on the topic of my presentation topic, which i am going to present in college. Here is my blog :: fifa coins cheap fifa 17
I have read so many articles about the blogger lovers except this piece of writing
is truly a pleasant article, keep it up. Check out my blog — mink eyelash extensions cruelty
Hey there, You’ve done a great job. I’ll definitely digg it
and personally recommend to my friends. I’m sure they’ll be benefited from this website. Visit my web site cs go skin trade hack
I like what you guys are usually up too. This type of clever work
and reporting! Keep up the very good works guys I’ve
incorporated you guys to blogroll. Feel free to visit my page; sell cs go skins for cash
Generally I do not learn post on blogs, however I would like to say that this write-up very compelled me to take a look at
and do it! Your writing taste has been amazed me. Thank you, very nice post. Here is my blog :: fifa 17 coins cheap comfort trade
Hello i am kavin, its my first time to commenting anywhere, when i read this piece of writing i thought i could
also make comment due to this good piece of writing. Here is my blog post — groupon mink lashes nyc
Your style is very unique compared to other folks I have read stuff from.
I appreciate you for posting when you have the opportunity,
Guess I’ll just book mark this page.
What’s up Dear, are you truly visiting this site daily, if
so after that you will without doubt get good know-how.
Excellent goods from you, man. I’ve understand your stuff previous to and you are just too
wonderful. I really like what you’ve acquired here, certainly like what you’re stating and the way in which you say it.
You make it entertaining and you still take care of to keep it wise. I can’t wait to read much more from you. This is actually a wonderful
web site.
Howdy just wanted to give you a quick heads up.
The text in your post seem to be running off the screen in Ie.
I’m not sure if this is a format issue or something to do
with web browser compatibility but I thought I’d post to let you know.
The style and design look great though! Hope you get the
problem solved soon. Cheers My homepage; sell cs go skins for cash
Howdy! Would you mind if I share your blog with my facebook group?
There’s a lot of people that I think would really appreciate your content.
Please let me know. Thanks Also visit my web-site — mink lashes extensions near me
Thank you for the auspicious writeup. It actually was a enjoyment account it.
Glance complicated to far delivered agreeable from you! However, how could we keep up a correspondence?
I was curious if you ever considered changing the layout of your blog?
Its very well written; I love what youve got to say.
But maybe you could a little more in the way of content
so people could connect with it better. Youve got an awful lot of text for only
having 1 or 2 images. Maybe you could space it out better?
Greate post. Keep writing such kind of information on your site.
Im really impressed by it.
Hello there, You’ve performed an excellent job.
I will definitely digg it and in my view
suggest to my friends. I am sure they will be benefited from this website.
Valuable info. Fortunate me I found your site unintentionally,
and I’m stunned why this coincidence didn’t happened earlier!
I bookmarked it.
Everything is very open with a clear clarification of the issues.
It was definitely informative. Your website is very useful.
Many thanks for sharing!
I visited several blogs but the audio feature for audio songs present at
this website is actually marvelous.
Howdy! I know this is kinda off topic however I’d figured I’d ask.
Would you be interested in trading links or maybe guest writing a blog
post or vice-versa? My site goes over a lot of the same topics as yours and I feel we
could greatly benefit from each other. If you are interested feel
free to shoot me an e-mail. I look forward to hearing from you!
Fantastic blog by the way!
Oh my goodness! Amazing article dude! Thank you, However I am experiencing difficulties with your RSS.
I don’t understand the reason why I cannot
join it. Is there anyone else having identical RSS problems?
Anyone that knows the answer will you kindly respond? Thanx!!
It’s an remarkable article for all the online viewers; they will take advantage from it I am sure. my homepage :: exiciting games available, sodermansel.se,
Saved as a favorite, I really like your web site! Here is my blog post — mink strip eyelashes australia [Shad]
Hey There. I found your weblog the usage of msn. This
is a very well written article. I’ll make sure to bookmark it and come back to read more of your helpful information. Thanks for the post.
I will certainly comeback. Also visit my weblog :: csgo skins steam wallet
Right here is the right web site for anyone who would like to understand this topic.
You realize a whole lot its almost tough to argue with you (not that I actually would want to…HaHa).
You certainly put a brand new spin on a topic that has been written about for a long time.
Excellent stuff, just wonderful! my webpage — mink eyelash extensions cruelty free (http://itechnologydesign.com/UserProfile/tabid/42/userId/210434/Default.aspx)
I’d like to find out more? I’d love to find out more details. My website — fifa coins buy cheap
Useful information. Lucky me I found your site by accident,
and I am surprised why this accident did not happened in advance! I bookmarked it. Take a look at my web-site csgo skins for sale paypal (Kathleen)
What i do not realize is in fact how you’re now not really a
lot more well-favored than you may be now. You are so intelligent. You realize therefore significantly when it comes
to this subject, made me personally consider it from numerous various angles. Its like men and women aren’t fascinated until it’s something to do with Woman gaga!
Your individual stuffs outstanding. Always handle it up! Check out my webpage; cs go skin betting websites (Bertha)
Hi to all, how is all, I think every one is getting more from
this web site, and your views are good in support of new people. Check out my blog :: mink strip lashes ebay (Jeanette)
May I just say what a comfort to uncover somebody that truly understands what they are discussing on the net.
You actually understand how to bring an issue to light and make it important.
More and more people should check this out and understand this side of the
story. I can’t believe you are not more popular since you most certainly possess the
gift. Look at my web page: madden nfl mobile cheats free coins and cash [Brigida]
Fantastic beat ! I would like to apprentice while you amend your web site, how could i subscribe for a
blog site? The account aided me a acceptable deal. I had been tiny
bit acquainted of this your broadcast offered bright clear idea Review my site; mink lash extensions kit, http://kkglass.co.kr/,
Hi, all is going perfectly here and ofcourse every one is sharing information, that’s truly excellent,
keep up writing. Here is my webpage cs go skins for sale ebay (Jorg)
Amazing issues here. I am very satisfied to see your article.
Thanks so much and I am taking a look forward to contact you.
Will you kindly drop me a e-mail? Here is my website … nba live coins generator
Its like you learn my thoughts! You appear to know so much approximately this,
like you wrote the book in it or something. I feel that
you can do with a few % to drive the message house a little bit, however instead of that, this is great blog.
An excellent read. I will definitely be back. Also visit my web blog :: nba live coins generator
Whats up very nice website!! Guy .. Excellent .. Wonderful ..
I’ll bookmark your site and take the feeds also? I am satisfied to
search out so many helpful information right
here within the put up, we want develop extra strategies in this regard, thank you for sharing.
. . . . . Feel free to visit my webpage — nba live coins ios; Annis,
Normally I do not learn post on blogs, however I would like to say that this write-up very compelled me to check out
and do it! Your writing style has been surprised me.
Thank you, quite great post. my blog post: mink lashes kit wholesale (petsmarket.us)
An interesting discussion is definitely worth comment.
I think that you need to write more about this subject matter,
it might not be a taboo matter but generally people do not speak
about such topics. To the next! Many thanks!! Visit my homepage: fifa coins zone facebook
Very quickly this web site will be famous among all blogging and site-building viewers, due to it’s pleasant articles
Thanks for finally talking about > Лек­ция № 5: Пи­ра­ми­даль­ная сор­ти­ров­ка |
Image Processing < Loved it! Also visit my web page; cs go skin trade hack (Roscoe)
Very soon this website will be famous amid all blogging viewers,
due to it’s pleasant articles Also visit my website — fifa coins zone ps4 — Virgilio -
Spot on with this write-up, I actually think this site needs a great
deal more attention. I’ll probably be back again to see more, thanks for the information! My blog … trusted madden mobile coin sellers (Steffen)
Hello! I’ve been reading your site for some time now and finally got the courage to go ahead
and give you a shout out from New Caney Texas! Just wanted to mention keep
up the great work! my webpage … silk lash extensions perth, Royce,
Hmm is anyone else experiencing problems with the pictures on this blog loading?
I’m trying to find out if its a problem on my end or if it’s the blog.
Any feedback would be greatly appreciated. Have a look at my site cheap pubg skins (summerhouse.uk.net)
Pretty! This was an extremely wonderful post. Thanks
for supplying these details. Feel free to surf to my site … cheap hut 17 coins (Lucile)
You could definitely see your enthusiasm in the work you write.
The world hopes for more passionate writers like you who aren’t afraid to mention how they believe.
At all times follow your heart. Review my page; csgo skins sites (Katherin)
You are so cool! I do not believe I’ve truly read
through a single thing like that before. So great to discover somebody with unique thoughts on this subject matter.
Seriously.. thank you for starting this up. This website is
one thing that’s needed on the internet, someone with a bit of originality! Also visit my web blog; buy cheap nba live coins (ecowon.bcpark.net)
Hi! Do you know if they make any plugins to safeguard against
hackers? I’m kinda paranoid about losing everything I’ve worked hard on. Any recommendations? Feel free to visit my web-site: buy nhl 17 coins
I will immediately take hold of your rss as I can not find
your e-mail subscription hyperlink or e-newsletter service.
Do you have any? Please permit me know so that I could
subscribe. Thanks. Also visit my web page; cheap csgo skins (soldierswap.com)
Howdy! This is my 1st comment here so I just wanted to give a quick shout out and
tell you I really enjoy reading your articles. Can you recommend any
other blogs/websites/forums that go over the same topics?
Thank you so much! Also visit my webpage … nba live coins cheap (1papacaio.com.br)
I’m really enjoying the theme/design of your website. Do you ever run into any internet
browser compatibility problems? A couple of my blog audience have complained about my site not working correctly
in Explorer but looks great in Safari. Do you have any ideas to
help fix this problem?
Hi to every one, since I am actually keen of reading this website’s post to be updated on a
regular basis. It carries pleasant information.
I pay a visit each day some web pages and sites to read articles, except this weblog offers feature
based writing.
Because the admin of this web page is working, no doubt very soon it will be well-known, due
to its quality contents. Take a look at my web page; nba mobile coins
These are truly wonderful ideas in concerning blogging.
You have touched some nice factors here. Any way keep
up wrinting. Here is my website … buy madden mobile coins
(http://www.topclassifiedsusa.com)
It is appropriate time to make a few plans for the long run and
it is time to be happy. I’ve read this publish and if I may just I wish to counsel
you few interesting issues or suggestions.
Maybe you could write next articles referring to this
article. I want to learn even more issues approximately it! Here is my page buy csgo skins
Simply desire to say your article is as surprising.
The clarity in your post is just excellent and i can assume you are an expert on this subject. Fine with your permission let me to grab your feed
to keep updated with forthcoming post. Thanks a million and
please keep up the enjoyable work. Here is my homepage: cheap mink eyelashes
What i do not realize is in truth how you are not
really much more well-liked than you may be right now.
You’re so intelligent. You realize therefore significantly in terms of this subject, produced me personally imagine it from a lot of varied angles.
Its like women and men are not involved until it is
one thing to do with Lady gaga! Your individual stuffs excellent.
Always deal with it up! my web site :: hut coins (https://www.smartmylife.fr/)
Hmm it looks like your website ate my first comment (it was
extremely long) so I guess I’ll just sum it up what I had written and say, I’m thoroughly enjoying your blog.
I as well am an aspiring blog blogger but I’m still new to everything.
Do you have any tips for rookie blog writers? I’d really appreciate it. My site nba mobile coins
all the time i used to read smaller articles or reviews that also clear
their motive, and that is also happening with this piece of writing which I am
reading at this place. My webpage; h1z1 kotk skins — Vickey -
Wow that was unusual. I just wrote an incredibly long
comment but after I clicked submit my comment didn’t show up.
Grrrr… well I’m not writing all that over again. Regardless, just wanted to say excellent blog! Also visit my web blog: pubg skins
Hi there! I realize this is kind of off-topic however I needed to
ask. Does running a well-established website like yours require a
lot of work? I’m brand new to writing a blog but I do write
in my diary daily. I’d like to start a blog so I can share my own experience and views online.
Please let me know if you have any recommendations or tips for new aspiring blog owners.
Thankyou! Here is my web site :: h1z1 items
My coder is trying to persuade me to move to .net from PHP.
I have always disliked the idea because of the costs.
But he’s tryiong none the less. I’ve been using Movable-type on a number of websites for
about a year and am worried about switching to another platform. I have heard good things about blogengine.net. Is there a
way I can transfer all my wordpress content into it? Any
kind of help would be really appreciated! Here is my blog post … buy fifa 18 coins
Thanks for finally writing about > Лек­ция № 5: Пи­ра­ми­даль­ная сор­ти­ров­ка |
Image Processing < Loved it! My page :: cheap fut 18 coins (http://mis.yongin.ac.kr/)
Hi! This is my first comment here so I just wanted
to give a quick shout out and tell you I really enjoy reading through
your articles. Can you recommend any other blogs/websites/forums that cover the same subjects?
Thank you! Also visit my web page :: cheap nba live coins
Great beat ! I would like to apprentice even as you amend your website, how could
i subscribe for a blog site? The account aided me a applicable deal.
I have been tiny bit familiar of this your broadcast provided vivid clear concept my web page — nba mobile coins
I am regular reader, how are you everybody? This
paragraph posted at this site is in fact pleasant. Here is my web page :: madden 17 coins
Whats up very cool website!! Guy .. Excellent .. Superb
.. I’ll bookmark your website and take the feeds also? I’m satisfied
to find numerous helpful information right here in the publish,
we need develop extra strategies in this regard, thank you for sharing.
. . . . . Feel free to visit my web blog; buy eyelashes, http://www.tagliate.it,
Hi there! I’m at work surfing around your blog from my new apple
iphone! Just wanted to say I love reading through your blog
and look forward to all your posts! Carry on the fantastic work! Look at my blog … fut 18 coins
Ridiculous story there. What occurred after?
Thanks! Here is my web page; cheap nba live coins (Nydia)
Hi everyone, it’s my first go to see at this web page, and article
is genuinely fruitful in support of me, keep up posting these posts. Here is my blog post; csgo skins free 2016 — filanthrope.org,
Amazing blog! Is your theme custom made or did you download it from
somewhere? A design like yours with a few simple adjustements would really make my blog jump out.
Please let me know where you got your theme. Thank you
Hi there Dear, are you really visiting this website regularly,
if so after that you will definitely get good
experience.
Hello great blog! Does running a blog similar to this require a lot
of work? I have virtually no knowledge of programming however I
had been hoping to start my own blog soon. Anyway, should you have any ideas or tips for new blog owners please share.
I know this is off subject nevertheless I just needed to ask. Thanks a lot!
I used to be recommended this blog by my cousin. I’m no longer
positive whether this post is written via him as no one else
know such detailed about my difficulty. You’re incredible!
Thank you!
Wow that was unusual. I just wrote an very long comment but after I clicked submit my comment didn’t show up.
Grrrr… well I’m not writing all that over again. Anyhow, just wanted to say great blog!
My family members always say that I am killing my time
here at web, but I know I am getting familiarity all the time by reading such fastidious content.
I absolutely love your blog.. Excellent colors & theme.
Did you build this website yourself? Please reply back as I’m trying
to create my own blog and would love to learn where you got this from or exactly what the theme is called. Kudos!
Howdy exceptional website! Does running a blog such as this
require a massive amount work? I have very little understanding of coding but I had been hoping to start my own blog soon. Anyway, should you have
any ideas or tips for new blog owners please share.
I know this is off topic nevertheless I simply wanted to ask.
Thanks a lot!
Do you have a spam issue on this blog; I also am a blogger,
and I was wondering your situation; we have developed some nice methods
and we are looking to trade techniques with other folks,
be sure to shoot me an email if interested.
I have been exploring for a little for any high quality
articles or weblog posts in this sort of space .
Exploring in Yahoo I finally stumbled upon this web site.
Reading this info So i’m happy to show that I’ve a very just right uncanny feeling I found
out just what I needed. I most no doubt will make sure to do not forget
this website and provides it a glance regularly.
This paragraph is really a nice one it assists new the web users, who are wishing for blogging.
We are a group of volunteers and opening a new scheme in our
community. Your site offered us with valuable info to work
on. You have done a formidable job and our whole community will be grateful to you.
online personal loans bad credit
payday loans online
cash till payday
where to buy generic levitra
levitra price
buy brand name levitra
My brother recommended I might like this blog. He was totally right.
This post truly made my day. You cann’t imagine just how much time
I had spent for this information! Thanks!
viagra buy uk
generic viagra 100 mg
order viagra south africa
Awesome website you have here but I was wanting to know if you knew
of any discussion boards that cover the same topics discussed in this
article? I’d really love to be a part of community where I can get suggestions from other
experienced people that share the same interest.
If you have any suggestions, please let me know. Appreciate it!
Having read this I thought it was very informative. I
appreciate you finding the time and energy to put this information together.
I once again find myself spending a significant amount of time both reading and commenting.
But so what, it was still worth it!
I do not even know how I finished up right here, but I believed this publish used to be good.
I don’t recognise who you might be however certainly you are going to a famous
blogger when you are not already. Cheers!
Hi there to every , because I am really eager of reading this blog’s post
to be updated on a regular basis. It contains pleasant stuff.
I blog often and I seriously thank you for your information. This article has
truly peaked my interest. I will book mark your blog and keep checking for new details about once
per week. I subscribed to your Feed too.
Definitely believe that which you said. Your favorite justification seemed to be on the net
the easiest thing to be aware of. I say to
you, I definitely get irked while people consider worries that they just don’t know about. You managed to hit the nail upon the top and also
defined out the whole thing without having side-effects , people could take a signal. Will probably be back to get more. Thanks
Your style is really unique in comparison to other folks I’ve read stuff from.
Thanks for posting when you’ve got the opportunity, Guess I will just bookmark this site.
I am in fact thankful to the owner of this web site who has shared this enormous paragraph at at this place.
My brother recommended I would possibly like this blog.
He used to be totally right. This publish actually made my day.
You can not consider simply how a lot time I had spent for this info!
Thanks!
discount prices on cialis
cialis 10 mg
generic cialis mail order
I think the admin of this website is really working hard for
his website, since here every stuff is quality based material.
Great blog right here! Additionally your web site a lot up fast! What web host are you the usage of? Can I am getting
your associate link on your host? I desire my web
site loaded up as quickly as yours lol
Tremendous things here. I am very satisfied to look your article.
Thank you a lot and I’m looking ahead to touch you. Will you please drop me a mail?
Yes! Finally someone writes about instacart coupon august 2017.
I used to be able to find good info from your articles.
Hello! Do you use Twitter? I’d like to follow you if that would be ok.
I’m undoubtedly enjoying your blog and look forward to new updates.
cheap cialis in canada
cialis
order cialis phone
bookmarked!!, I like your site!
I don’t know if it’s just me or if perhaps everyone else
experiencing problems with your website. It seems like some of the text in your content are running off the screen. Can someone else please comment and let me know if this is happening to them too?
This might be a problem with my web browser because I’ve had this happen previously.
Kudos
top online live casino
online casino real money
100 best online casinos
Do you mind if I quote a few of your articles as long as I provide credit and sources back to your blog?
My website is in the exact same niche as yours and my visitors would genuinely benefit from
a lot of the information you provide here. Please let me know if this
okay with you. Many thanks!
Great delivery. Outstanding arguments. Keep up the amazing spirit.
Wow, marvelous blog structure! How long have you been running a blog for? you make blogging glance easy. The total look
of your web site is magnificent, let alone
the content material!
liquid viagra buy uk
viagra 100mg
buy viagra london
best place buy levitra online
buy levitra
cheap levitra in uk
cheap viagra no rx
viagra without a doctor prescription
order a viagra online
what is the interest rate on a personal loan
pay day loans
personal loan offers
order viagra from boots
generic viagra
viagra sale derby
popular pills online compra cialis italy
cialis 10 mg
cialis cheap prescription
donde puedo comprar viagra argentina
generic viagra online
is 200 mg of viagra safe
list of approved canadian pharmacies
canadian online pharmacy
International Pharmacies that Ship to the USA
order viagra cialis
cheapest generic cialis uk
cheap cialis from canada
buy cialis in vancouver
cheap cialis prices
cialis buy uk
buy cialis online in uk
cialis buy london
buy cialis united states
buy cialis in the usa
can you buy cialis over the counter
buy cialis walmart
online pharmacy cialis
cialis buy uk online
cheap cialis prices
cialis online pharmacy
wholesale cost of cialis
http://realrich7casinogames.org/ — play roulette
bonus Pokies
Casino slots
http://getloansusapersonal.com/ — direct payday loans
no fee payday loans
direct payday lenders for bad credit
payday loans hattiesburg ms
personal loan rates
bad credit payday advance
2000 loan
online loans no paperwork
payday loans no checks
need cash today
personal loans for fair credit
cash loans today
personal loans colorado springs
loans poor credit
loans colorado springs
Good day! Would you mind if I share your blog with my
twitter group? There’s a lot of folks that I think would really
appreciate your content. Please let me know.
Thanks
https://easycarup.com/ — auto insurance in india
lowest auto insurance
best auto insurance georgia
I used to be suggested this blog through my cousin. I’m not certain whether this submit is written by means
of him as nobody else recognise such distinct approximately my problem. You’re incredible! Thanks!
Hey there just wanted to give you a quick heads up. The text in your article seem to
be running off the screen in Ie. I’m not sure if this is a formatting issue or something to do
with internet browser compatibility but I thought I’d post to let you
know. The design and style look great though!
Hope you get the problem solved soon. Many thanks
If you are going for most excellent contents like I do, only go to see
this website every day for the reason that it gives quality contents, thanks
Greetings! Very useful advice in this particular article! It is the little changes that make the greatest changes.
Many thanks for sharing!
same day unsecured loans
cashloans
fast online payday
Hello there, just became alert to your blog through Google,
and found that it’s really informative. I am going to watch out for
brussels. I’ll appreciate if you continue this in future. A lot of people will be benefited from your writing. Cheers!
Hi there very cool blog!! Man .. Beautiful .. Wonderful ..
I will bookmark your blog and take the feeds also?
I am satisfied to find numerous helpful info right here
in the put up, we want work out extra strategies on this regard, thanks
for sharing. . . . . .
Excellent beat ! I wish to apprentice at the same time
as you amend your website, how could i subscribe for a blog website? The account helped me a appropriate deal. I have been a
little bit acquainted of this your broadcast provided bright transparent idea
What’s up, I log on to your blogs daily. Your writing style
is witty, keep up the good work!
Actually when someone doesn’t understand afterward its up to other people that they will help,
so here it happens.
single mother loans
apply for a loan
payday loans in columbus ohio
I every time spent my half an hour to read this weblog’s posts all
the time along with a mug of coffee.
Hello there! I know this is kinda off topic however ,
I’d figured I’d ask. Would you be interested in exchanging links or maybe guest authoring a blog post
or vice-versa? My website addresses a lot of the same subjects as
yours and I believe we could greatly benefit from each other.
If you are interested feel free to shoot me
an e-mail. I look forward to hearing from you! Great blog by
the way!
Attractive section of content. I just stumbled upon your weblog and in accession capital to assert that I get actually enjoyed account your blog posts.
Any way I’ll be subscribing to your feeds and even I achievement you
access consistently quickly.
Hi, I think your blog might be having browser compatibility issues.
When I look at your blog in Firefox, it looks fine but when opening
in Internet Explorer, it has some overlapping. I just wanted to
give you a quick heads up! Other then that, excellent blog!
I visited several web sites except the audio quality for audio songs current
at this website is genuinely wonderful.
private personal loan
payday advance loans
loans in las vegas
It’s amazing for me to have a web page, which is
useful in support of my knowledge. thanks admin
loans for bad credit no fees no guarantor no brokers
trimark funds
online payday loans in va
Thank you, I’ve just been searching for info about this topic for
a long time and yours is the greatest I’ve came upon so far.
But, what in regards to the conclusion? Are you positive
about the supply?
buy online viagra viagra
buy viagra forum
cheap viagra brand
http://littlebearonline.com/?option=com_k2&view=itemlist&task=user&id=35210 — auto insurance questions
auto insurance under 18
auto insurance quiz
safe online payday loans
cash loans for bad credit
personal unsecured loan
banks that give personal loans
online cash advance loans
small dollar loans
online cash advance payday loans
no checking account payday loans
bad credit loans with monthly payments
cash advance apr
loan companies for people with bad credit
online cash advance direct lender
Piece of writing writing is also a fun, if you
be acquainted with after that you can write if
not it is complex to write.
There is definately a lot to know about this subject.
I really like all the points you made.
These are really great ideas in concerning blogging.
You have touched some fastidious things here.
Any way keep up wrinting.
Wonderful post however , I was wondering if you could write a litte more on this topic?
I’d be very thankful if you could elaborate a little bit
further. Thank you!
Right here is the right web site for anyone who really wants to understand this topic.
You understand a whole lot its almost tough to argue with you (not that I actually would want to…HaHa).
You certainly put a fresh spin on a topic which has been discussed for decades.
Great stuff, just excellent!
car insurance quotes
auto insurance quotes
auto insurance quotes
cheap car insurance
Keep on working, great job!
Your way of telling everything in this paragraph is actually pleasant,
all be capable of easily understand it, Thanks a lot.
Thanks for a marvelous posting! I truly enjoyed reading it, you could be a great author.
I will make certain to bookmark your blog and will eventually come back sometime soon. I want to encourage one to continue
your great posts, have a nice weekend!
quick loans for bad credit
quick loans
free loan
bad credit personal loans not payday loans
cash loan
personal loan companies
Amazing! Its really amazing article, I have got much
clear idea about from this paragraph.
buy zithromax 500mg online
buy zithromax 500mg online
buy zithromax online
zithromax z-pak buy online
Hello I am so grateful I found your website, I really found
you by error, while I was searching on Yahoo for something else, Anyways I am here now and would just like to say thank you for a marvelous post and a all round interesting
blog (I also love the theme/design), I don’t have time to
go through it all at the minute but I have book-marked it and also included your RSS feeds,
so when I have time I will be back to read a great deal more, Please do
keep up the great b.
cash advance bad credit
peachy payday loans
loans on line
viagra buy in singapore
viagra for sale uk
order genuine viagra online
bad credit signature loan
fast cash loans
loans for single moms
zithromax z-pak
zithromax z pak cost
buying zithromax online
zithromax z-pak buy online
I loved as much as you’ll receive carried out
right here. The sketch is attractive, your authored subject matter stylish.
nonetheless, you command get got an shakiness 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 hike.
Hello! Do you use Twitter? I’d like to follow you if that would be ok.
I’m definitely enjoying your blog and look forward to new posts.
Howdy! Do you use Twitter? I’d like to follow you if that would
be ok. I’m definitely enjoying your blog and look forward
to new posts.
It’s really very complicated in this active life to listen news on Television, therefore I just use internet for that purpose, and
get the most up-to-date information.
I’ll immediately take hold of your rss as I can’t in finding your email subscription link or newsletter service.
Do you’ve any? Kindly allow me know in order that I may just subscribe.
Thanks.
payday loans in laredo tx
same day loans
what is unsecured loan
max loan
cash loans
quick payday loan online
Hi there! I know this is somewhat off-topic however I had to ask.
Does building a well-established website like yours require a lot of work?
I am completely new to operating a blog however I do write
in my diary every day. I’d like to start a blog so I can easily share my experience and feelings online.
Please let me know if you have any kind of
ideas or tips for new aspiring blog owners. Thankyou!
Hello there, You’ve done an incredible job.
I’ll certainly digg it and personally suggest to my friends.
I’m confident they’ll be benefited from this website.
auto insurance rates increase
is auto insurance required in oregon
why auto insurance can be terminated
auto insurance fraud
Hi friends, how is the whole thing, and what you
desire to say about this piece of writing, in my view its truly amazing in support of me.
If some one wants to be updated with most up-to-date technologies afterward
he must be pay a visit this web page and be up to date everyday.
auto insurance owatonna
will auto insurance replace mailbox
auto insurance trivia
auto insurance ri
It’s a pity you don’t have a donate button! I’d definitely
donate to this outstanding blog! I guess for now i’ll settle for
bookmarking and adding your RSS feed to my Google account.
I look forward to new updates and will share this website with my Facebook group. Talk soon!
high risk auto insurance
auto insurance subrogation
auto insurance victoria tx
auto insurance direct
top auto insurance companies in pa
auto insurance exam
auto insurance agents
auto insurance rates
Hello to every one, the contents existing at this website are truly
amazing for people experience, well, keep up the
good work fellows.
Excellent pieces. Keep posting such kind of information on your blog.
Im really impressed by your blog.
Hey there, You have performed a great job.
I will certainly digg it and for my part recommend to my friends. I am confident they’ll be benefited from this website.
buy cialis online from uk
cialis coupon
cialis discount online
It’s impressive that you are getting thoughts from this post as
well as from our argument made at this time.
buy cialis online no prescription usa
buy cialis
order generic viagra cialis
Very great post. I simply stumbled upon your
blog and wanted to mention that I’ve truly enjoyed browsing your blog posts.
After all I’ll be subscribing on your feed and I hope you write once more very soon!
viagra sale vegas
buy viagra
buy cheap viagra in the uk
cheapest levitra canada
buy levitra
levitra online sales
online payday loans
bad credit payday loans
paydayloans
online payday loans no credit check
cialis china buy
cialis cost
can you buy cialis over the counter in usa
best online casinos
online slots casino
game slot
slots vegas
slots vegas
buy cialis eli lilly
buy cialis
buy cialis online legal
Excellent beat ! I wish to apprentice at the same time as you amend your web site, how can i subscribe for a blog web site?
The account aided me a appropriate deal.
I were a little bit familiar of this your broadcast
provided shiny clear idea
mail order cialis generic
cialis cost
cheap viagra or cialis
I’m not sure why but this blog is loading extremely slow for me.
Is anyone else having this problem or is it a issue on my end?
I’ll check back later on and see if the problem still exists.
propecia cheap online
buy propecia nz
buy propecia australia
buy celebrex online uk
celebrex buy online
cerebrex pills
where to buy celebrex online
celebrex tablets arthritis
This paragraph offers clear idea in favor of the new visitors of blogging, that really how to do blogging and
site-building.
I every time emailed this webpage post page to all my associates, since if like to
read it after that my contacts will too.
Thanks for another informative website. Where else may just I get that type of information written in such a perfect way? I have a undertaking that I am simply now operating
on, and I’ve been at the glance out for such information.
You actually make it appear so easy together with your presentation but I in finding this matter to be actually
one thing which I think I would by no means understand.
It kind of feels too complicated and extremely huge for
me. I am having a look ahead for your subsequent put up,
I’ll attempt to get the hang of it!
I like the helpful information you provide to your articles. I will bookmark your weblog and take a look at again right
here regularly. I am quite certain I will be informed lots of new stuff proper here! Good luck for the next!
It’s fantastic that you are getting thoughts from this
article as well as from our argument made at this place.
I need to to thank you for this very good read!!
I definitely loved every little bit of it. I have
you saved as a favorite to check out new things you post…
My brother suggested I might like this website. He was once entirely right.
This put up truly made my day. You can not believe simply how so much time
I had spent for this info! Thanks!
This design is incredible! You most 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!) Excellent job.
I really enjoyed what you had to say, and more than that,
how you presented it. Too cool!
cialis buy australia
cialis online
cialis cheap prescription
buy cialis generic online
buy viagra
ok split cialis pills
online casino usa
slot machines
online casino canada
casino online
mobile casino
online roulette
online casino canada
casinos online
Regardless of all the possibilities, an escorts arrangement makes up
for a perfect choice of present for folks owned
by all types of clients. My professional Delhi Escorts Service are experienced and
specialized who love what they do. Each escorts girl is a talented with
an exclusive style that is the great companion to any event. Here you can see in my gallery page! You can find real & hot pics as I captured with my phone inside my rooms, I have up to date my gallery page
once in a week.
online slots casino
slot sites
online casinos
slots games
slots lv
payday loan no credit check
apply for payday loans
online payday loan
apply for payday loans
how to cut cialis pills
generic cialis 2017
buy cialis mastercard
viagra sale point pakistan
generic viagra online
viagra buy online no prescription
gambling Pokies
online casino luxury
online casino 18 years old
livecasino
levitra discount coupon
vardenafil 20mg
can you buy levitra from canada
autocad r14 64 bit download
autodesk student autocad
install autocad software
2012 autocad serial number
autocad 2014
product key autocad 2011 32 bit
buy cialis no prescription in uk
cialis without a doctor’s prescription
cialis buy online pharmacy
order viagra without rx
viagra online
where can i buy viagra in london
cheapest place to buy cialis online
cialis without a doctor prescription
pharmacy has cheapest cialis
cutting cialis pills in half
viagra without a doctor prescription
cialis pills amazon
online bingo and slots
no deposit bonus with no max cashout
fruit machine jackpot key
casino knokke
slot sites canada
car finance no deposit 0 interest
online casino games for real money in india
online gambling slots real money
online roulette real money no deposit
online roulette guide

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

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

   

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