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

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

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

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

   

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