Yazan : Şadi Evren ŞEKER

Bu yazının amacı, aptal sıralaması olarak bilinen (stupid sort) ve daha sonraları gnome sıralaması ismiyle anılan sıralama algoritmasını (sort algorithm) anlatmaktır. Algoritma 2000 yılında, Hamid Sarbazi-Azad tarafından bulunmuştur ve bir dizideki sayıları sıralama amacıyla, doğru aralığa taşımayı amaçlar.

Algoritma basitçe aşağıdaki şekilde anlatılabilir:

Yanyana duran ve sıralama kriterini bozan bir ikili bulana kadar dizide hareket edilir.

Bu ikili bulununca düzeltilir ve dengeye ulaşana kadar gerekirse dizinin başına kadar geri dönülür.

Ardından işlem kaldığı yerden devam eder.

Şimdi bu adımların örnek bir dizi üzerinde nasıl uygulandığını görelim.

Örneğin sıralamak istediğimiz dizi aşağıdaki şekilde olsun:

2 6 8 1 3 7 4 9 0 5

Sol baştan başlayarak yanlış duran, yanyana iki sayı arıyoruz.

2 6 8 1 3 7 4 9 0 5

2,6 doğru

2 6 8 1 3 7 4 9 0 5

6,8 doğru

2 6 8 1 3 7 4 9 0 5

8,1 hatalı (büyük sayı sağda olmalı) Yer değitşirilir ve gelinen en son nokta olan 3. eleman akılda tutulur:

3 <-> 2

2 6 1 8 3 7 4 9 0 5

kararlı olan kadar tekrar kontrol edilir.

2 6 1 8 3 7 4 9 0 5

6,1 hatalı değiştirilir:

2 <-> 1

2 1 6 8 3 7 4 9 0 5

2,1 hatalı değiştirilir:

1 <-> 0

1 2 6 8 3 7 4 9 0 5

dizide kalıdığımız yerden devam ediyoruz. En son 3. elemana kadar ilerlemiştik buradan devam edelim:

8,3 hatalı değiştirilir ve 4. elemana kadar gelindiği akılda tutulur.:

4 <-> 3

1 2 6 8 3 7 4 9 0 5

6,3 hatalı değiştirilir

1 2 6 3 8 7 4 9 0 5

3 <-> 2

1 2 3 6 8 7 4 9 0 5

Kalınan yerden devam edilir:

1 2 3 6 8 7 4 9 0 5

8,7 hatalı değiştirilir ve 5. eleman kalınan yer olarak saklanır:

5 <-> 4

1 2 3 6 7 8 4 9 0 5

Hatasız kalınan yerden devam edilir:

1 2 3 6 7 8 4 9 0 5

8,4 hatalı değiştirilir:

6 <-> 5

1 2 3 6 7 4 8 9 0 5

7,4 hatalı değiştirilir:

5 <-> 4

1 2 3 6 4 7 8 9 0 5

6,4 hatalı, değiştirilir:

4 <-> 3

1 2 3 4 6 7 8 9 0 5

Kalınan yerden devam edilir:

1 2 3 4 6 7 8 9 0 5

Sorunsuz devam edilir:

1 2 3 4 6 7 8 9 0 5

9,0 hatalı değiştirilir:

8 <-> 7

1 2 3 4 6 7 8 0 9 5

7 <-> 6

1 2 3 4 6 7 0 8 9 5

6 <-> 5

1 2 3 4 6 0 7 8 9 5

5 <-> 4

1 2 3 4 0 6 7 8 9 5

4 <-> 3

1 2 3 0 4 6 7 8 9 5

3 <-> 2

1 2 0 3 4 6 7 8 9 5

2 <-> 1

1 0 2 3 4 6 7 8 9 5

1 <-> 0

0 1 2 3 4 6 7 8 9 5

Kalınan yerden devam edilir:

0 1 2 3 4 6 7 8 9 5

9,5 Hatalı yer değiştirilir:

9 <-> 8

0 1 2 3 4 6 7 8 5 9

8 <-> 7

0 1 2 3 4 6 7 5 8 9

7 <-> 6

0 1 2 3 4 6 5 7 8 9

6 <-> 5

0 1 2 3 4 5 6 7 8 9

Görüldüğü üzere dizinin son elemanına kadar ulaşılmış ve dizi sıralanmıştır. Bu algoritmanın kodu aşağıdaki şekilde yazılabilir:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
void gnomesort(int *a, int size){
   int i = 1;
   while(i < size){
       if(a[i] >= a[i-1])
           i++;
       else{
                int gecici = a[i];
                a[i] = a[i-1];
                a[i-1] = gecici;
                printf(" %d <-> %dn",i,i-1);
                if( i > 1)
                        i--;
                else
                        i++;
        }
        for(int j=0;j<size;j++)
                printf("%d ",a[j]);
        printf("n");
   }
}
int main(){
        int a[10] = {2,6,8,1,3,7,4,9,0,5};
        gnomesort (a,10);
        return 0;
}

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


sekiz − = 0