Rychlé řazení jako programovací metoda

V roce 1960 vyvinul K. A. Hoare metodu rychlého třídění informací, která se stala nejslavnější. Dnes je široce používán v programování, protože má mnoho pozitivních vlastností: lze jej použít pro obecné případy, vyžaduje malý nárůst další paměti, je kompatibilní s různými typy seznamů a je vhodný pro implementaci. Existují však také nevýhody, které má rychlé řazení: při práci v práci je povoleno mnoho chyb a je poněkud nestabilní.

To je však nejvíce studovaná verze. Po vzhledu Hoarových prvních výpočtů se mnozí zabývali hustým studiem. Na teoretických otázkách hledání času stráveného na práci byla vytvořena velká základna, která byla podpořena empirickými daty. Byly skutečné návrhy na zlepšení hlavního algoritmu a zvýšení rychlosti práce.

Rychlé řazení je velmi běžné, lze ho najít všude. Je založen na metodě TList.Sort, která existuje ve všech verzích (s výjimkou 1) Delphi, funkce knihovny času stráveného spouštění, qsort v jazyce C ++.

Základní princip práce lze formulovat jako "rozdělit a dobýt". Rozpis seznamu je rozdělen na dvě skupiny a třídění se provádí pro každou jednotlivou část. Z toho vyplývá, že je třeba věnovat větší pozornost procesu separace, během něhož nastane následující: základní prvek je určen a celý seznam je již vzhledem k němu posunut. Skupina kandidátů je tvořena nalevo, jejichž hodnoty jsou menší, všechny ostatní jsou přeneseny doprava. Ukazuje se, že hlavní prvek v tříděném seznamu je umístěn na jeho správném místě. Dalším krokem je volání rekurzivní funkce třídění pro obě strany prvků vzhledem k základně. Proces práce končí pouze tehdy, když seznam obsahuje pouze jeden prvek, to znamená, že bude roztříděn. Abyste tak zvládli takovou programovací funkci jako rychlé řazení, musíte znát provoz algoritmů nižší úrovně: a) volbu základního prvku, b) nejúčinnější permutaci seznamu pro získání dvou sad s menšími a většími hodnotami.

Budeme se seznámit s principy prvního. Při výběru základního prvku by měl být ze seznamu vybrán prostřední prvek. Potom, když je rozbit, je rozdělen na dvě stejné poloviny. Spočítejte pouze střední hodnota v seznamu je velmi obtížné, takže i nejrychlejší třídění obchází tento počet po stranách. Ale výběr hlavního prvku s maximální nebo minimální hodnotou není také nejlepší volbou. V případě takové definice bude zaručeno, že jeden z vytvořených seznamů bude prázdný a druhý z nich bude přeplněn. Z toho vyplývá, že jako základní prvek by se měl vybrat jeden, který je bližší průměru, ale dále od maxima a minima.

Jakmile jste se rozhodli pro volbu, můžete pokračovat v operaci rozdělovacího algoritmu. Jedná se o tzv. Interní cykly rychlého řazení. Všechno je postaveno na dvou rychle pracujících ukazatelích: první bude procházet prvky zleva doprava, druhý - naopak - zprava doleva. Spustí se operace spuštění vpravo: index prochází seznamem a porovnává všechny hodnoty s hlavní hodnotou. Cyklus se považuje za úplný, jestliže je prvek menší nebo roven základnímu. To znamená, že hodnota indexu je porovnávána a snižována. Na levé straně je práce dokončena, když je nalezena větší nebo stejná hodnota. A zde se hodnota srovnání zvyšuje.

V této fázi rozdělovacího algoritmu, který obsahuje rychlé řazení, mohou nastat dvě situace. Prvním je, že index vlevo bude menší než pravý. Označuje chybu, tj. Položky, které byly zadány, jsou v seznamu nesprávné. Cesta ven mění místa. Druhá situace je, když jsou obě sloupce stejné nebo protínají. To naznačuje úspěšné rozdělení seznamu, to znamená, že práce lze považovat za dokončenou.