sortér

Detaljer

sort er der en generisk funktion for, hvilke metoder, der kan skrives, og sort.int er den interne metode, som er kompatible med S, hvis kun de tre første argumenter er brugt.

standard sort metode gør brug af order for klassificeret objekter, hvilket igen gør brug af den generiske funktion xtfrm (og kan være langsom, medmindre en xtfrm metode har været defineret eller is.numeric(x) er sand).,

komplekse værdier sorteres først efter den virkelige del og derefter den imaginære del.

Bortset fra metode "radix" sorteringsrækkefølge for karakter vektorer, vil afhænge af den sammenstille sekvens af den landestandard, der er i brug: se Comparison. Sorteringsrækkefølgen for faktorer er rækkefølgen af deres niveauer (hvilket er særligt passende for bestilte faktorer).

Hvis partialikke er NULL, anses det for at indeholde indekser over elementer af resultatet, som skal placeres i deres korrekte positioner i det sorterede array ved delvis sortering., For hver af resultatværdierne i en bestemt position garanteres alle værdier, der er mindre end den ene, at have et mindre indeks i det sorterede array, og alle værdier, der er større, garanteres at have et større indeks i det sorterede array. (Dette er inkluderet for effektivitet, og mange af mulighederne er ikke tilgængelige for delvis sortering. Det er kun væsentligt mere effektivt, hvis partial har en håndfuld elementer, og en fuld form er gjort (Quicksort, hvis det er muligt), hvis der er mere end 10.) Navne kasseres til delvis sortering.,

Metode "quick" bruger Singleton (1969)’s implementering af Hoare er Quicksort metode, og er kun tilgængelige, når x er numerisk (dobbelt eller heltal) og partial er NULL. (For andre typer af x Shellsort anvendes, lydløst.) Det er normalt noget hurtigere end Shellsort (måske 50% hurtigere på vektorer af Længde en million og dobbelt så hurtigt på en milliard), men har dårlig ydeevne i det sjældne værste tilfælde., (Peto ‘ s modifikation ved hjælp af en pseudo-tilfældig midtpunkt bruges til at gøre det værste tilfælde sjældnere.) Dette er ikke en stabil slags, og bånd kan ombestilles.

metode "radix" er afhængig af simpel hashing for at skalere tiden lineært med inputstørrelsen, dvs.dens asymptotiske tidskompleksitet er o(n). Den specifikke variant og dens implementering stammer fra dataene.tabel pakke og er på grund af mat do .le og Arun Srinivasan., For små indgange (< 200) bruger implementeringen en indsættelsestype (o(n^2)), der fungerer på stedet for at undgå allokeringsoverhead for radi.-sorten. For heltalsvektorer af rækkevidde mindre end 100.000 skifter det til en enklere og hurtigere lineær tidstælling. I alle tilfælde er sorten stabil; rækkefølgen af bånd bevares. Det er standard metode til heltal vektorer og faktorer.

"radix" – metoden overgår generelt de andre metoder, især for tegnvektorer og små heltal., I forhold til hurtig slags, det er lidt hurtigere for vektorer med store heltal eller reelle værdier (men i modsætning til hurtig slags, radix er stabil og understøtter alle na.last indstillinger). Gennemførelsen er størrelsesordner hurtigere end shell form for karakter vektorer, delvis takket være klog anvendelse af den interne CHARSXP tabel.

der er Dog nogle begrænsninger med radix sort:

  • Hvis x er et character vektor, er alle elementer, der skal dele den samme kodning., Kun UTF-8 (herunder ASCII) og Latin-1 kodninger understøttes. Sortering følger altid” C ” locale.

  • lange vektorer (med mere end 2^32 elementer) ogcomplex vektorer understøttes endnu ikke.

Leave a Comment