Trpasličí 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é 1. června 2021; ověření vyžaduje 1 úpravu .

Gnome sort ( angl. Gnome sort ) je třídicí algoritmus podobný třídění podle insertů , ale na rozdíl od toho druhého před vložením na správné místo dojde k řadě výměn, jako je tomu u bublinového třídění . Název pochází z domnělého chování zahradních trpaslíků při třídění řady zahradních květináčů.

Třídění trpaslíků je založeno na technice, kterou používá běžný holandský zahradní trpaslík ( holandský tuinkabouter ). To je metoda, kterou zahradní trpaslík třídí řadu květináčů. V podstatě se dívá na současné a předchozí zahradní květináče: pokud jsou ve správném pořadí, postoupí o jeden květináč vpřed, jinak je vymění a ustoupí o jeden květináč dozadu. Okrajové podmínky: pokud neexistuje žádný předchozí bank, postupuje vpřed; pokud není další hrnec, je hotový.
Dick Grun

Algoritmus je koncepčně jednoduchý a nevyžaduje vnořené smyčky. Pracovní doba . V praxi může algoritmus běžet stejně rychle jako vkládání. $O\left(n^{2}\vpravo)$

Algoritmus najde první místo, kde jsou dva sousední prvky ve špatném pořadí, a prohodí je. Využívá toho, že výměna může vytvořit nový pár ve špatném pořadí těsně před nebo po prohozených prvcích. Neumožňuje seřadit prvky za aktuální pozicí, takže stačí zkontrolovat pozici před přeskupenými prvky.

Popis

Níže je pseudokód řazení . Toto je optimalizovaná verze využívající proměnnou j , která umožňuje skočit dopředu tam, kde přestala, než se přesunete doleva, čímž se vyhnete zbytečným iteracím a porovnáváním:

gnomeSort(a[0..velikost - 1]) i = 1; j = 2; zatímco já < velikost pokud a[i - 1] > a[i] //chcete-li seřadit vzestupně, změňte znak porovnání na < i = j; j = j + 1; jiný vyměnit a[i - 1] a a[i] i = i - 1; pokud i == 0 i = j; j = j + 1;

Příklad:

Pokud chceme seřadit pole s prvky [4] [2] [7] [3] od největšího po nejmenší, pak se během iterací cyklu while stane následující:

[4] [2] [7] [3] (počáteční stav: i == 1, j == 2);
[4] [2] [7] [3] (nic se nestalo, ale teď i == 2, j == 3);
[4] [7] [2] [3] (prohoďte a[2] a a[1], nyní i == 1 a j == 3 stále);
[7] [4] [2] [3] (výměna a[1] a a[0], nyní i == 3, j == 4);
[7] [4] [3] [2] (výměna a[3] a a[2], nyní i == 2, j == 4);
[7] [4] [3] [2] (nic se nestalo, ale teď i == 4, j == 5);
cyklus je u konce, protože i není < 4.

Optimalizace

V důsledku optimalizace gnome se řazení přirozeně transformuje na řazení vložení . Pokaždé, když "gnome" zasáhne nové číslo, všechny hodnoty nalevo od "gnome" jsou již seřazeny.

Odkazy

Popis metod a seznam programů pro třídění gnome .

Algoritmy řazení
Teorie	Složitost O zápis Objednávkový vztah Seřadit typy udržitelného Vnitřní Externí
Výměna	bublina Míchání Trpaslíci Rychle Hřeben Řazení sudé-liché bitový
Výběr	Výběr Pyramidový Hladký
vložky	vložky shella strom
fúze	fúze
Žádné srovnání	Počítací blok
hybridní	introsort Timsort
jiný	Topologické sítí biton
nepraktický	Bogosort Stooge řazení lívanec pomalý