funkce třídění

Podrobnosti

sort je generická funkce, pro které metody může být písemná, a sort.int je interní metoda, která je kompatibilní s li pouze první tři argumenty, které jsou používány.

výchozí sort metoda využívá order pro klasifikované objekty, což zase využívá generické funkce xtfrm (a může být pomalé, pokud metoda xtfrm byla definována nebo is.numeric(x) je pravda).,

komplexní hodnoty jsou řazeny nejprve podle skutečné části, pak imaginární části.

s Výjimkou pro metoda "radix", pořadí řazení pro charakter vektorů, bude záviset na pořadí řazení pro národní prostředí v použití: Comparison. Řazení faktorů je pořadí jejich úrovní (což je zvláště vhodné pro objednané faktory).

Pokud partial NULL, to je vzato obsahují indexy prvků z výsledku, které mají být umístěny v jejich správné pozice v seřazené pole o částečné třídění., Pro každou z hodnot výsledků v zadané pozici jsou zaručeny, že jakékoli hodnoty menší než tyto budou mít menší index v tříděném poli a všechny hodnoty, které jsou větší, budou mít v tříděném poli větší index. (To je zahrnuto pro efektivitu a mnoho možností není k dispozici pro částečné třídění. To je jen podstatně efektivnější, pokud partial má několik prvků, a plné řazení je provedeno (Quicksort, pokud je to možné), pokud existuje více než 10.) Názvy jsou vyřazeny pro částečné třídění.,

metoda "quick" používá Singleton (1969)’s implementací metody Hoare Quicksort a je k dispozici pouze tehdy, když x je číselná (dvojitá nebo celočíselná) a partial je NULL. (Pro jiné typy x Shellsort se používá tiše.) Je obvykle o něco rychlejší než Shellsort (možná o 50% rychlejší na vektorech délky milion a dvakrát rychlejší na miliardu), ale ve vzácném nejhorším případě má špatný výkon., (Petova modifikace pomocí pseudo-náhodného středového bodu se používá k tomu, aby byl nejhorší případ vzácnější.) Nejedná se o stabilní druh a vazby mohou být znovu uspořádány.

metoda "radix" spoléhá na jednoduché hashování, aby lineárně měnil čas s velikostí vstupu, tj. jeho asymptotická časová složitost je o(n). Konkrétní varianta a její implementace pochází z dat.tabulka balíček a jsou vzhledem k Matt Dowle a Arun Srinivasan., U malých vstupů (< 200) používá implementace vkládací řazení (o(n^2)), které funguje na místě, aby se zabránilo alokaci nad hlavou třídiče radix. U celočíselných vektorů s rozsahem menším než 100 000 se přepne na jednodušší a rychlejší lineární Časové počítání. Ve všech případech je druh stabilní, pořadí vazeb je zachováno. Je to výchozí metoda pro celočíselné vektory a faktory.

metoda"radix" obecně překonává ostatní metody, zejména pro znakové vektory a malá celá čísla., Ve srovnání s quick sort je o něco rychlejší u vektorů s velkými celočíselnými nebo reálnými hodnotami (ale na rozdíl od quick sort je radix stabilní a podporuje všechny na.last možnosti). Implementace je řádově rychlejší než shell sort pro znakové vektory, částečně díky chytrému použití interní CHARSXP tabulky.

Nicméně, tam jsou některé výhrady s radix sort:

  • Pokud x character vektor, všechny prvky musí sdílet stejné kódování., Podporovány jsou pouze kódování UTF-8 (včetně kódování ASCII) a Latin-1. Collace vždy následuje “ C “ locale.

  • dlouhé vektory (s více než 2^32 prvky) a complex vektory ještě nejsou podporovány.

Leave a Comment