🚀 go-pugleaf

Dla prostoty weźmy Haskellową implementację (pseudo) quicksorta:

qsort [] = []
qsort (h:t) = (qsort [x|x<-t, x<h]) \
       ++[h]++(qsort [x|x<-t, x>=h])

Jeżeli tylko
x >= y <=> ~(x < y)
i jeżeli każde wywołanie x < y daje tę samą wartość, to lewa i prawa strona listy będzie każdorazowo malała przy kolejnych wywołaniach rekurencyjnych (bo są rozłączne, i wyciągamy z listy jeden element, h).
Dlatego brak przechodniości operatora < nie powinna mieć wpływu na to, czy algorytm się zakończy.

W prawdziwym quicksorcie jest lepiej, bo tam wywołujesz funkcję porównującą tylko raz na iterację dla każdego elementu, i przerzucasz elementy na lewo i prawo od pivota. Ale schemat rekursji jest dokładnie taki sam.

Rezultat będzie oczywiście niezdefiniowany, ale algorytm się zakończy.

On Sunday, November 24, 2019 at 8:49:55 AM UTC, Borneq wrote:
> Pytanie z Algorytmów i struktur danych
> Co się zdarzy, gdy funkcja oceniająca będzie dawała dziwne wyniki:
> typu A<B , B<C, ale C<A ?
> Czy w QuickSort zawsze pyta się minimalna ilość razy?
> Ale z drugiej strony, może być początkowe posortowanie takie że 
> QuickSort będzie miał złożoność kwadratową, czyli na pewno nie pyta 
> minimalna ilość razy. Co wtedy? QuickSort się wykrzaczy? Jak się to objawi?

Objawi ci się to kwadratową złożonością algorytmu...
czyli dla tablicy 1000 elementów wykonasz milion porównań.
Mała ciekawostka: największym koszmarem quicksorta jest tablica częściowo posortowana.

On Sunday, November 24, 2019 at 9:50:35 PM UTC+1, Tomasz Konstanty Maluszycki wrote:
> On Sunday, November 24, 2019 at 8:49:55 AM UTC, Borneq wrote:
> > Pytanie z Algorytmów i struktur danych
> > Co się zdarzy, gdy funkcja oceniająca będzie dawała dziwne wyniki:
> > typu A<B , B<C, ale C<A ?
> > Czy w QuickSort zawsze pyta się minimalna ilość razy?
> > Ale z drugiej strony, może być początkowe posortowanie takie że 
> > QuickSort będzie miał złożoność kwadratową, czyli na pewno nie pyta 
> > minimalna ilość razy. Co wtedy? QuickSort się wykrzaczy? Jak się to objawi?
> 
> [...]
> Mała ciekawostka: największym koszmarem quicksorta jest tablica częściowo 
> posortowana.

Trzeba wybierać losowo element 'podziału'.
Pozdrawiam

W dniu 24.11.2019 o 16:42, godek.maciek@gmail.com pisze:
> Dlatego brak przechodniości operatora < nie powinna mieć wpływu na to, czy algorytm się zakończy.

A czy da się uzyskać infrmację, że w pewnym kroku porównanie było 
nieprzechodnie?
A co gdy mamy wiele elementów równych sobie, tak że mamy zawsze wybór z 
trzech a nie dwóch możliwości, gdyby były tak samo prawdopodobne, to 
zysk byłby log(3)/log(2)=1.58 raza.