fil quicksort Mariusz: https://prnt.sc/stszo0 Znalazłem u pewnej Hinduski kod quick sorta Jednak ma pewien błąd w funkcji partycjonującej Ciekaw jestem czy znajdziesz błąd Ona bierze pierwszy element jako tzw pivot Jak zmodyfikowałbyś jej kod aby na tzw pivota był brany losowo wybrany element Jak według ciebie wyglądałby iteracyjny równoważnik tego algorytmu

fil: W sensie iteracyjny quicksort? to chyba na std::stack() sie robi

Mariusz: No tak ale zobacz na kod jej programu Coś nie tak jest z wersją rekurencyjną przedstawionego przez nią algorytmu https://ideone.com/865Hcm

fil: A co to jest lB (lower bound) oraz uB (upper bound) −− z tego co ona robi, wynika ze sa to indeksy tak?

fil: I wedlug mnie brakuje ifow() w ciele funkcji quicksort()

fil: A raczej juz mam blad, w ifie powinno byc "lb + 1 < ub"

fil: Jednak nie, szukam dalej

Mariusz: Dobrze odczytałeś znaczenie zmiennych lb oraz ub Jeśli chcesz wskazówkę to przeanalizuj obieg głównej pętli w funkcji Partition

fil: ehh, nadal nic, dlatego sie nie pisze wlasnorecznie wbudowanych funkcji. Jak ten caly kod mozna zmienic: const auto pivot_iter = std:rev(end); const auto par_point = std:artition(begin, end, [pivot_iter](auto arg) { return arg < *pivot_iter; }); gdzie begin, end to ireratory

Mariusz: nie pisze wlasnorecznie wbudowanych funkcji no a później się nie wie jak dany algorytm działa a poza tym z czytaniem kodu też są problemy

Mariusz: Ja wiem gdzie ta Hinduska ma błąd Chciałem sprawdzić czy tobie uda się go wskazać Gdybyś wczytał się w kod to pewnie też byś

fil: Czesc Mariusz, troche mi sie zapomnialo aby tu zajrzec bo jutro juz zaczynam matury . Czy blad jest w tym momencie? while (A[start] <= pivot) start++ −−− w warunku while() nie powinnismy dodac jeszcze jednego warunku, ze start < A.size() − 1?

Mariusz: No właśnie znalazłeś błąd Aby go naprawić popatrz na warunek z zewnętrznej pętli Wydaje mi się że wystarczy dopisać we wskazanej przez ciebie pętli warunek z poprzedniej pętli przy czym ten warunek z poprzedniej pętli musi być sprawdzany jako pierwszy Ta Hinduska po prostu nie sprawdzała czy czy wewnętrzna iteracja się zatrzyma Powodzenia na maturze Ja z matematyki miałem dobry z pisemnego i bardzo dobry z ustnego U mnie matematyka to był przedmiot z wyboru W maju tego roku minęła okrągła rocznica mojej matury

fil: A w twoich czasach byla juz matura z informatyki?

Mariusz: Nie pamiętam już dokładnie Jeśli chodzi o iteracyjną wersję Quick Sorta to nie podałeś szczegółów ale pewną propozycję podają na ważniaku http://wazniak.mimuw.edu.pl/index.php?title=Algorytmy_i_struktury_danych/Sortowanie:_MergeSort%2C_HeapSort_i_QuickSort na samym końcu artykułu