Cześć czy mógłby mi ktoś wytłumaczyć jak działa “pod spodem” metoda sort?
np:
mamy tablice arr= [“g”,“d”,“c”,“f”] i teraz chcemy ją posortować malejąco, zatem
arr.sort! do |x,y|
y<=>x
end
Nie rozumiem na jakiej zasadzie (jak działa algorytm tej metody) to działa.
|x,y| - oznacza że porównujemy dwa elementy, każdy ze sobą?
|x, y| to są dwa argumenty bloku (czyli czegoś wykonywanego dla każdej pary w tym przypadku).
<=> to “Combined comparison operator. Returns 0 if first operand equals second, 1
if first operand is greater than the second and -1 if first operand is
less than the second.”
Natomiast wyjaśnienie z Ruby doc: “The block must implement a comparison between a and
b, and return -1, when a follows
b, 0 when a and b are
equivalent, or +1 if b follows a.”
Gdybym miał to wyjaśnić łopatologicznie, to dla “a > b” wynikiem jest +1, co dla sort oznacza przesunięcie a o jedną pozycję do tyłu, a dla a < b" -1 i o jedną do przodu. Nie wiem, czy faktycznie tak się dzieje (na pewno nie dokładnie tak, bo w takim przypadku pętla by działała w nieskończoność dla a != b), ale wyjaśnienie nie najgorsze.
Nie wiem, jaki algorytm jest stosowany, ale wyjaśnienie, które podałem powyżej przypomina algorytm bąbelkowy. Możesz sprawdzić na Wiki co to jest sortowanie bąbelkowe. Z tego co pamiętam, jest tam nawet implementacja w Ruby.
Jeśli natomiast nie wiesz, jak działa blok, to cóż… to jest podstawa języka Ruby, więc wszędzie znajdziesz wyjaśnienia. W uproszczeniu: między pipe’ami ( |…| ) dajesz sortowi informację, że chcesz, aby on tam ci wstawił dwie liczby x i y. Tak się składa, że sort akurat przekazuje do bloku dwie liczby, więc nie ma tutaj problemu. Sort następnie wykonuje wewnętrzny kod (między do i end) kilka razy. Ile, to już zależy od samego sorta. Tyle ile trzeba.Za każdym razem przekazuje dwie nowe zmienne i wykonuje kod, a jego wynik "wciąga:’ z powrotem do swojego kodu. Można powiedzieć, że blok to sposób wrzucenia swojego kodu w środek jakiegoś innego algorytmu/w środek innej metody. W tym przypadku jest to algorytm sortowania.
Blok nie jest wykonywany dla każdej pary. Gdyby tak było to byłoby n^2 porównań, a zatem użyty algorytm miałby złożoność co najmniej kwadratową, a tak nie jest. Oczywiście liczba porównań jest zależna od zastosowanego algorytmu, ale jak zaraz się okaże, ten użyty w Rubym ma mniejszą złożoność niż kwadratowa.
Nie należy kojarzyć wartości -1, 1 bezpośrednio z przesuwaniem elementów o 1 pozycję do tyłu bądź do przodu. To są tylko i wyłącznie przyjęte wartości (równie dobrze mogło by być to 1, 2 i 3), które odpowiadają na pytanie: jak element A ma się do elementu B. -1 oznacza, że element A powinien znajdować się przed elementem B (w przyjętym porządku sortowania). 0 oznacza, że elementy są równoważne. 1 oznacza, że A powinien znajdować się za elementem B.
Całe piękno sortowania właśnie polega na tym, że posiadając pewną funkcję f(a, b), która umie porównać elementy a i b zgodnie z opisaną wcześniej regułą, możemy zastosować całą gamę algorytmów sortujących. Blok przekazywany do metody Array#sort! pełni rolę takiej funkcji. Ruby używa algorytmu quicksort. Żaden produkcyjny język nie użyłby sortowania bąbelkowego bo jego złożoność jest n^2 (quicksorta n*log n).
Ależ ja zdaję sobie sprawę z każdego wymienionego przez Ciebie punktu. Staram się tylko przybliżyć działanie całej struktury.
Mam nadzieję, że łącząc nasze odpowiedzi, użytkownik @itwillbeok zrozumie o co chodzi 