Který algoritmus dělá JavaScript Array#sort()
využití funkce? Chápu, že k provádění různých druhů může být zapotřebí nejrůznějších argumentů a funkcí, prostě mě zajímá, jaký algoritmus používá vanilkové řazení.
Odpověď
Právě jsem se podíval na zdroj WebKit (Chrome, Safari…). V závislosti na typu pole se používají různé způsoby řazení:
Číselná pole (nebo pole primitivního typu) se třídí pomocí funkce standardní knihovny C++ std::qsort
který implementuje nějakou variaci quicksortu (obvykle introsort).
Souvislá pole nenumerického typu jsou stringována a tříděna pomocí mergesort, pokud je k dispozici (pro získání stabilního řazení) nebo qsort
pokud není k dispozici žádné řazení sloučení.
Pro jiné typy (nesouvislá pole a pravděpodobně pro asociativní pole) WebKit používá buď výběrové řazení (které nazývají „min“ řazení), nebo v některých případech třídí pomocí stromu AVL. Zde je bohužel dokumentace poněkud vágní, takže byste museli sledovat cesty kódu, abyste skutečně viděli, pro které typy se používá metoda řazení.
A pak jsou tu skvosty jako tento komentář:
// FIXME: Since we sort by string value, a fast algorithm might be to use a // radix sort. That would be O(N) rather than O(N log N).
– Doufejme, že kdokoli to skutečně „opraví“, rozumí asymptotickému běhovému prostředí lépe než autor tohoto komentáře a uvědomí si, že radix sort má poněkud složitější popis běhového prostředí než jednoduše O(N).
(Děkujeme phsource za upozornění na chybu v původní odpovědi.)