Kääpiöiden lajittelu

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 1.6.2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Gnome sort ( eng. Gnome sort ) on lajittelualgoritmi, joka muistuttaa lajittelua lisäysten mukaan , mutta toisin kuin jälkimmäinen, ennen oikeaan paikkaan lisäämistä tapahtuu sarja vaihtoja, kuten kuplalajittelussa . Nimi tulee puutarhatontujen oletetusta käytöksestä lajitellessaan puutarharuukkuja.

Kääpiöiden lajittelu perustuu yleisen hollantilaisen puutarhatontun ( hollantilainen tuinkabouter ) käyttämään tekniikkaan. Tämä on menetelmä, jolla puutarhatonttu lajittelee kukkaruukkuja. Pohjimmiltaan se tarkastelee nykyistä ja edellistä puutarharuukkua: jos ne ovat oikeassa järjestyksessä, se astuu yhden ruukun eteenpäin, muuten se vaihtaa ne ja astuu yhden ruukun taaksepäin. Rajaehdot: jos edellistä pottia ei ole, se astuu eteenpäin; jos seuraavaa pottia ei ole, hän on valmis.
Dick Grun

Algoritmi on käsitteellisesti yksinkertainen eikä vaadi sisäkkäisiä silmukoita. Työaika . Käytännössä algoritmi voi toimia yhtä nopeasti kuin lisäyslajittelu. $O\vasen(n^{2}\oikea)$

Algoritmi löytää ensimmäisen paikan, jossa kaksi vierekkäistä elementtiä ovat väärässä järjestyksessä, ja vaihtaa ne. Hän käyttää hyväkseen sitä, että vaihto voi tuottaa uuden parin väärässä järjestyksessä juuri ennen tai jälkeen vaihdettuja elementtejä. Se ei salli nykyisen sijainnin jälkeisten elementtien lajittelua, joten täytyy vain tarkistaa sijainti ennen uudelleen järjestettyjä elementtejä.

Kuvaus

Alla on lajittelun pseudokoodi . Tämä on optimoitu versio, joka käyttää j -muuttujaa , jotta voit siirtyä eteenpäin siihen, mihin se jäi ennen vasemmalle siirtymistä, välttäen turhat iteraatiot ja vertailut:

gnomeSort(a[0..koko - 1]) i = 1; j = 2; kun minä < koko jos a[i - 1] > a[i] //lajitellaksesi nousevaan järjestykseen, vaihda vertailumerkki muotoon < i = j; j = j + 1; muu vaihda a[i - 1] ja a[i] i = i - 1; jos i == 0 i = j; j = j + 1;

Esimerkki:

Jos haluamme lajitella taulukon, jossa on elementtejä [4] [2] [7] [3], suurimmasta pienimpään, while-silmukan iteraatioiden aikana tapahtuu seuraavaa:

[4] [2] [7] [3] (alkutila: i == 1, j == 2);
[4] [2] [7] [3] (mitään ei tapahtunut, mutta nyt i == 2, j == 3);
[4] [7] [2] [3] (vaihda a[2] ja a[1], nyt i == 1 ja j == 3 still);
[7] [4] [2] [3] (vaihda a[1] ja a[0], nyt i == 3, j == 4);
[7] [4] [3] [2] (vaihda a[3] ja a[2], nyt i == 2, j == 4);
[7] [4] [3] [2] (mitään ei tapahtunut, mutta nyt i == 4, j == 5);
sykli on ohi, koska en ole < 4.

Optimointi

Gnome-optimoinnin seurauksena lajittelu muuttuu luonnollisesti lisäyslajitteluksi . Joka kerta kun "gnome" osuu uuteen numeroon, kaikki "gnome" -kohdan vasemmalla puolella olevat arvot on jo lajiteltu.

Linkit

Menetelmän kuvaus ja listaus gnome-lajitteluohjelmista .

Lajittelualgoritmit
Teoria	Monimutkaisuus O merkintä Tilaussuhde Lajittele tyypit kestävää Sisäinen Ulkoinen
Vaihto	kupla Sekoitetaan Kääpiöt Nopeasti Kampa Lajittelu parillinen-pariton Bitittain
Valinta	Valinta Pyramidin muotoinen Sileä
insertit	insertit shella puu
fuusio	fuusio
Ei vertailuja	Laskenta lohko
hybridi	introsort Timsort
Muut	Topologinen verkkoja bitonia
epäkäytännöllistä	Bogosort Stooge lajittelu pannukakku hidas