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 .
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 .
![{\displaystyle 1{,}247...={\tfrac {1}{1-e^{-\phi ))))](https://wikimedia.org/api/rest_v1/media/math/render/svg/675c0ec636cd237bb29d3eafe6e24263bb228bfa)
![e](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd253103f0876afc68ebead27a5aa9867d927467)
![\phi](https://wikimedia.org/api/rest_v1/media/math/render/svg/72b1f30316670aee6270a28334bdf4f5072cdde4)
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
- Täytän taulukon satunnaisluvuilla.
- Aloitan silmukan ehdolla "i < i + j", joka tarkoittaa kirjaimellisesti "i on erilainen kuin i + j".
- Nollasin i, jotta indeksi ei ylitä rajojaan taulukon uuden ajon aikana.
- 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".
- Jos a[i] > a[i + j], vaihdan ne.
- lisään i.
- 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.
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ä ;
}
}
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 ++ ;
}
}
}
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 ;
}
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
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
- ↑ 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 .