Kertitörpe-rendezés

A Wikipédiából, a szabad enciklopédiából
Kertitörpe-rendezés vizualizációja

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;[1] á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.[2]

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(n2), de O(n)-hez közelít, ha az elemek már közel sorrendben vannak, azaz a sorozat „majdnem” rendezett.[3]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

  1. Sarbazi-Azad, Hamid (2000. október 2.). „Stupid Sort: A new sorting algorithm”. Newsletter (599), 4. o, Kiadó: Computing Science Department, Univ. of Glasgow. Hozzáférés ideje: 2014. november 25.  
  2. http://www.dickgrune.com/Programs/gnomesort.html
  3. Paul E. Black: gnome sort. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. (Hozzáférés: 2011. augusztus 20.)

Források[szerkesztés | forrásszöveg szerkesztése]

További információk[szerkesztés | forrásszöveg szerkesztése]

Kapcsolódó szócikkek[szerkesztés | forrásszöveg szerkesztése]