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?

do góry

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.

do góry

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.

do góry

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

do góry

W dniu 24.11.2019 o 16:42, g...@g...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.

do góry