[japer]

#japeruczyibawi #programowanie #algorytmika #naukaprogramowania

Sortowanie szybkie

Co to jest sortowanie szybkie?

Jest to jedna z metod sortowania zbiorów. Jak nazwa wskazuje, ta metoda jest dość szybką metodą.

Na czym ona polega?

Metoda bazuje na fenomenie częściowego porządku. Poprzez dzielenie tablicy na mniejsze części doprowadza do posortowania. W tej metodzie ustala się element osiowy (nie musi być na środku zbioru, może być skrajnym elementem, a nawet losowym). Gdy element zostanie ustalony, algorytm sortuje jedną część na elementy mniejsze bądź równe elementowi osiowemu, a prawa strona - na elementy większe od elementu osiowego. Kiedy zostanie wprowadzony wstępny porządek, to algorytm zaczyna sortować powstałe partycje, czyli części częściowo uporządkowane.

Jak to wygląda w praktyce?

Otóż tak. Widać dokładnie, jak algorytm wybiera element osiowy i zaczyna częściowo sortować. Też należy zauważyć, że powstałe partycje nie muszą być równe.

W jaki sposób jest ustalany częściowy porządek?

Najpierw szukamy elementu, który od lewej strony nie pasuje do elementu osiowego, podobnie z prawej strony. Jeśli znajdziemy taki element - zamieniamy go miejscami. Porządkowanie uznane jest za zakończone, kiedy dwa wskaźniki przekroczą swoje partycje. Kiedy porządkowanie jest skończone, to wskaźniki od lewej i prawej wyznaczają miejsce podziału do sortowania partycji.

Kod

[Roballo]

@japer: daj #naukaprogramowania

[biczek]

@japer: dźwięki z tego filmiku mi schored earth przypominaja :D

[C.....m]

T

[k.....r]

@japer: tutaj jest bardzo dobry post o implementacji algorytmow sortujacych w c++: http://stackoverflow.com/a/24650627/2823821

[japer]

Poprawiony kod

[japer]

@kuhar: ja akurat jeszcze brodzę w starych rozwiązaniach. 8)

[k.....r]

@japer: Jak chcesz "stare" rozwiązanie, to zobacz sobie jak jest qsort w c zaimplementowany.

[moon5]

@japer: Imponujące, zwłaszcza to wideo. Poza tym, niewiele jeszcze rozumiem.

[megan_]

@japer: warto jeszcze dodać, że wbrew temu co może sugerować nazwa, nie jest to najszybszy algorytm sortujący :)

@moon5: jeśli Cię to interesuje to poczytaj sobie jakieś książki na temat algorytmiki, taką chyba najbardziej klasyczną pozycją są "Algorytmy i struktury danych" Cormena (aczkolwiek to straszna cegła i raczej nie jest prosta). Ostatnio ktoś mi jeszcze polecał taką książkę, ale jeszcze jej nie czytałam, więc nie wiem co w

[moon5]

@megan_: Dziękuję. Przejrzę, ja będę robiła coś bardziej związanego z programowaniem, czyli kontynuację nauki PHP i JS, czy poznawanie podstaw języka C.

[Z.....k]

@japer: Jeśli chodzi o quick sorta to najbardziej podoba mi się ta wizualizacja: https://www.youtube.com/watch?v=ywWBy6J5gz8 ( ͡° ͜ʖ ͡°)

no, a jeśli chodzi o kod to nic nie przebije tego w wersji Haskella:)

[japer]

@megan_: złożoność sprowadza się do kwadratu w najgorszym wypadku, zapomniałem dodać. Algorytm można zoptymalizować poprzez medianę trzech, która zmniejsza ryzyko tempa pesymistycznego.