Cüce Sıralaması

Bir araştırma yaparken rastladım bu "cüce"ye ve hemen not aldım. Soyadımı taşıyan bu sıralama algoritması beni pek bi cezbetti.

Bakalım wikipedia ne demiş:

Cüce sıralaması (Gnome sort), bilgisayar bilimlerinde kullanılan araya sokmalı sıralamaya benzer bir sıralama algoritmasıdır. Ara sokmalı sıralamadan farkı kabarcık sıralaması yönteminde olduğu gibi, bir elemanın sıralanan dizideki yerine birçok yer değiştirme yoluyla gelmesidir. Cüce Sıralaması adı algoritmanın yönteminin mitolojideki Hollanda cücelerinin (gnome) bir dizi çiçek saksısını sıraya diziş biçimine benzemesinden kaynaklanmaktadır.

Pseudocode:
function gnomeSort(a[0..size-1]) {
i := 1
j := 2
while i < size - 1
if a[i-1] >= a[i]
i := j
j := j + 1
else
swap a[i-1] and a[i]
i := i - 1
if i = 0
i := 1
}

Aslında bahçıvan mantığı şu: Önceki ve sonraki çiçek saksısına bakar; eğer doğru sıradalar ise bir saksı ileriye adım atar, doğru sırada değillerse saksıları yer değiştirir ve bir saksı geriye adım atar. Sınır değerleri için: Eğer bir geride saksı yoksa ileri adım atar; eğer bir ileride saksı yoksa iş bitmiştir.

Karmaşıklık en iyi O(n) , en kötü durumda O(n^2)

C Kodu:
#include<stdio.h>

void gnomesort(int , int []);

void main(){

int ar[4]={5,3,2,4};

gnomesort(4,ar) ;

}

void gnomesort(int n, int ar[]) {
int i = 0;

while (i < n) {
if (i == 0 || ar[i-1] <= ar[i])
i++;
else {
int tmp = ar[i];
ar[i] = ar[i-1];
ar[--i] = tmp;
}
}

for(i=0;i<n;i++)
printf("%d\n",ar[i]);
}


Örnek:
Sıralı olmayan bir dizi verilsin, a = [5, 3, 2, 4], Cüce sıralaması “while” döngüsü boyunca aşağıdaki adımları gerçekleyecektir. “Geçerli konum” kalın gösterilmiştir:

Geçerli dizi Yapılan işlemler
[5, 3, 2, 4], konum == 0, arttır konum:
[5, 3, 2, 4], a[konum] < a[konum-1] , yer değiştir ve azalt konum:
[3, 5, 2, 4], konum == 0, arttır konum:
[3, 5, 2, 4], a[konum] > a[konum-1], arttır konum:
[3, 5, 2, 4], a[konum] < a[konum-1] , yer değiştir ve azalt konum:
[3, 2, 5, 4], a[konum] < a[konum-1] , yer değiştir ve azalt konum:
[2, 3, 5, 4], konum == 0, arttır konum:
[2, 3, 5, 4], a[konum] > a[konum-1], arttır konum:
[2, 3, 5, 4], a[konum] > a[konum-1], arttır konum:
[2, 3, 5, 4], a[konum] < a[konum-1] , yer değiştir ve azalt konum:
[2, 3, 4, 5], a[konum] > a[konum-1], arttır konum:
[2, 3, 4, 5], a[konum] > a[konum-1], arttır konum:
[2, 3, 4, 5], konum == uzunluk(a), bitti.

Hemen hemen tüm programlama dillerinde yazılmış Gnome sort: buradan


kaynak : 1 , 2 , 3 , 4