Szybkie sortowanie jako metoda programowania

W 1960 r. K.A. Hoare opracował metodę szybkiego sortowania informacji, która stała się najbardziej znana. Obecnie jest szeroko stosowany w programowaniu, ponieważ ma wiele pozytywnych właściwości: może być stosowany w ogólnych przypadkach, wymaga niewielkiego zwiększenia dodatkowej pamięci, jest kompatybilny z różnymi typami list i jest wygodny do wdrożenia. Ale są też wady, które charakteryzują szybkie sortowanie: gdy jest używany w pracy, wiele błędów jest dozwolonych i jest nieco niestabilne.

Jednak jest to najbardziej przebadana wersja. Po pojawieniu się pierwszych obliczeń Hoara wielu zaangażowało się w jej gęste badania. Powstała duża baza teoretycznych pytań o znalezienie czasu przeznaczonego na pracę, która została poparta danymi empirycznymi. Pojawiły się prawdziwe propozycje ulepszenia głównego algorytmu i zwiększenia szybkości pracy.

Szybkie sortowanie jest bardzo powszechne, możeszspotkać się wszędzie. Opiera się na metodzie TList.Sort, która istnieje we wszystkich wersjach (z wyjątkiem 1) Delphi, funkcji bibliotecznej czasu poświęconego na wykonywanie, qsort w C ++.

Podstawową zasadę pracy można sformułować jako"dziel i rządź". Istnieje podział listy na dwie grupy i sortowanie odbywa się dla każdej części samodzielnie. Wynika z tego, że należy zwrócić większą uwagę na proces separacji, podczas którego następuje: element podstawowy jest ustalany, a cała lista jest już przesunięta względem niego. Po lewej stronie formuje się grupa kandydatów, których wartości są mniejsze, a wszystkie inne są przenoszone na prawo. Okazuje się, że główny element na posortowanej liście znajduje się w odpowiednim miejscu. Następnym krokiem jest wywołanie funkcji sortowania rekurencyjnego dla obu stron elementów względem podstawy. Proces pracy kończy się tylko wtedy, gdy lista zawiera tylko jeden element, to znaczy zostanie posortowana. Zatem, aby opanować taką funkcję programowania jak szybkie sortowanie, trzeba znać działanie algorytmów niższego poziomu: a) wybór elementu bazowego; b) najbardziej efektywną permutację listy dla uzyskania dwóch zbiorów o mniejszych i większych wartościach.

Zapoznamy się z zasadami pierwszego. Wybierając element bazowy, najlepiej wybrać środkowy z listy. Następnie, po rozbiciu, dzieli się na dwie równe części. Oblicz tylko, że średnia wartość na liście jest bardzo trudna, więc nawet najszybsze sortowanie pomija ten rachunek z boku. Ale wybór głównego elementu z maksymalną lub minimalną wartością również nie jest najlepszą opcją. W przypadku takiej definicji jedna z utworzonych list będzie gwarantowana jako pusta, a druga z nich przepełniona. Stąd wniosek, że jako element podstawowy należy wybrać taki, który jest bliższy średniej, ale dalej od maksimum i minimum.

Gdy już zdecydujesz się na wybór, możeszprzejdź do pracy algorytmu partycjonowania. Są to tak zwane wewnętrzne szybkie cykle sortowania. Wszystko opiera się na dwóch szybko działających wskaźnikach: pierwszy przejdzie od lewej do prawej, drugi od prawej do lewej. Rozpocznie się operacja wykonania z prawej: indeks przechodzi przez listę i porównuje wszystkie wartości z głównym. Cykl uznawany jest za zakończony, jeśli istnieje element mniejszy lub równy pierwszemu. Oznacza to, że wartość indeksu jest porównywana i maleje. Po lewej stronie praca kończy się, gdy zostanie znaleziona większa lub równa wartość. I tutaj wzrasta wartość porównania.

Na tym etapie algorytmu partycjonowaniaktóry zawiera szybki sort, mogą powstać dwie sytuacje. Po pierwsze indeks po lewej będzie mniejszy niż prawy. Oznacza to błąd, tzn. Elementy, do których zostały podane, znajdują się w niewłaściwej kolejności na liście. Wyjście zmienia miejsca. Druga sytuacja ma miejsce, gdy obie kolumny są równe lub przecinają się. Wskazuje to na pomyślny podział listy, to znaczy pracę można uznać za kompletną.

</ p></ p>>