Kam sortering

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 27 november 2019; kontroller kräver 27 redigeringar .
Kam sortering

Visualisering av kamsortering
ändamål Sorteringsalgoritm
värsta tiden O( n 2 )
Lämpligast tid O( nlogn )
Snittid
Minneskostnad O(1)
 Mediafiler på Wikimedia Commons

Att sortera med en kam ( eng.  comb sort ) är snyggt[ förtydliga ] En förenklad sorteringsalgoritm som ursprungligen designades av Włodzimierz Dobosiewicz 1980. Den återupptäcktes senare och populariserades i en April 1991 Byte Magazine- artikel av Steven Lacey och Richard Box [1] . Kamsortering förbättras på bubbelsortering och konkurrerar med algoritmer som quicksort . Huvudidén är att eliminera sköldpaddor , eller små värden i slutet av listan, vilket gör bubbelsortering extremt långsam ( kaniner , stora värden i början av listan, är inte ett problem för bubbelsortering).

I bubbelsortering, när två element jämförs, är gapet (avståndet från varandra) 1. Grundidén med kamsortering är att gapet kan vara mycket större än 1 ( Shellsorteringen är också baserad på denna idé, men det är en modifiering av sorteringsinsättning, inte bubbelsortering).

Algoritm

I " bubblan ", " shaker " och " jämnt-udda ", när man itererar över en array, jämförs intilliggande element. Huvudidén med "kammen" är att initialt ta ett tillräckligt stort avstånd mellan de jämförda elementen och, allteftersom arrayen är beställd, minska detta avstånd till ett minimum. Således kammar vi arrayen och jämnar gradvis ut den till mer och mer exakta strängar. Det initiala gapet mellan de jämförda elementen tas bäst med i beräkningen av ett speciellt värde som kallas reduktionsfaktorn, vars optimala värde är cirka 1,247 . För det första är avståndet mellan elementen maximalt, det vill säga lika med storleken på arrayen minus ett. Sedan, efter att ha passerat arrayen med detta steg, är det nödvändigt att dividera steget med reduktionsfaktorn och gå igenom listan igen. Detta fortsätter tills indexskillnaden når ett. I det här fallet jämförs närliggande element som i bubbelsortering, men det finns bara en sådan iteration.

Det optimala värdet för reduktionsfaktorn , där  är basen för den naturliga logaritmen , och  är det gyllene snittet .

Implementering som inline-sammansättning i C

För att följande funktion ska fungera korrekt måste arrayen som ska sorteras vara global.

const int N = 100 ; int a [ N ]; dubbel faktor = 1,2473309 ; vidsort ( ) { asm ( // variabler "movsd factor(%rip), %xmm1 \n " // faktor i xmm1 "xorl %r9d, %r9d \n " // räknare j i den inre cykeln i r9d "movl N(%rip), %r10d \n " // n i r10d "leaq a(%rip), %r12 \n " // a i r12 // gör steg "cvtsi2sdl %r10d, %xmm0 \n " "divsd %xmm1, %xmm0 \n " "cvttsd2sil %xmm0, %r8d \n " // stega in 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 Ändra_steg \n " "movl (%r12, %r9, 4), %r13d \n " // a[j] "movl %r9d, %r11d \n " // nytt index i r11d "addl %r8d, %r11d \n " // nytt index = j + steg "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 " "Ändra_steg:" "cvtsi2sdl %r8d, %xmm0 \n " "divsd %xmm1, %xmm0 \n " "cvttsd2sil %xmm0, %r8d \n " "check_step:" "cmpl $1, %r8d \n " "jl av \n " "xorl %r9d, %r9d \n " "jmp Check_j \n " Av: ); }

Implementering i Pascal

  1. Jag fyller arrayen med slumptal.
  2. Jag startar en loop med villkoret "i < i + j", vilket ordagrant betyder "i är annorlunda än i + j".
    1. Jag återställer i så att indexet inte går över sina gränser under en ny körning genom arrayen.
    2. Jag startar en inre slinga med villkoret "i + j <= n", vilket ordagrant betyder "summan av index i och avståndet j mellan a[i] och ett annat jämfört element är inte större än det största arrayindexet".
      1. Om a[i] > a[i + j], så byter jag dem.
      2. jag ökar i.
    3. Jag minskar j.
const n = 5 ; var a : array [ 0..n ] av heltal ; _ _ i , jr : heltal ; j : äkta _ börja för i := 0 till n gör a [ i ] := Slumpmässig ( 12 ) ; j : = n jr := Rund ( j ) ; medan i < i + jr börjar i : = 0 ; jr := Rund ( j ) ; medan i + j <= n börjar om a [ i ] > a [ i + Rund ( j ) ] börjar sedan a [ i ] := a [ i ] + a [ i + jr ] ; a [ i + jr ] := a [ i ] - a [ i + jr ] ; a [ i ] := a [ i ] - a [ i + jr ] ; slut ; Inc ( i ) ; slut ; j := j / 1,247 ; slut ; för i := 0 till n börjar för jr := 0 till i - 1 börjar om a [ jr ] > a [ jr + 1 ] sedan börjar a [ jr ] : = a [ jr ] + a [ jr + 1 ] ] ; a [ jr + 1 ] : = a [ jr ] - a [ jr + 1 ] ; a [ jr ] := a [ jr ] - a [ jr + 1 ] ; slut ; slut ; slut ; Skrivln ( a ) ; slut .

Slingan stannar först när j blir lika med 0, med andra ord när i blir lika med i + j.

Implementering i C++

void comb ( std :: vektor < int > & data ) // data är namnet på vektorn (passera förbi referens så att comb(array)-anropet ändrar arrayvektorn) { dubbel faktor = 1,2473309 ; // minska faktor int steg = data . storlek () - 1 ; // sorteringssteg //Sista loop-iteration när steg==1 motsvarar en bubbelsorteringspass medan ( steg >= 1 ) { för ( int i = 0 ; i + steg < data . storlek (); i ++ ) { if ( data [ i ] > data [ i + steg ]) { std :: swap ( data [ i ], data [ i + steg ]); } } steg /= faktor ; } }

Implementering i Java

offentlig statisk < E sträcker sig Jämförbar <? super E >> void sort ( E [] input ) { int gap = input . längd ; boolesk swappad = sant ; while ( gap > 1 || swappad ) { if ( gap > 1 ) gap = ( int ) ( gap / 1,247330950103979 ); int i = 0 ; bytte = falskt ; 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 ; bytte = sant ; } i ++ ; } } }

