Quicksort z prednasky - zacyklenie?

Moderátor: FeroG

<<

Aries

Príspevky: 379

Registrovaný: Pia Jan 30, 2009 1:26 pm

Bydlisko: 127.0.0.1

Poslať Str Feb 24, 2010 10:54 am

Quicksort z prednasky - zacyklenie?

Pozrel som sa na kod quicksortu z prednasky a zda sa mi, ze funguje len pre polia s roznymi prvkami. Akonahle sa za pivot vezme prvok, ktory je v poli viackrat, vznikne nekonecny cyklus v metode partition (dva rovnake prvky sa budu dookola vymienat a ukazovatel na lavy a pravy prvok sa nezmeni). Dobre som sa na to pozeral? :) Alebo som sa niekde pomylil? Nevylucujem to, este trochu spim a zaroven predychavam nas hokejovy vykon proti Norom... Kazdopadne, kod som prepisal do Eclipse a skutocne sa zacyklil, tak snad este prepisovat viem :)

Riesenim by mohlo byt po swape znizit ukazovatel na pravy prvok o jedna. Dufam, ze som pri oprave chyby nespravil dalsiu, ako to byva zvykom :)

//EDIT, nezacykli sa vzdy ked su tam dva+ rovnake prvky, iba ked je tam viac takych prvkov ako je pivot.
Vasnivy pestovatel binarnych stromov a opravar Turingovych strojov na polovicny uvazok.
"Problem citatov najdenych na internete je taky, ze si nikdy nemozete byt isti ich autenticitou" Abraham Lincoln
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Str Feb 24, 2010 9:28 pm

Zdanie je dobre. V skutocnosti ten kod predpoklada, ze vsetky cisla v poli su rozne (i ked je pravda, ze v slidoch o tom nie je zmienka a to, ci o tom bola zmienka na prednaske neviem, kedze som prednasku nesledoval velmi pozorne).

Tebou navrhnuta uprava je OK. Ale, co bude vracat metoda partition v tomto pripade ? Bude fungovat algoritmus aj v pripade, ze sa ako pivot nebude volit prvy prvok v podpoli ?
<<

Aries

Príspevky: 379

Registrovaný: Pia Jan 30, 2009 1:26 pm

Bydlisko: 127.0.0.1

Poslať Str Feb 24, 2010 10:22 pm

Predpokladal som ze ako pivot sa bude brat vzdy prvy prvok. Inak partition vracia index laveho prvku, ako aj povodny algoritmus z prednasky. Najlepsie bude asi hodit sem kod, trochu som sa na to este potom pozeral a toto z toho vzniklo:
(tvari sa to funkcne, ale ak tam je chyba/nedostatok, rad sa necham poucit :))

  Kód:
public static int partition(int[] pole, int left, int right) {
      int pivot = pole[left];
      
      while (left<right) {
         while(pole[left]<pivot) left++;
         while(pole[right]>pivot) right--;
         if (pole[left] != pole[right]) {
            int temp = pole[left];
            pole[left] = pole[right];
            pole[right] = temp;
         } else {
            right--;
         }
      }
      return left;
   }

public static void quickSort(int[] pole, int left, int right) {
      if (left>=right) return;
      
      int pivotIdx = partition(pole, left, right);
      
      quickSort(pole, left, pivotIdx-1);
      quickSort(pole, pivotIdx+1, right);
   }
Vasnivy pestovatel binarnych stromov a opravar Turingovych strojov na polovicny uvazok.
"Problem citatov najdenych na internete je taky, ze si nikdy nemozete byt isti ich autenticitou" Abraham Lincoln
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Str Feb 24, 2010 10:32 pm

Kod, ktory si napisal je trochu iny, ako si ho opisoval. :-) Dolezita vec, ktoru si pridal je to, ze extra right--; robis len vtedy, ked su vybrane prvky rovnake (da sa lahko vidiet, ze to je vtedy, ked oba maju rovnaku hodnotu ako pivot). Dolezite je si uvedomit, ze stale alebo left alebo right su pivotom.

V pripade, ze by sa vyberal ako pivot iny prvok, aby to vsetko fungovalo, treba ho najprv vymenit s left-om. Kolegovia sa urcite potesia, ze si pre nich pripravil aj vseobecnejsiu verziu quicksortu.

Zakerna otazka na zamyslanie pre ludi z E-cka: QuickSort je dobry, ak sa ako pivot vyberie prvok, ktory by bol po utriedeni v strede (median). Ako efektivne ide najst median ?
<<

Aries

Príspevky: 379

Registrovaný: Pia Jan 30, 2009 1:26 pm

Bydlisko: 127.0.0.1

Poslať Str Feb 24, 2010 10:41 pm

FeroG píše:Kod, ktory si napisal je trochu iny, ako si ho opisoval. :-)

To uz je neskorsia verzia, ktoru som spravil az po napisani prispevku :) Predtym to bol len taky napad z hlavy, takze to asi nebolo uplne presne.

Co sa tyka medianu, pri poriadne velkych poliach by sa mohli nahodne vybrat len niektore prvky a z nich sa median da odhadnut... Potom uz len prejdeme pole a ked najdeme nieco medianu blizke, mame to. Ale pri mensich poliach by to bola asi blbost :) Neviem ci by sa tam vobec oplatilo nieco hladat, na prvy pohlad sa to zda ako prilis vela prace navyse.
Vasnivy pestovatel binarnych stromov a opravar Turingovych strojov na polovicny uvazok.
"Problem citatov najdenych na internete je taky, ze si nikdy nemozete byt isti ich autenticitou" Abraham Lincoln
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Štv Feb 25, 2010 9:53 pm

Re: Quicksort z prednasky - zacyklenie?

Aries píše:Akonahle sa za pivot vezme prvok, ktory je v poli viackrat, vznikne nekonecny cyklus v metode partition (dva rovnake prvky sa budu dookola vymienat a ukazovatel na lavy a pravy prvok sa nezmeni).
//EDIT, nezacykli sa vzdy ked su tam dva+ rovnake prvky, iba ked je tam viac takych prvkov ako je pivot.


Ďalšia zaujímavé pozorovanie vzniklo dnes na cvičeniach skupiny B (aj navzdory nedôvere menej chápavého cvičiaceho). Dá sa ukázať, že stačí, aby v poli boli nejaké 2 rovnaké hodnoty a algoritmus z prednášky sa nutne zacyklí.

Dôkaz (sporom): Zoberme si najmenšie podpole v QuickSorte, v ktorom sú obe rovnaké hodnoty spolu. Ak jedna z nich je pivotom, máme zacyklenie. V opačnom prípade sa pivotuje podľa inej hodnoty. V dôsledku pivotovania (keďže majú rovnakú hodnotu, ale inú než pivot) sa dostanú do rovnakého podpoľa. Toto podpole je menšie ako zvolené podpole. Dostávame tak spor, že sme vybrali najmenšie podpole, kde sú spolu.

Späť na PAZ1b

Kto je on-line

Užívatelia prezerajúci fórum: Žiadny registrovaný užívateľ nie je prítomný a 3 hostia

cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software.
Slovenský preklad.