Kampalajittelu

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 27. marraskuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 27 muokkausta .
Kampalajittelu

Kampalajittelun visualisointi
tarkoitus Lajittelualgoritmi
pahin aika O( n 2 )
Paras aika O( nlogn )
Keskimääräinen aika
Muistin hinta O(1)
 Mediatiedostot Wikimedia Commonsissa

Kammalla lajittelu ( eng.  comb sort ) on nättiä[ selventää ] Yksinkertaistettu lajittelualgoritmi, jonka alun perin suunnitteli Włodzimierz Dobosiewicz vuonna 1980. Myöhemmin se löydettiin uudelleen ja tehtiin suosituksi huhtikuussa 1991 julkaistussa Steven Laceyn ja Richard Boxin Byte Magazine -artikkelissa [1] . Kampalajittelu parantaa kuplalajittelua ja kilpailee algoritmien, kuten pikalajittelun, kanssa . Pääideana on poistaa kilpikonnat eli listan lopusta pienet arvot, jotka tekevät kuplalajittelusta äärimmäisen hitaita ( kanit , suuret arvot listan alussa, eivät ole ongelma kuplalajittelussa).

Kuplalajittelussa kahta elementtiä verrattaessa aukko (etäisyys toisistaan) on 1. Kampalajittelun perusideana on, että rako voi olla paljon suurempi kuin 1 ( Tälle ajatukselle perustuu myös Shell-lajittelu , mutta se on lajittelun lisäyksen muunnos, ei kuplalajittelu).

Algoritmi

Kun " kupla ", " ravistin " ja " parillinen pariton " iteroidaan taulukon yli, verrataan vierekkäisiä elementtejä. "Kamman" pääidea on aluksi ottaa riittävän suuri etäisyys verrattujen elementtien välillä ja kaventaa tätä etäisyyttä minimiin, kun ryhmä on tilattu. Näin ollen tavallaan kampaamme matriisin tasoittaen sitä vähitellen yhä tarkempiin säikeisiin. Vertailtavien elementtien välinen alkurako otetaan parhaiten huomioon ottamalla huomioon erityinen arvo, jota kutsutaan vähennyskertoimeksi ja jonka optimaalinen arvo on noin 1,247 . Ensinnäkin elementtien välinen etäisyys on maksimi, eli yhtä suuri kuin taulukon koko miinus yksi. Sitten, kun taulukko on läpäissyt tällä vaiheella, on tarpeen jakaa askel vähennyskertoimella ja käydä luettelo uudelleen läpi. Tätä jatketaan, kunnes indeksiero saavuttaa yhden. Tässä tapauksessa vierekkäisiä elementtejä verrataan kuten kuplalajittelussa, mutta tällaista iteraatiota on vain yksi.

Vähennyskertoimen optimaalinen arvo , jossa  on luonnollisen logaritmin kanta  ja kultainen suhde .

Toteutus inline-kokoonpanona C:ssä

Jotta seuraava funktio toimisi oikein, lajiteltavan taulukon on oltava globaali.

