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.http://www.dickgrune.com/Programs/gnomesort.html

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; }

Jegyzetek

Források

További információk Kapcsolódó szócikkek

Kategória:Rendezési algoritmusok