Dvärgsortering
Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 1 juni 2021; verifiering kräver 1 redigering .Gnome sort ( eng. Gnome sort ) är en sorteringsalgoritm som liknar sortering efter inserts , men till skillnad från den senare, innan den sätts in på rätt plats, sker en serie utbyten, som i bubble sort . Namnet kommer från det förmodade beteendet hos trädgårdstomtar när de sorterar en rad trädgårdskrukor.
Dvärgsortering bygger på den teknik som används av den vanliga holländska trädgårdstomten ( holländska tuinkabouter ). Detta är metoden som en trädgårdstomte sorterar en rad med blomkrukor. I huvudsak tittar den på nuvarande och tidigare trädgårdskrukor: om de är i rätt ordning, kliver den fram en kruka, annars byter den dem och kliver tillbaka en kruka. Gränsvillkor: om det inte finns någon tidigare pott, kliver den framåt; om det inte finns någon nästa pott är han klar.
Dick Grun
Algoritmen är konceptuellt enkel och kräver inga kapslade loopar. Arbetstid . I praktiken kan algoritmen köras lika snabbt som infogningssortering.
Algoritmen hittar den första platsen där två angränsande element är i fel ordning och byter ut dem. Han utnyttjar det faktum att ett utbyte kan producera ett nytt par i fel ordning precis före eller efter de utbytta elementen. Det tillåter inte att element efter den aktuella positionen sorteras, så man behöver bara kontrollera positionen före de omarrangerade elementen.
Beskrivning
Nedan finns sorteringspseudokoden . Detta är en optimerad version som använder variabeln j för att tillåta att hoppa framåt till där den slutade innan den flyttas till vänster, för att undvika onödiga iterationer och jämförelser:
Exempel:
Om vi vill sortera en array med element [4] [2] [7] [3] från största till minsta, kommer följande att hända under iterationer av while-slingan:
- [4] [2] [7] [3] (initialtillstånd: i == 1, j == 2);
- [4] [2] [7] [3] (ingenting hände, men nu är i == 2, j == 3);
- [4] [7] [2] [3] (byt a[2] och a[1], nu är i == 1 och j == 3 fortfarande);
- [7] [4] [2] [3] (byte a[1] och a[0], nu i == 3, j == 4);
- [7] [4] [3] [2] (byte a[3] och a[2], nu i == 2, j == 4);
- [7] [4] [3] [2] (ingenting hände, men nu är i == 4, j == 5);
- cykeln är över eftersom jag inte är < 4.
Optimering
Som ett resultat av gnome-optimeringen förvandlas sortering naturligt till insättningssortering . Varje gång "gnome" träffar ett nytt nummer, är alla värden till vänster om "gnome" redan sorterade.
Länkar
- Metodbeskrivning och listning av gnomesorteringsprogram .
| Sorteringsalgoritmer | |
|---|---|
| Teori | Komplexitet O notation Orderförhållande Sorteringstyper hållbar Inre Extern |
| Utbyta | |
| Val | |
| Insatser | |
| fusion | |
| Inga jämförelser | |
| hybrid | |
| Övrig | |
| opraktisk | |