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.

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 ?

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);
   }

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 ?

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.

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.