Kertitörpe-rendezés

Kertitörpe-rendezés
Kertitörpe-rendezés vizualizációja
Kategória	rendezési algoritmus
Adatstruktúra	tömb
Legrosszabb időbonyolultság	$O(n^{2})$
Legjobb időbonyolultság	$\Omega (n)$
Átlagos idő bonyolultság	$O(n^{2})$
Legrosszabb tár bonyolultság	$O(1)$ kiegészítés
Optimális	nem

A kertitörpe-rendezés (angolul gnome sort) egy tömb elemeinek sorba rendezésére szolgáló algoritmus. Az algoritmust először Dr. Hamid Sarbazi-Azad, a Sharif University of Technology Számítástechnikai tanszékének professzora publikálta 2000-ben, és ő nevezte el „buta rendezés”-nek; ám ezt később Dick Grune keresztelte el „kertitörpe-rendezésnek”, mivel az algoritmus menete őt arra emlékeztette, ahogy egy kerti törpe rendezné a virágcserepek egy sorát.

Hasonlít a beszúrásos rendezésre, azonban az elemek a buborékrendezésre emlékeztető módon, sorozatos cserék után kerülnek a helyükre. Elve egyszerű, nem használ beágyazott ciklusokat. Várható végrehajtási ideje O(n²), de O(n)-hez közelít, ha az elemek már közel sorrendben vannak, azaz a sorozat „majdnem” rendezett.

Az algoritmus megkeresi az első olyan helyet, ahol két egymást követő elem rossz sorrendben van, és megcseréli őket. Ha egy ilyen csere után rossz sorrend keletkezik, az csak közvetlenül a legutolsó csere előtt lehet, így ezt is ellenőrizzük. Csere után ismét ellenőrzés következik, ezért a cserék addig folytatódnak, amíg az elem a megfelelő helyre nem kerül.

Példakód

Egy C-nyelven írt példakód:

#include <stdio.h>  // printf, ...
#include <stdlib.h> // malloc, free, rand, ...
#include <time.h>   // time, ...

const int N = 10; // tömb elemszáma (teszteléshez!)
const int maxNumber = 100; // legnagyobb lehetséges szám (teszteléshez!)

// array -> mutató a tömbre
// n -> tömb elemszáma
void gnome_sort( int *array, int n ) {
    int i = 0;
    while(i < n-1) {
        if( array[i] <= array[i+1] ) i++;  // ha jó a sorrend: index növelése
        else {
            int tmp = array[i];	   // i. és i+1. elem cseréje
            array[i] = array[i+1];
            array[i+1] = tmp;

            if(--i < 0) i = 0;     // index csökkentése
        }
    }
}

int main(void) {
    int i;

    srand(time(NULL));

    int *a = (int*)malloc(sizeof(int) * N); // hely foglalása a tömbhöz
    if(a == NULL) { // egy kis hibakezelés
        perror("Memory error");
        return 1;
    }

    // feltöltjük a tömböt véletlenszerű elemekkel
    for(i = 0; i < N; i++) {
        a[i] = rand()%maxNumber;
    }

    // rendezzük
    gnome_sort(a, N);

    // kiíratjuk
    for(i = 0; i < N; i++) printf("a[%d] = %d\n", i, a[i]);

    free(a); // lefoglalt terület felszabadítása
    return 0;
}

Források

• Kulik Csaba: Adatstruktúrák, algoritmusok, objektumok (AAO); Szemelvénygyűjtemény a 2005/2006-os anyagból Csink László és Miklós Árpád előadásai alapján (magyar nyelven) (pdf) pp. 26./90. BMF-NIK-AAO, 2007. január 16. [2016. március 10-i dátummal az eredetiből archiválva]. (Hozzáférés: 2014)
• Dick Grune: Gnome Sort - The Simplest Sort Algorithm (angol nyelven). Dick Grune, 2003. május 14. (Hozzáférés: 2014) „The simplest sort algorithm is not Bubble Sort..., it is not Insertion Sort..., it's Gnome Sort!”