Implementering i PHP

function combsort ( $array ) { $sizeArray = count ( $array ); // Gå igenom alla arrayelement för ( $i = 0 ; $i < $sizeArray ; $i ++ ) { // Jämför i par. // Börja med det första och sista elementet, minska sedan gradvis // intervallet för värden som jämförs. för ( $j = 0 ; $j < $i + 1 ; $j ++ ) { // Index för det högra elementet i den aktuella jämförelseiterationen $ elementRight = ( $sizeArray - 1 ) - ( $i - $j ); if ( $array [ $j ] > $array [ $elementRight ]) { $buff = $array [ $j ]; $array [ $j ] = $array [ $elementRight ]; $array [ $elementRight ] = $buff ; unset ( $buff ); } } } returnera $array ; }

Implementering i Python

från slumpmässig import randint list_1 = [ randint ( 1 , 100 ) för ett inom intervallet ( 10 )] n = len ( list_1 ) steg = n medan steg > 1 eller q : om steg > 1 : steg -= 3 q , i = Falskt , 0 medan i + steg < n : om list_1 [ i ] > list_1 [ i + steg ]: list_1 [ i ], list_1 [ i + steg ] = list_1 [ i + steg ], list_1 [ i ] q = Sant i += steg

Implementering i JavaScript

function combineSorting ( array ) { var interval = Math . golv ( array . längd / 1,3 ); while ( intervall > 0 ) { for ( var i = 0 ; i + intervall < array . length ; i ++ ) { if ( array [ i ] > array [ i + intervall ]) { var small = array [ i + intervall ] ]; array [ i + intervall ] = array [ i ]; array [ i ] = liten ; } } intervall = Math . golv ( intervall / 1,3 ); } }

Implementering i C#

byte [] bytes = Fil . ReadAllBytes ( "file.txt" ); ulong gap = ( ulong ) byte . Längd ; bool swappad = false ; while (( gap > 1 ) || swappad ) { gap = ( ulong )( gap / 1,2473309 ); if ( gap < 1 ) gap = 1 ; ulong i = 0 ; lång m = gap ; bytte = falskt ; while ( m < ( ulong ) bytes . Length ) { if ( bytes [ i ] > bytes [ m ]) { swapped = true ; byte t = byte [ i ]; bytes [ i ] = bytes [ m ]; bytes [ m ] = t ; } i ++; m = i + gap ; } }

Anteckningar

  1. ↑ Lacey S., Box R. En snabb, enkel sortering: En ny förbättring gör en bubbelsortering till en av de snabbaste  sorteringsrutinerna  // Byte . - April 1991. - Vol. 16, nr. 4 . - s. 315-320. — ISSN 0360-528 .
 Sorteringsalgoritmer
Teori Komplexitet O notation Orderförhållande Sorteringstyper hållbar Inre Extern
Utbyta
Val
Insatser
fusion
Inga jämförelser
hybrid
Övrig
opraktisk