Czy nie jest ktoś z was w posiadaniu Qusorta, ale metodą nierekurencyjną...
Widziałem kiedyś coś takiego w necie, nawet próbowałem skompilować ale nic z tego nie wyszło :/ Jeśli ktoś ma to będe wdzięczny :)
0
0
Wystarczy zastąpić rekurencję przez jawny stos. Ale efektywności to wiele nie zmieni.
0
Mógłbyś opisać to troche bardziej szczegółowo ;P
Nie chodzi mi o efektywność - po prostu w pewnych przypadkach qsort zawodzi... do czego nie moge dpouścić bo sypie mi sie pół programu a drugie pół nie działa jak należy...
0
nie lepiej zastosować funkcje ze standardowych bibliotek qsort jeżeli C i sort jeżeli C++ ?
0
Mimo wszystko jeśli ktoś mógłby coś o tym napisać, to byłbym wdzięczny...
0
Nie słyszałem o qsorcie nie wykorzystującym rekurencji ani własnego stosu, ale do pisania programów polecam IntroSort z STL'a. Jest szybszy od QuickSorta praktycznie w każdym wypadku.
rt+: nie, dlatego, że jeżeli myślimymy o tych samych funkcjach to są one wolniejsze, a jest to spowodowane tym, że przy każdym wywołaniu musi być przekazana jako parametr funkcja porównująca dwie wartości.
Jeżeli chodzi nierekurencyjny qsort z wykorzystaniem stosu to jest to opisane np. w książce Algorytmy i struktury danych Alfred V.Aho John E.Hopcroft Jeffrey D.Ullman. W dużym skrócie polega to na tym, że w przypadku rekurencji przy każdym wywołaniu na stos jest odkładana ramka tego wywołania :) a w naszym algorytnie robimy to po prostu jawnie na własnym stosie i można wtedy obejść rekurencję... ale wg mnie jest to beznadziejne bo zmniejsza czytelność kodu (i to jak!!!) a zysk jest niewielki - o wiele lepiej do domowych użytków zastosować rekurencję a w poważnych aplikacjach i tak trzeba korzystać z STL'a. Jeżeli jeszcze Cię nie zniechęciłem to poszukaj na googlach pod hasłami typu usuwanie rekurencji .
0
Thx, za pomoc :)