Cormen - algorytm sortujący

[Dumel]

Mając do dyspozycji procedurę BIASED_SORT() która zwraca liczbę 1 z prawdopodobieństwem p, a 0 z prawdopodobieństwem 1-p (nie znamy tych wartości) napisać funkcję SORT() która zwraca obie wartości z równym prawdopodobieństwem.
Jak sie do tego zabrać? Kombinowałem z kilkoma losowaniami i parzystością sumy wyników, ale nie wychodzi prawidłowo.

[Zeratul]

Może na przykład coś takiego rekurencyjnego:

Wykonujemy dwa razy BIASED_SORT() i zapisujemy wyniki. Jeśli pierwszy wynik to 1, a drugi 0 - zwracamy 1. Jeżeli pierwszy wynik to 0, a drugi 1 - zwracamy 0. Jeżeli oba wyniki będą równe 0 lub oba będą równe 1 - rekurencja.

Taki algorytm teoretycznie może działać w nieskończoność, ale w zadaniu pytają o oczekiwany czas działania względem \(\displaystyle{ p}\), więc podejrzewam, że być może takie rozwiązanie jest wystarczające.

BTW. Oczekiwana liczba wywołań BIASED_SORT() wyszła mi \(\displaystyle{ {1 \over p-p^2}}\), o ile się nie pomyliłem.

Kod: Zaznacz cały

SORT()
1 x=BIASED_SORT()
2 y=BIASED_SORT()
3 if x=y
4   return SORT()
5 return x

PS. Czemu niby nazywa się to u Ciebie algorytmem sortującym?

[Dumel]

faktycznie, bez sensu (zbyt często ostatnio słyszałem słowo ,,sortowanie" )
tak właśnie to losowanie w nieskończoność mi nie pasowało, jak to rozkminiałem