Sortarea piticilor

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 1 iunie 2021; verificarea necesită 1 editare .

Gnome sort ( ing.  Gnome sort ) este un algoritm de sortare asemănător sortării după inserții , dar spre deosebire de acesta din urmă, înainte de introducerea în locul potrivit, au loc o serie de schimburi, ca în bubble sort . Numele provine de la presupusul comportament al gnomilor de grădină atunci când sortează o linie de ghivece de grădină.

Sortarea piticilor se bazează pe tehnica folosită de gnomul de grădină olandez comun ( Dutch  tuinkabouter ). Aceasta este metoda prin care un gnom de grădină sortează o linie de ghivece de flori. În esență, se uită la ghivecele de grădină actuale și anterioare: dacă sunt în ordinea corectă, face un pas înainte cu un ghiveci, în caz contrar le schimbă și dă un pas înapoi. Condiții limită: dacă nu există o oală anterioară, face un pas înainte; dacă nu există următoarea oală, el este terminat.
Dick Grun

Algoritmul este conceptual simplu și nu necesită bucle imbricate. Timp de lucru . În practică, algoritmul poate rula la fel de rapid ca sortarea prin inserare.

Algoritmul găsește primul loc în care două elemente învecinate sunt în ordinea greșită și le schimbă. El profită de faptul că un schimb poate produce o nouă pereche în ordinea greșită chiar înainte sau după elementele schimbate. Nu permite sortarea elementelor după poziția curentă, așa că trebuie doar să verificați poziția înaintea elementelor rearanjate.

Descriere

Mai jos este pseudocodul de sortare . Aceasta este o versiune optimizată care utilizează variabila j pentru a permite săriți înainte de unde a rămas înainte de a vă deplasa la stânga, evitând iterațiile și comparațiile inutile:

gnomeSort(a[0..size - 1]) i = 1; j = 2; în timp ce i < dimensiune dacă a[i - 1] > a[i] //pentru a sorta în ordine crescătoare, schimbați semnul de comparație în < i = j; j = j + 1; altfel schimbați a[i - 1] și a[i] i = i - 1; dacă i == 0 i = j; j = j + 1;

Exemplu:

Dacă vrem să sortăm o matrice cu elemente [4] [2] [7] [3] de la cel mai mare la cel mai mic, atunci se va întâmpla următoarele în timpul iterațiilor buclei while:

• [4] [2] [7] [3] (starea inițială: i == 1, j == 2);
• [4] [2] [7] [3] (nu s-a întâmplat nimic, dar acum i == 2, j == 3);
• [4] [7] [2] [3] (schimbați a[2] și a[1], acum i == 1 și j == 3 încă);
• [7] [4] [2] [3] (schimbă a[1] și a[0], acum i == 3, j == 4);
• [7] [4] [3] [2] (schimbă a[3] și a[2], acum i == 2, j == 4);
• [7] [4] [3] [2] (nu s-a întâmplat nimic, dar acum i == 4, j == 5);
• ciclul s-a încheiat pentru că i nu este < 4.

Optimizare

Ca rezultat al optimizării gnome, sortarea se transformă în mod natural în sortarea prin inserție . De fiecare dată când „gnome” atinge un număr nou, toate valorile din stânga „gnome” sunt deja sortate.

Link -uri

• Descrierea metodei și listarea programelor de sortare gnome .

Algoritmi de sortare
Teorie	Complexitate O notație Relația de comandă Sortați tipuri durabil Intern Extern
schimb valutar	bule Agitând Piticii Rapid Pieptene Sortare par-impar Pe bit
Alegere	Alegere Piramidal Neted
inserții	inserții shella copac
fuziune	fuziune
Fara comparatii	Socoteală bloc
hibrid	introsort Timsort
Alte	Topologic retelelor biton
nepractic	Bogosort Soiul de ciudăţeni clătită încet