Kam sortering
Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 27. november 2019; checks kræver 27 redigeringer .| Kam sortering | |
|---|---|
| Visualisering af kamsortering | |
| formål | Sorteringsalgoritme |
| værste tid | O( n 2 ) |
| Bedste tid | O ( nlogn ) |
| Gennemsnitlig tid | |
| Hukommelsesomkostninger | O(1) |
| Mediefiler på Wikimedia Commons | |
At sortere med en kam ( eng. comb sort ) er smukt[ klargør ] En forenklet sorteringsalgoritme , der oprindeligt blev designet af Włodzimierz Dobosiewicz i 1980. Den blev senere genopdaget og populariseret i en Byte Magazine -artikel fra april 1991 af Steven Lacey og Richard Box [1] . Kamsortering forbedrer boblesortering og konkurrerer med algoritmer som quicksort . Hovedideen er at eliminere skildpadder , eller små værdier i slutningen af listen, som gør boblesortering ekstremt langsom ( kaniner , store værdier i begyndelsen af listen, er ikke et problem for boblesortering).
I boblesortering, når to elementer sammenlignes, er mellemrummet (afstanden fra hinanden) 1. Den grundlæggende idé med kamsortering er, at mellemrummet kan være meget større end 1 ( Shellsortering er også baseret på denne idé, men det er en ændring af sorteringsindsættelse, ikke boblesortering).
Algoritme
I " boble ", " shaker " og " lige-ulige " sammenlignes tilstødende elementer, når der gentages over et array. Hovedideen med "kammen" er til at begynde med at tage en tilstrækkelig stor afstand mellem de sammenlignede elementer og, efterhånden som arrayet er bestilt, indsnævre denne afstand til et minimum. Således kæmmer vi arrayet og udjævner det gradvist til mere og mere nøjagtige tråde. Det indledende mellemrum mellem de sammenlignede elementer tages bedst under hensyntagen til en speciel værdi kaldet reduktionsfaktoren, hvis optimale værdi er cirka 1,247 . For det første er afstanden mellem elementerne maksimal, det vil sige lig med størrelsen af arrayet minus en. Derefter, efter at have bestået arrayet med dette trin, er det nødvendigt at dividere trinnet med reduktionsfaktoren og gå gennem listen igen. Dette fortsætter, indtil indeksforskellen når et. I dette tilfælde sammenlignes tilstødende elementer som i boblesortering, men der er kun én sådan iteration.
Den optimale værdi af reduktionsfaktoren , hvor er basis for den naturlige logaritme , og er det gyldne snit .
Implementering som inline assembly i C
For at følgende funktion skal fungere korrekt, skal arrayet, der skal sorteres, være globalt.
const int N = 100 ; int a [ N ]; dobbelt faktor = 1,2473309 ; vidsort ( ) { asm ( // variabler "movsd factor(%rip), %xmm1 \n " // faktor i xmm1 "xorl %r9d, %r9d \n " // tæller j i den indvendige cyklus i r9d "movl N(%rip), %r10d \n " // n i r10d "leaq a(%rip), %r12 \n " // a i r12 // gør skridt "cvtsi2sdl %r10d, %xmm0 \n " "divsd %xmm1, %xmm0 \n " "cvttsd2sil %xmm0, %r8d \n " // trin i r8d "jmp Check_step \n " "Inkrement_j:" "inkl %r9d \n " "Check_j:" "movl %r9d, %r11d \n " "addl %r8d, %r11d \n " "cmpl %r10d, %r11d \n " "jge Change_step \n " "movl (%r12, %r9, 4), %r13d \n " // a[j] "movl %r9d, %r11d \n " // nyt indeks i r11d "addl %r8d, %r11d \n " // nyt indeks = j + trin "movl (%r12, %r11, 4), %r14d \n " // a[j + 1] "cmpl %r14d, %r13d \n " "jle Increment_j \n " "movl %r13d, (%r12, %r11, 4) \n " "movl %r14d, (%r12, %r9, 4) \n " "jmp Increment_j \n " "Skift_trin:" "cvtsi2sdl %r8d, %xmm0 \n " "divsd %xmm1, %xmm0 \n " "cvttsd2sil %xmm0, %r8d \n " "check_step:" "cmpl $1, %r8d \n " "jl fra \n " "xorl %r9d, %r9d \n " "jmp Check_j \n " Af: ); }Implementering i Pascal
- Jeg fylder arrayet med tilfældige tal.
- Jeg starter en loop med betingelsen "i < i + j", som bogstaveligt betyder "i er forskellig fra i + j".
- Jeg nulstiller i, så indekset ikke går ud over dets grænser under en ny kørsel gennem arrayet.
- Jeg starter en indre sløjfe med betingelsen "i + j <= n", hvilket bogstaveligt betyder "summen af indeks i og afstand j mellem a[i] og et andet sammenlignet element er ikke større end det største matrixindeks".
- Hvis a[i] > a[i + j], så bytter jeg dem.
- jeg øger i.
- jeg mindsker j.
Løkken stopper først, når j bliver lig med 0, med andre ord, når i bliver lig med i + j.
Implementering i C++
void comb ( std :: vektor < int > & data ) // data er navnet på vektoren (passer ved reference, så comb(array)-kaldet ændrer array-vektoren) { dobbelt faktor = 1,2473309 ; // decrement factor int step = data . størrelse () - 1 ; // sorteringstrin //Sidste sløjfeiteration, når trin==1 svarer til én boblesorteringspas mens ( trin >= 1 ) { for ( int i = 0 ; i + trin < data . størrelse (); i ++ ) { if ( data [ i ] > data [ i + step ]) { std :: swap ( data [ i ], data [ i + trin ]); } } trin /= faktor ; } }Implementering i Java
offentlig statisk < E udvider Sammenlignelig <? super E >> void sortering ( E [] input ) { int gap = input . længde ; boolesk ombyttet = sand ; while ( gab > 1 || ombyttet ) { if ( gap > 1 ) mellemrum = ( int ) ( gab / 1.247330950103979 ); int i = 0 ; byttet = falsk ; while ( i + gap < input . length ) { if ( input [ i ] . compareTo ( input [ i + gap ] ) > 0 ) { E t = input [ i ] ; input [ i ] = input [ i + gap ] ; input [ i + gap ] = t ; byttet = sand ; } i ++ ; } } }Implementering i PHP
function combsort ( $array ) { $sizeArray = count ( $array ); // Loop gennem alle array-elementer for ( $i = 0 ; $i < $sizeArray ; $i ++ ) { // Sammenlign i par. // Start med det første og sidste element, og reducer derefter gradvist // rækken af værdier, der sammenlignes. for ( $j = 0 ; $j < $i + 1 ; $j ++ ) { // Indeks for det rigtige element i den aktuelle sammenligningsiteration $ elementRight = ( $sizeArray - 1 ) - ( $i - $j ); if ( $array [ $j ] > $array [ $elementRight ]) { $buff = $array [ $j ]; $array [ $j ] = $array [ $elementRight ]; $array [ $elementRight ] = $buff ; unset ( $buff ); } } } returnere $array ; }Implementering i Python
fra tilfældig import randint liste_1 = [ randint ( 1 , 100 ) for et i interval ( 10 )] n = len ( liste_1 ) trin = n mens trin > 1 eller q : hvis trin > 1 : trin -= 3 q , i = Falsk , 0 mens i + trin < n : hvis liste_1 [ i ] > liste_1 [ i + trin ]: liste_1 [ i ], liste_1 [ i + trin ] = liste_1 [ i + trin ], liste_1 [ i ] q = Sandt i += trinImplementering i JavaScript
function combineSorting ( matrix ) { var interval = Math . gulv ( array . længde / 1,3 ); while ( interval > 0 ) { for ( var i = 0 ; i + interval < matrix . længde ; i ++ ) { if ( matrix [ i ] > matrix [ i + interval ]) { var small = matrix [ i + interval ) ]; array [ i + interval ] = array [ i ]; matrix [ i ] = lille ; } } interval = Matematik . gulv ( interval / 1,3 ); } }Implementering i C#
byte [] bytes = Fil . ReadAllBytes ( "fil.txt" ); ulong gap = ( ulang ) bytes . Længde ; bool byttet = falsk ; while (( gap > 1 ) || byttet ) { gap = ( ulang )( gap / 1,2473309 ); hvis ( gab < 1 ) mellemrum = 1 ; ulong i = 0 ; lang m = gab ; byttet = falsk ; while ( m < ( ulong ) bytes . Length ) { if ( bytes [ i ] > bytes [ m ]) { swapped = true ; byte t = bytes [ i ]; bytes [ i ] = bytes [ m ]; bytes [ m ] = t ; } i ++; m = i + mellemrum ; } }Noter
- ↑ Lacey S., Box R. En hurtig, nem sortering: En ny forbedring gør en boblesortering til en af de hurtigste sorteringsrutiner // Byte . - April 1991. - Bd. 16, nr. 4 . - S. 315-320. — ISSN 0360-528 .
| Sorteringsalgoritmer | |
|---|---|
| Teori | Kompleksitet O notation Ordreforhold Sorter typer bæredygtige Indre Ekstern |
| Udveksling | |
| Valg | |
| indsætter | |
| fusion | |
| Ingen sammenligninger | |
| hybrid | |
| Andet | |
| upraktisk | |