const int N = 100 ; int a [ N ]; kaksinkertainen kerroin = 1,2473309 ; voidsort ( ) { asm ( // muuttujat "movsd factor(%rip), %xmm1 \n " // tekijä xmm1 "xorl %r9d, %r9d \n " // laskuri j r9d:n sisäisessä syklissä "movl N(%rip), %r10d \n " // n in r10d "leaq a(%rip), %r12 \n " // a in r12 // askeleen tekeminen "cvtsi2sdl %r10d, %xmm0 \n " "divsd %xmm1, %xmm0 \n " "cvttsd2sil %xmm0, %r8d \n " // askel in r8d "jmp Check_step \n " "Increment_j:" "sisältää %r9d \n " "Check_j:" "movl %r9d, %r11d \n " "lisää %r8d, %r11d \n " "cmpl %r10d, %r11d \n " "jge Change_step \n " "movl (%r12, %r9, 4), %r13d \n " // a[j] "movl %r9d, %r11d \n " // uusi hakemisto r11d:ssä "addl %r8d, %r11d \n " // uusi indeksi = j + askel "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 " "Change_step:" "cvtsi2sdl %r8d, %xmm0 \n " "divsd %xmm1, %xmm0 \n " "cvttsd2sil %xmm0, %r8d \n " "check_step:" "cmpl $1, %r8d \n " "jl pois \n " "xorl %r9d, %r9d \n " "jmp Check_j \n " Vinossa: ); }

Toteutus Pascalissa

  1. Täytän taulukon satunnaisluvuilla.
  2. Aloitan silmukan ehdolla "i < i + j", joka tarkoittaa kirjaimellisesti "i on erilainen kuin i + j".
    1. Nollasin i, jotta indeksi ei ylitä rajojaan taulukon uuden ajon aikana.
    2. Aloitan sisäisen silmukan ehdolla "i + j <= n", joka tarkoittaa kirjaimellisesti "indeksin i ja etäisyyden j summa a[i]:n ja toisen verrattavan elementin välillä ei ole suurempi kuin suurin taulukkoindeksi".
      1. Jos a[i] > a[i + j], vaihdan ne.
      2. lisään i.
    3. vähennän j.
vakio n = 5 ; var a : kokonaisluvun taulukko [ 0 .. n ] ; _ i , jr : kokonaisluku ; j : todellinen _ aloita i : = 0 - n do a [ i ] := Satunnainen ( 12 ) ; j : = n jr := Kierros ( j ) ; kun taas i < i + jr aloita i := 0 ; jr := Kierros ( j ) ; kun taas i + j <= n alkavat , jos a [ i ] > a [ i + Kierros ( j )] , sitten alkavat a [ i ] := a [ i ] + a [ i + jr ] ; a [ i + jr ] := a [ i ] - a [ i + jr ] ; a [ i ] := a [ i ] - a [ i + jr ] ; loppu ; Inc ( i ) ; loppu ; j := j / 1,247 ; loppu ; for i : = 0 - n do alkaa jr : = 0 - i - 1 aloita jos a [ jr ] > a [ jr + 1 ] sitten alkaa [ jr ] : = a [ jr ] + a [ jr + 1 ] ; a [ jr + 1 ] := a [ jr ] - a [ jr + 1 ] ; a [ jr ] := a [ jr ] - a [ jr + 1 ] ; loppu ; loppu ; loppu ; Kirjallinen ( a ) ; loppua .

Silmukka pysähtyy vain, kun j:stä tulee yhtä suuri kuin 0, toisin sanoen, kun i:stä tulee yhtä suuri kuin i + j.

Toteutus C++ :ssa

void comb ( std :: vector < int > & data ) // data on vektorin nimi (välitetään viittauksella, jotta comb(array)-kutsu muuttaa taulukkovektorin) { kaksinkertainen kerroin = 1,2473309 ; // vähennyskerroin int step = data . koko () - 1 ; // lajitteluvaihe //Viimeinen silmukan iteraatio, kun vaihe==1 vastaa yhtä kuplan lajittelua, kun ( vaihe >= 1 ) { for ( int i = 0 ; i + askel < data . koko (); i ++ ) { jos ( data [ i ] > data [ i + askel ]) { std :: swap ( data [ i ], data [ i + askel ]); } } askel /= tekijä ; } }

Toteutus Javassa

julkinen staattinen < E ulottuu Vertailukelpoinen <? super E >> void sort ( E [] input ) { int gap = input . pituus ; boolean swap = tosi ; while ( väli > 1 || vaihdettu ) { if ( aukko > 1 ) väli = ( int ) ( väli / 1.247330950103979 ); int i = 0 ; vaihdettu = false ; while ( i + väli < tulo . pituus ) { if ( tulo [ i ] . verrataTo ( tulo [ i + väli ] ) > 0 ) { E t = tulo [ i ] ; tulo [ i ] = tulo [ i + väli ] ; tulo [ i + väli ] = t ; vaihdettu = tosi ; } i ++ ; } } }

Toteutus PHP :ssä

function combsort ( $array ) { $sizeArray = count ( $array ); // Kierrä kaikki taulukkoelementit kohteelle ( $i = 0 ; $i < $sizeArray ; $i ++ ) { // Vertaa pareittain. // Aloita ensimmäisestä ja viimeisestä elementistä ja pienennä sitten vähitellen // vertailtavien arvojen aluetta. for ( $j = 0 ; $j < $i + 1 ; $j ++ ) { // Oikean elementin indeksi nykyisessä vertailuiteraatiossa $ elementRight = ( $sizeArray - 1 ) - ( $i - $j ); if ( $array [ $j ] > $array [ $elementRight ]) { $buff = $array [ $j ]; $taulukko [ $j ] = $taulukko [ $elementRight ]; $array [ $elementRight ] = $buff ; unset ( $buff ); } } } return $array ; }

Toteutus Pythonissa

satunnaisesta tuonnista randint _ lista_1 = [ randint ( 1 , 100 ) alueella ( 10 ) ] n = len ( lista_1 ) _ _ askel = n while step > 1 or q : if step > 1 : step -= 3 q , i = False , 0 while i + step < n : if list_1 [ i ] > list_1 [ i + step ]: list_1 [ i ], list_1 [ i + askel ] = lista_1 [ i + askel ], lista_1 [ i ] q = tosi i += askel

Toteutus JavaScriptissä

toiminto yhdistääLajittelu ( taulukko ) { var interval = Math . lattia ( matriisi . pituus / 1,3 ); while ( väli > 0 ) { for ( var i = 0 ; i + intervalli < taulukon pituus ; i ++ ) { if ( matriisi [ i ] > taulukko [ i + väli ] ) { var pieni = taulukko [ i + väli ]; taulukko [ i + väli ] = taulukko [ i ]; taulukko [ i ] = pieni ; } } väli = Math . kerros ( väli / 1,3 ); } }

Toteutus C#

byte [] bytes = Tiedosto . ReadAllBytes ( "tiedosto.txt" ); ulong gap = ( ulong ) tavua . Pituus ; bool vaihdettu = false ; while (( väli > 1 ) || vaihdettu ) { aukko = ( ulong )( aukko / 1.2473309 ); jos ( rako < 1 ) rako = 1 ; ulong i = 0 ; pitkä m = rako ; vaihdettu = false ; while ( m < ( ulong ) tavua . Pituus ) { if ( tavua [ i ] > tavua [ m ]) { vaihdettu = tosi ; tavu t = tavua [ i ]; tavua [ i ] = tavua [ m ]; tavua [ m ] = t ; } i ++; m = i + rako ; } }

Muistiinpanot

  1. ↑ Lacey S., Box R. Nopea, helppo lajittelu: Uusi parannus tekee kuplalajittelusta yhdeksi nopeimmista lajittelurutiineista   // Byte . - Huhtikuu 1991. - Voi. 16, ei. 4 . - s. 315-320. — ISSN 0360-528 .
 Lajittelualgoritmit
Teoria Monimutkaisuus O merkintä Tilaussuhde Lajittele tyypit kestävää Sisäinen Ulkoinen
Vaihto
Valinta
insertit
fuusio
Ei vertailuja
hybridi
Muut
epäkäytännöllistä