Szybkie sortowanie jest jedną z najlepszych metod sortowania tablic.

Jeśli programujesz, a Twój kod wykracza poza pisanie kalkulatora, często natkniesz się lub natkniesz na konieczność posortowania określonej tablicy danych. Istnieje wiele sposobów sortowania. W tym artykule przeanalizujemy główne z nich i skupimy się na szybkim sortowaniu.

Szybka koncepcja sortowania

Szybkie sortowanie - Szybkie sortowanie lub qsort. Z nazwy staje się jasne, co to jest i dlaczego. Ale jeśli nie jest to jasne, to to jest algorytm Dzięki szybkiemu sortowaniu macierzy algorytm ma średnią wydajność O (n log n). Co to znaczy? Oznacza to, że średni czas działania algorytmu wzrasta wzdłuż tej samej trajektorii, co wykres tej funkcji. Niektóre popularne języki mają wbudowane biblioteki z tym algorytmem, a to już oznacza, że ​​jest niezwykle skuteczny. Są to języki takie jak Java, C ++, C #.

Algorytm

Metoda szybkiego sortowania wykorzystuje rekursję i strategię "Podziel i pokonaj".

1. W tablicy szukamy pewnego elementu wsparcia, dla uproszczenia lepiej jest wybrać centralny, ale jeśli chcesz pracować nad optymalizacją, będziesz musiał wypróbować różne opcje.

2. Na lewo od podparcia, poszukiwany jest element większy niż referencja, a po prawej mniejszy element niż referencja, a następnie zamieniamy je. Zrób to, dopóki maksymalna wartość po prawej stronie nie będzie mniejsza niż minimum po lewej stronie. Tak więc wszystkie małe elementy są rzucane na początek, duże - do końca.

3. Rekursywnie zastosuj ten algorytm w lewej i prawej części naszego algorytmu osobno, a następnie ponownie i ponownie, aż do osiągnięcia jednego elementu lub pewnej liczby elementów. Jaka jest ta liczba elementów? Istnieje inny sposób optymalizacji tego algorytmu. Kiedy posortowana część stanie się w przybliżeniu równa 8 lub 16, może być przetworzona przez zwykłe sortowanie, na przykład sortowanie bąbelkowe. Tak więc zwiększymy efektywność naszego algorytmu, ponieważ nie przetwarza małych tablic tak szybko, jak byśmy tego chcieli.

W ten sposób cała tablica zostanie przetworzona i posortowana. A teraz obejrzymy ten algorytm wizualnie.

Szybka wydajność sortowania

Czy szybki sortuje najszybszy algorytm sortowania? Zdecydowanie nie. Teraz jest coraz więcej sortowań, w chwili gdy najszybszym sortowaniem jest Timsort, działa bardzo szybko dla tablic, które zostały pierwotnie posortowane inaczej. Ale nie zapominaj, że metoda szybkiego sortowania jest jedną z najłatwiejszych do napisania, jest bardzo ważna, ponieważ z reguły prosty projekt wymaga tylko prostej pisowni, a nie ogromnego algorytmu, którego sam nie możesz napisać. Timsort nie jest też najbardziej skomplikowanym algorytmem, ale tytuł najprostszego nie świeci mu specjalnie.

Implementacja algorytmu

Cóż, dotarliśmy do "pysznego". Teraz spójrzmy, jak ten algorytm jest zaimplementowany. Jak wspomniano wcześniej, nie jest to zbyt skomplikowane do wdrożenia, a nawet proste. Wciąż jednak analizujemy wszystkie działania naszego kodu, aby zrozumieć, jak działa szybkie sortowanie.

Nasza metoda nazywa się quickSort. Działa na głównym algorytmie, w którym przenosimy tablicę, jej pierwsze i ostatnie elementy. Zapamiętywamy w zmiennych i i k pierwszy i ostatni element posortowanego segmentu, aby nie zmieniać tych zmiennych, ponieważ są one nam potrzebne. Następnie sprawdzamy odległość między pierwszym a ostatnim sprawdzanym: czy jest większy lub równy jeden? Jeśli nie, to dotarliśmy do centrum i musimy wydostać się z sortowania tego segmentu, a jeśli tak, kontynuujemy sortowanie.

Następnie bierzemy pierwszy element w segmencie posortowanym dla elementu wspierającego. Robimy następny cykl, aż dotrzemy do centrum. W tym robimy jeszcze dwa cykle: pierwszy jest dla lewej części, a drugi dla prawej. Przeprowadzamy je tak długo, jak istnieją elementy, które pasują do stanu, lub do momentu dotarcia do elementu nośnego. Następnie, jeśli minimalny element nadal znajduje się po prawej stronie, a maksimum po lewej, zamień je. Po zakończeniu cyklu zmień pierwszy element i odniesienie, jeśli wartość odniesienia jest mniejsza. Następnie rekurencyjnie wykonujemy nasz algorytm dla prawej i lewej części tablicy, i tak dalej, aż dotrzemy do segmentu o długości 1 elementu. Wtedy wszystkie nasze algorytmy rekursywne powrócą i całkowicie zakończymy sortowanie. Również na dole znajduje się metoda wymiany - dość standardowa metoda podczas sortowania tablicy zamienników. Aby kilka razy nie zapisywać zastąpienia elementów, piszemy raz i zmieniamy elementy w tej tablicy.

Podsumowując, można powiedzieć, że pod względem stosunku jakości do złożoności szybkie sortowanie znajduje się w czołówce wśród wszystkich algorytmów, więc powinieneś zdecydowanie zanotować metodę i użyć jej w razie potrzeby w swoich projektach.