10.4 Sıralama (Sorting)
10.4 Sıralama (Sorting)
Bazı uygulamalarda bir grup sayının büyükten küçüğe, veya küçükten büyüğe, doğru sıralanması gerekebilir. Bu tip sıralama problemleri için çeşitli algoritmalar geliştirilmiştir. Sıralama mantığını anlamadan önce bir dizinin en büyük (veya en küçük) elemanının nasıl bulunduğunu inceleyelim. Program 10.3, bir dizinin en büyük elemanını bulup ekrana yazar.
Program 10.3: Bir dizinin en büyük elemanının bulunuşu
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
/* 10prg03.c Bir dizinin en büyük elemanını bulup ekrana yazar */ #include <stdio.h> int main(void) { int a[10] = {100, -250, 400, 125 ,550, 900, 689, 450, 347, 700}; int k, eb; /* ilk eleman en büyük kabul ediliyor */ eb = a[0]; for(k=1; k<10; k++) if( a[k]>eb ) eb = a[k]; printf("En buyuk eleman = %d\n",eb); return 0; } |
ÇIKTI
|
1 |
En buyuk eleman = 900 |
En büyük sayıyı bulan bu algoritma oldukça kolaydır. 12. satırda eb = a[0]; ataması ile dizinin ilk elemanının en büyük olduğu varsayılır. Daha sonra büyüğe rastladıkça (15. satır) eb = a[k]; ile eb değişmektedir.
Program 10.3 bir dizinin en büyük elemanını bulur. En büyük elemanın kaçıncı indis (eleman) olduğu sorgulanmak istendiğinde: programdaki koşul yapısını aşağıdaki gibi değiştirmek yeterlidir. eb değiştikçe, i değişkeni en büyük elemanın indisini tutar.
|
1 2 3 4 5 6 |
for(k=0; k<10; k++){ if( a[k] > eb ){ eb = a[k]; i = k; } } |
n elemanlı bir dizinin, elemanlarını büyükten küçüğe doğru sıralamak için çok popüler iki algoritma aşağıda verilmiştir[2].
Seçerek Sıralama (Selection Sort):
En büyük elemanı bul başa koy biçimindeki sıramadır. Algoritmanın uygulaması Program 10.4’de gösterilmiştir.
Bu algoritmada kullanılan kombinasyon sayısı (algoritmanın karmaşıklığı): n*(n-1)/2 dir.
Program 10.4: Seçerek Sıralama (Selection Sort) Algoritması
|
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
/* 09prg04.c Seçerek Sıralama (Selection Sort) Algoritması ile bir dizinin elemanlarını büyükten küçüğe dogru sıralar */ #include <stdio.h> #define n 10 int main(void) { int a[n] = {100, -250, 400, 125 ,550, 900, 689, 450, 347, 700}; int i, j, k, eb; /* Dizinin kendisi */ printf("Once : "); for(k=0;k<n;k++) printf("%5d ",a[k]); /* Sırala */ for(k=0; k<n; k++){ eb = a[k]; i = k; for(j=k+1; j<n; j++) if( a[j]>eb ){ eb = a[j]; i = j; } a[i] = a[k]; a[k] = eb; } /* Sıralama bitti */ printf("\nSonra: "); for(k=0; k<n; k++) printf("%5d ",a[k]); printf("\n"); return 0; } |
ÇIKTI
|
1 2 |
Once : 100 -250 400 125 550 900 689 450 347 700 Sonra: 900 700 689 550 450 400 347 125 100 -250 |
Kabarcık Sıralama (Bubble Sort):
Yanyana elemanları karşılaştırarak yer değiştir biçimde sıralamadır. Algoritmanın uygulaması Program 10.5’de gösterilmiştir.
Bu algoritmanın karmaşıklığı: (n-1)2 dir.
Program 10.5: Kabarcık Sıralama (Bubble Sort) Algoritması
|
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 27 28 29 30 31 32 33 34 35 36 |
/* 09prg05.c Kabarcık Sıralama (Bubble Sort) Algoritması ile bir dizinin elemanlarını büyükten küçüğe dogru sıralar */ #include <stdio.h> #define n 10 int main(void) { int a[n] = {100, -250, 400, 125 ,550, 900, 689, 450, 347, 700}; int j,k,gecici; /* Dizinin kendisi */ printf("Once : "); for(k=0; k<n; k++) printf("%5d ",a[k]); /* Sırala */ for(k=0; k<n-1; k++) for(j=0; j<n-1; j++) if( a[j]<a[j+1] ){ gecici = a[j]; a[j] = a[j+1]; a[j+1] = gecici; } /* Sıralama bitti */ printf("\nSonra: "); for(k=0; k<n; k++) printf("%5d ",a[k]); printf("\n"); return 0; } |
ÇIKTI
|
1 2 |
Once : 100 -250 400 125 550 900 689 450 347 700 Sonra: 900 700 689 550 450 400 347 125 100 -250 |
