Programátoři, kteří přecházejí z vývoje na PC a webu na kódování pro mobilní zařízení nebo vestavěné systémy, zjišťují, že více času stráví výběrem a kódováním jejich vlastních datových struktur a algoritmů. S menší pamětí a omezeným úložištěm dat zde není místo pro předem vytvořené knihovny nebo frameworky. Takže pro ty, kteří si potřebují napsat své vlastní postupy třídění, zde jsou některé úvahy o výběru nízko bublinového třídění.
Pozadí
Bublinové řazení je jednoduchý algoritmus, který třídí seznam položek v paměti. Dané pole kód opakovaně porovnává každý pár sousedních položek a vyměňuje je, pokud nejsou v pořádku. Proces se opakuje, dokud již nedojde k žádné výměně. Pokud by bylo možné zobrazit pole, zatímco probíhá řazení, nízké hodnoty by „bublaly“ nahoru, zatímco velké hodnoty by klesaly dolů. Zde je příslušný kód ve Visual Basic 2010:
Video dne
Zatímco swap = True swap = False For i = 0 To tbl.length - 2 If tbl (i) > tbl (i + 1) Then tmp = tbl (i) tbl (i) = tbl (i + 1) tbl (i + 1) = tmp swap = True End If Next End While
Kdy zvolit bublinové řazení
Tento algoritmus má několik výhod. Jednoduše se píše, je srozumitelný a zabere jen pár řádků kódu. Data jsou setříděna na místě, takže jejich režie je malá, a jakmile jsou data roztříděna, jsou v paměti a připravena ke zpracování. Velkou nevýhodou je časová náročnost třídění. Průměrný čas se zvyšuje téměř exponenciálně s rostoucím počtem prvků tabulky. Třídění desetinásobku počtu položek trvá téměř stokrát déle.
Další druhy pole
Algoritmy řazení se liší složitostí, rychlostí a režií. Bublinové řazení je nejméně složité, ale také jedno z nejpomalejších. Jiné druhy založené na poli, jako je řazení vložení a řazení výměny, jsou o něco rychlejší, ale vyžadují více kódu (viz odkazy níže). Hlavní výhodou řazení založených na poli je, že používají nejméně kódu a zabírají nejmenší množství pracovní paměti. Zvažte tyto druhy pro jednoduchá pole s méně než několika stovkami položek.
Komplexní třídicí algoritmy
Větší datové sady vyžadují složitější kód a více paměti. Rychlé řazení a třídění haldy jak rozděluje, tak kopíruje soubory dat, aby se optimalizoval počet srovnání. Rychlé třídění neustále rozděluje seznam a poté jej znovu sestavuje v seřazeném pořadí. Řazení haldy zkopíruje data do stromové struktury a poté projde strom, aby zkopírovala data zpět do pořadí. Oba jsou rychlé a efektivní, ale vyžadují více kódu a mnohem větší pracovní úložiště. Vyberte tyto algoritmy pro velké soubory dat.
