Szybkie sortowanie jako metoda programowania

W 1960 roku K. A. Hoare opracował metodę szybkiego sortowania informacji, która stała się najbardziej znaną. Dzisiaj jest on szeroko stosowany w programowaniu, ponieważ ma wiele pozytywnych właściwości: można go używać w przypadkach ogólnych, wymaga niewielkiego zwiększenia pamięci dodatkowej, jest kompatybilny z różnymi typami list i jest wygodny do wdrożenia. Ale są też wady, które szybsze sortowanie: gdy używane w pracy pozwoliło na wiele błędów i jest nieco niestabilne.

Jest to jednak najstarsza wersja. Po pojawieniu się pierwszych obliczeń Hoar wiele osób angażowało się w jej gęste studium. Powstała duża baza na teoretyczne pytania o znalezienie czasu spędzonego na pracy, co zostało poparte danymi empirycznymi. Były prawdziwe propozycje poprawienia głównego algorytmu i zwiększenia szybkości pracy.

Szybkie sortowanie jest bardzo powszechne, można go znaleźć wszędzie. Opiera się on na metodzie TList.Sort, która istnieje we wszystkich wersjach (z wyjątkiem 1) Delphi, bibliotece czasu wykonywanego, qsort w C ++.

Podstawową zasadą pracy można sformułować jako "dziel i zwyciężaj". Podzielić listę na dwie grupy i sortowanie jest wykonywane dla każdej części przez siebie. Wynika z tego, że należy poświęcić więcej uwagi procesowi rozdzielania, w trakcie którego następuje: podstawowy element jest określony, a cała lista jest już przesunięta względem niego. Na lewo są tworzone grupy kandydatów, których wartości są mniejsze, wszystkie inne są przenoszone na prawo. Okazuje się, że główny element listy posortowanych znajduje się we właściwym miejscu. Następnym krokiem jest wywołanie rekursywnej funkcji sortowania dla obu stron elementów względem podstawy. Proces pracy kończy się tylko wtedy, gdy lista zawiera tylko jeden element, tzn. Zostanie on posortowany. Tak więc, w celu opanowania takiej funkcji programowania jako szybkiego sortowania, konieczne jest poznanie operacji algorytmów niższego poziomu: a) wybór elementu bazowego; B) najskuteczniejsza permutacja listy w celu uzyskania dwóch zestawów o mniejszych i większych wartościach.

Poznamy zasady pierwszego. Wybierając element bazowy, najlepiej wybrać środek z listy. Potem, gdy jest złamany, dzieli się na dwie równe części. Tylko obliczanie średniej wartości na liście jest bardzo trudne, więc nawet najszybsze sortowanie pomija ten rachunek po stronie. Ale wybór elementu głównego z wartością maksymalną lub minimalną również nie jest najlepszym rozwiązaniem. W przypadku takiej definicji jedna z utworzonych list zostanie zagwarantowana jako pusta, a druga jest przepełniona. Stąd wniosek, że jako element podstawowy należy wybrać taki, który jest bliższy średniej, ale dalej od maksymalnego i minimalnego.

Gdy zdecydujesz się na wybór, możesz przystąpić do operacji algorytmu partycjonowania. Są to tak zwane wewnętrzne cykle szybkiego sortowania. Wszystko opiera się na dwóch szybko działających indeksach: pierwsza przechodzi elementy od lewej do prawej, druga, przeciwnie, od prawej do lewej. Po prawej wykonuje się operację: indeks przechodzi przez listę i porównuje wszystkie wartości z głównym. Cykl jest uważany za kompletny, jeśli jest element mniejszy lub równy podstawce. Oznacza to, że wartość indeksu jest porównywana i malejąca. Po lewej stronie praca kończy się, gdy zostanie znaleziona większa lub równa wartość. I tu wzrasta wartość porównania.

Na tym etapie algorytm partycjonowania, który zawiera szybkie sortowanie, mogą pojawić się dwie sytuacje. Po pierwsze, indeks po lewej stronie będzie mniejszy niż po prawej. Oznacza to błąd, tzn. Elementy, na które został określony, są nieprawidłowe z listy. Wyjście zmienia miejsca. Druga sytuacja polega na tym, że obie kolumny są równe lub przecięte. Oznacza to pomyślne oddzielenie listy, tzn. Praca może być uznana za zakończoną.