Лек­ция № 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 бай­та), ско­рость сор­ти­ров­ки па­да­ет. Это вы­зва­но тем, что ал­го­ритм об­ра­ща­ет­ся к эле­мен­там мас­си­ва до­воль­но слу­чай­ным об­ра­зом (с точ­ки зре­ния ал­го­рит­ма ра­бо­ты кэ­ша). По ме­ре то­го, как всё мень­шая часть дан­ных умень­ша­ет­ся в кэ­ше, ско­рость ра­бо­ты ал­го­рит­ма всё бо­лее опре­де­ля­ет­ся ско­ро­стью ра­бо­ты опе­ра­тив­ной па­мя­ти, а не ско­ро­стью ра­бо­ты кэ­ша. В од­ной из сле­дую­щих лек­ций мы устра­ним этот не­до­ста­ток.

204 отзыва на запись «Лек­ция № 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.

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

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

   

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