Hřeben třídění - Comb sort

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Hřebenové třídění“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Březen 2011) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Hřeben třídění

Hřeben třídění s faktorem zmenšení k=1.24733
Třída	Algoritmus řazení
Datová struktura	Pole
Nejhorší případ výkon	${ displaystyle O (n ^ {2})}$[1]
Nejlepší případ výkon	${ displaystyle Theta (n log n)}$
Průměrný výkon	${ displaystyle Omega (n ^ {2} / 2 ^ {p})}$, kde str je počet přírůstků[1]
Nejhorší případ složitost prostoru	${ displaystyle O (1)}$

Hřeben třídění je poměrně jednoduchý třídicí algoritmus původně navrhli Włodzimierz Dobosiewicz a Artur Borowy v roce 1980,^[1][2] později znovuobjevený Stephen Lacey a Richard Box v roce 1991.^[3] Vyčesávání se zlepšuje třídění bublin.

Algoritmus

Základní myšlenkou je eliminovat želvy, nebo malé hodnoty na konci seznamu, protože v třídění podle bublin tyto třídění ohromně zpomalují. Králíci, velké hodnoty na začátku seznamu, nepředstavují problém při třídění bublin.

v třídění bublin, když jsou porovnány jakékoli dva prvky, vždy mají 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. Vnitřní smyčka třídění bublin, která vyměnit, je upraven tak, že mezera mezi vyměněnými prvky klesá (pro každou iteraci vnější smyčky) v krocích „zmenšovacího faktoru“ k: [ n/k, n/k², n/k³, ..., 1 ].

Mezera začíná jako délka seznamu n řazeno děleno zmenšovacím faktorem k (obecně 1,3; viz níže) a jeden průchod výše zmíněného upraveného druhu bublin se použije s touto mezerou. Potom je mezera znovu rozdělena faktorem zmenšení, seznam je seřazen podle této nové mezery a proces se opakuje, dokud není mezera 1. V tomto okamžiku pokračuje hřebenové třídění s použitím mezery 1, dokud není seznam plně tříděn. Konečná fáze třídění je tedy ekvivalentní třídění bublin, ale do této doby byla většina želv řešena, takže třídění bublin bude efektivní.

Faktor zmenšení má velký vliv na účinnost třídění hřebenů. k = 1,3 navrhli autoři původního článku jako ideální faktor zmenšení po empirickém testování na více než 200 000 náhodných seznamech. Hodnota příliš malá zpomaluje algoritmus tím, že dělá zbytečně mnoho srovnání, zatímco hodnota příliš velká nedokáže účinně řešit želvy, což vyžaduje mnoho průchodů s velikostí mezery 1.

Vzor opakovaných průchodů třídění se zmenšujícími se mezerami je podobný Shellsort, ale v Shellsortu je pole tříděno úplně každý průchod, než přejde na další nejmenší mezeru. Průběhy hřebenového třídění prvky úplně netřídí. To je důvod, proč Sekvence mezer Shellsort mají větší optimální faktor smrštění asi 2,2.

Pseudo kód

funkce kombinovat (pole vstup) je    gap: = input.size // Inicializuje velikost mezery    zmenšit: = 1.3 // Nastavte faktor zmenšení mezery    seřazeno: = false smyčka zatímco seřazeno = false // Aktualizujte hodnotu mezery pro další hřeben        mezera: = podlaha (mezera / zmenšení) -li mezera ≤ 1 pak            mezera: = 1 seřazeno: = true // Pokud neexistují žádné swapy, je toto povolení hotovo        skončit, pokud        // Jediný „hřeben“ nad vstupním seznamem        i: = 0 smyčka zatímco i + mezera  // Viz Třídění skořápky pro podobný nápad            -li vstup [i]> vstup [i + mezera] pak                vyměnit (vstup [i], vstup [i + mezera]) seřazeno: = false // Pokud k tomuto přiřazení ve smyčce nikdy nedojde, // pak nedošlo k žádným swapům a seznam je seřazen.             skončit, pokud                 i: = i + 1 koncová smyčka     koncová smyčkakoncová funkce

Pythonský kód

Navíc dvě rychlé implementace Pythonu: jedna pracuje na seznamu (nebo poli nebo jiném proměnlivém typu, kde operace použité na něm dávají jazyku smysl) na místě, druhá vytváří seznam se stejnými hodnotami jako daná data a vrátí to po seřazení (podobně jako vestavěná funkce `seřazeno`).

def combsort_inplace(data):    délka = len(data)    zmenšit = 1.3    _mezera = délka    tříděny = Nepravdivé    zatímco ne tříděny:        # Python nemá vestavěnou funkci „floor“, takže my / já mám jen jednu proměnnou (_gap), kterou je třeba zmenšit,        # a celočíselná proměnná (mezera) pro uložení zkrácení (jiné proměnné) v a        # použít pro věci týkající se indexování        _mezera /= zmenšit        # gap = np.floor (_gap)        mezera = int(mezera)        -li mezera <= 1:            tříděny = Skutečný            mezera = 1        # ekvivalent k `i = 0; while (i + mezera)         pro i v rozsah(délka - mezera):            sm = mezera + i            -li data[i] > data[sm]:                # protože Python je velmi pěkný, tím je swap proveden                data[i], data[sm] = data[sm], data[i]                tříděny = Nepravdivédef kombinovat(data):    délka = len(data)    zmenšit = 1.3    _mezera = délka    ven = seznam(data)    tříděny = Nepravdivé    zatímco ne tříděny:        _mezera /= zmenšit        mezera = int(_mezera)        -li mezera <= 1:            tříděny = Skutečný            mezera = 1        pro i v rozsah(délka - mezera):            sm = mezera + i            -li ven[i] > ven[sm]:                ven[i], ven[sm] = ven[sm], ven[i]                tříděny = Nepravdivé    vrátit se ven

Viz také

• Třídění bublin, obecně pomalejší algoritmus, je základem hřebenového třídění.
• Koktejl, nebo obousměrné třídění bublin, je variace třídění bublin, která také řeší problém želv, i když méně efektivně.

Reference