Hřebenové třídění

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 27. listopadu 2019; kontroly vyžadují 27 úprav .
Hřebenové třídění

Vizualizace hřebenového řazení
účel Algoritmus řazení
nejhorší čas O( n 2 )
Nejlepší čas O( nlogn )
Průměrný čas
Náklady na paměť O(1)
 Mediální soubory na Wikimedia Commons

Řazení hřebenem ( angl.  comb sort ) je hezké[ upřesnit ] Zjednodušený třídicí algoritmus původně navržený Włodzimierzem Dobosiewiczem v roce 1980. Později byl znovu objeven a popularizován v článku v časopise Byte z dubna 1991 od Stevena Laceyho a Richarda Boxe [1] . Comb sort vylepšuje bublinové řazení a konkuruje algoritmům jako quicksort . Hlavní myšlenkou je eliminovat želvy nebo malé hodnoty na konci seznamu, díky kterým je řazení podle bublin extrémně pomalé ( králíci , velké hodnoty na začátku seznamu nejsou pro řazení podle bublin problém).

V bublinovém třídění, když se porovnávají dva prvky, je mezera (vzdálenost od sebe) 1. Základní myšlenkou hřebenového třídění je, že mezera může být mnohem větší než 1 ( Skořápkové třídění je také založeno na této myšlence, ale jedná se o modifikaci vkládání třídění, nikoli o bublinové třídění).

Algoritmus

V " bublině ", " třepačce " a " sudé-liché " se při iteraci přes pole porovnávají sousední prvky. Hlavní myšlenkou "hřebenu" je zpočátku zaujmout dostatečně velkou vzdálenost mezi porovnávanými prvky a, jak je pole uspořádáno, zúžit tuto vzdálenost na minimum. Pole tak nějak češeme a postupně uhlazujeme do stále přesnějších pramenů. Počáteční mezeru mezi porovnávanými prvky je nejlépe zohlednit s přihlédnutím ke speciální hodnotě zvané redukční faktor, jejíž optimální hodnota je přibližně 1,247 . Za prvé, vzdálenost mezi prvky je maximální, tedy rovna velikosti pole mínus jedna. Poté, co jsme prošli polem s tímto krokem, je nutné vydělit krok redukčním faktorem a znovu projít seznam. Toto pokračuje, dokud rozdíl indexu nedosáhne jedné. V tomto případě se sousední prvky porovnávají jako v bublinovém třídění, ale existuje pouze jedna taková iterace.

Optimální hodnota redukčního faktoru , kde  je základna přirozeného logaritmu a  je zlatý řez .

Implementace jako inline sestava v C

Aby následující funkce fungovala správně, musí být řazené pole globální.

const int N = 100 ; int a [ N ]; dvojnásobný faktor = 1,2473309 ; voidsort ( ) { asm ( // proměnné "movsd factor(%rip), %xmm1 \n " // faktor v xmm1 "xorl %r9d, %r9d \n " // čítač j ve vnitřním cyklu v r9d "movl N(%rip), %r10d \n " // n v r10d "leaq a(%rip), %r12 \n " // a v r12 // dělá krok "cvtsi2sdl %r10d, %xmm0 \n " "divsd %xmm1, %xmm0 \n " "cvttsd2sil %xmm0, %r8d \n " // krok v r8d "jmp Check_step \n " "Increment_j:" "včetně %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 " // nový index v r11d "addl %r8d, %r11d \n " // nový index = j + krok "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 " "Krok_změny:" "cvtsi2sdl %r8d, %xmm0 \n " "divsd %xmm1, %xmm0 \n " "cvttsd2sil %xmm0, %r8d \n " "check_step:" "cmpl $1, %r8d \n " "jl vypnuto \n " "xorl %r9d, %r9d \n " "jmp Check_j \n " Vypnuto: ); }

Implementace v Pascalu

  1. Vyplňuji pole náhodnými čísly.
  2. Začnu smyčku s podmínkou "i < i + j", což doslova znamená "i se liší od i + j".
    1. Obnovil jsem i, aby index nepřekročil své hranice při novém průchodu polem.
    2. Zahájím vnitřní smyčku s podmínkou "i + j <= n", což doslova znamená "součet indexu i a vzdálenosti j mezi a[i] a dalším porovnávaným prvkem není větší než největší index pole".
      1. Pokud a[i] > a[i + j], pak je prohodím.
      2. zvětšuji i.
    3. snižujem j.
konst n = 5 ; var a : pole [ 0 .. n ] celého čísla ; i , jr : celé číslo ; j : skutečný _ begin for i := 0 až n do a [ i ] := Náhodné ( 12 ) ; j : = n jr := Kolo ( j ) ; zatímco i < i + jr do begin i := 0 ; jr := Kolo ( j ) ; while i + j <= n do begin if a [ i ] > a [ i + Round ( j )] then begin a [ i ] := a [ i ] + a [ i + jr ] ; a [ i + jr ] := a [ i ] - a [ i + jr ] ; a [ i ] := a [ i ] - a [ i + jr ] ; konec ; Inc ( i ) ; konec ; j := j / 1,247 ; konec ; for i := 0 až n do begin for jr := 0 až i - 1 do begin if a [ jr ] > a [ jr + 1 ] pak begin a [ jr ] := a [ jr ] + a [ jr + 1 ] ; a [ jr + 1 ] := a [ jr ] - a [ jr + 1 ] ; a [ jr ] := a [ jr ] - a [ jr + 1 ] ; konec ; konec ; konec ; Writeln ( a ) ; konec .

Smyčka se zastaví pouze tehdy, když se j rovná 0, jinými slovy, když se i rovná i + j.

Implementace v C++

void comb ( std :: vector < int > & data ) // data jsou název vektoru (předat odkazem, takže volání comb(array) změní vektor pole) { dvojnásobný faktor = 1,2473309 ; // faktor snížení int krok = data . velikost () - 1 ; // krok řazení // iterace poslední smyčky, když krok==1 je ekvivalentní jednomu průchodu řazení pomocí bublin while ( krok >= 1 ) { for ( int i = 0 ; i + krok < data . velikost (); i ++ ) { if ( data [ i ] > data [ i + krok ]) { std :: swap ( data [ i ], data [ i + krok ]); } } krok /= faktor ; } }

Implementace v Javě

public static < E extends Comparable <? super E >> void sort ( E [] input ) { int gap = input . délka ; boolean swapped = true ; while ( mezera > 1 || prohozena ) { if ( mezera > 1 ) mezera = ( int ) ( mezera / 1,247330950103979 ); int i = 0 ; swapped = false ; while ( i + mezera < vstup . délka ) { if ( vstup [ i ] . porovnejTo ( vstup [ i + mezera ] ) > 0 ) { E t = vstup [ i ] ; vstup [ i ] = vstup [ i + mezera ] ; vstup [ i + mezera ] = t ; zaměněno = pravda ; } i ++ ; } } }

Implementace v PHP

function combsort ( $array ) { $sizeArray = count ( $array ); // Procházet všechny prvky pole pro ( $i = 0 ; $i < $sizeArray ; $i ++ ) { // Porovnejte ve dvojicích. // Začněte prvním a posledním prvkem, poté postupně snižujte // rozsah porovnávaných hodnot. for ( $j = 0 ; $j < $i + 1 ; $j ++ ) { // Index pravého prvku v aktuální iteraci porovnání $ elementRight = ( $sizeArray - 1 ) - ( $i - $j ); if ( $array [ $j ] > $array [ $elementRight ]) { $buff = $pole [ $j ]; $array [ $j ] = $array [ $elementRight ]; $array [ $elementRight ] = $buff ; unset ( $buff ); } } } return $array ; }

Implementace v Pythonu

z náhodného importu randint seznam_1 = [ randint ( 1 , 100 ) pro a v rozsahu ( 10 )] n = len ( seznam_1 ) krok = n while krok > 1 nebo q : pokud krok > 1 : krok -= 3 q , i = False , 0 while i + krok < n : if seznam_1 [ i ] > seznam_1 [ i + krok ]: seznam_1 [ i ], seznam_1 [ i + krok ] = seznam_1 [ i + krok ], seznam_1 [ i ] q = Pravda i += krok

Implementace v JavaScriptu

function joinSorting ( pole ) { var interval = Math . patro ( pole . délka / 1,3 ); while ( interval > 0 ) { for ( var i = 0 ; i + interval < pole . délka ; i ++ ) { if ( pole [ i ] > pole [ i + interval ]) { var small = pole [ i + interval ]; pole [ i + interval ] = pole [ i ]; pole [ i ] = malé ; } } interval = Matematika . patro ( interval / 1,3 ); } }

Implementace v C#

byte [] bytes = Soubor . ReadAllBytes ( "soubor.txt" ); ulong mezera = ( ulong ) bajtů . Délka ; bool prohozen = false ; while (( mezera > 1 ) || prohozena ) { mezera = ( ulong )( mezera / 1,2473309 ); if ( mezera < 1 ) mezera = 1 ; ulong i = 0 ; dlouhý m = mezera ; swapped = false ; while ( m < ( ulong ) bajtů . Délka ) { if ( bajtů [ i ] > bajtů [ m ]) { swapped = true ; byte t = bajty [ i ]; bajty [ i ] = bajty [ m ]; bajtů [ m ] = t ; } i ++; m = i + mezera ; } }

Poznámky

  1. ↑ Lacey S., Box R. A Fast, Easy Sort: Nové vylepšení dělá z bublinového třídění jednu z nejrychlejších třídicích  rutin  // Byte . - Duben 1991. - Sv. 16, č. 4 . - S. 315-320. — ISSN 0360-528 .
 Algoritmy řazení
Teorie Složitost O zápis Objednávkový vztah Seřadit typy udržitelného Vnitřní Externí
Výměna
Výběr
vložky
fúze
Žádné srovnání
hybridní
jiný
nepraktický