|
|
|
Klasik sıralama(sorting) algoritmaları - 1 |
|
| Gönderiliyor lütfen bekleyin... |
|
|
Bu makalemizde en
temel ve en basit sıralama algoritmalarından Insertion Sort, Selection Sort ve
Shell Sort algoritmalarını öğreneceğiz. Bildiğiniz gibi bilgisayar sistemlerinin ve
programlama tarihinin en başından beri sıralama algoritmaları her zaman önemli olmuştur.
Bir çok önemli algoritmada sıralama algoritmaları kullanılır. Peki bilgisayar
sıralama işlemini nasıl yapar. Mesela bir insana verilen üzerinde harfler
bulunan karışık kartların sıralamasını istediğimizde önce rastgele bir kart
alır.Sonra bir kart daha alır, sonra aldığı kartı ile ilk aldığı kartı karşılaştırır
ve kartı uygun yere koyar. Bütün kartları bu şekilde yaptıktan sonra
sıralama işlemi tamamlanır. Bilgisayar sistemleride genelde sıralama yaparken insanların
yaptığı gibi karşılaştırma yapar. Bu makalede göreceğimiz algoritmalar genelde
yavaş çalışan algoritmalardır.Bunların yanında Merge Sort, Quick Sort ve
Heap Sort gibi diğer hızlı algoritmalar da vardır. Ancak bazı hızlı algoritmaların
da başka dezavantajları vardır. Bir başka makalede bu hızlı algoritmaların üzerinde
duracağız. Şimdi ilk algoritmamız olan Insertion Sort algoritmasına bakalım.
Insertion
Sort(sıralama)
Bu algoritma insanların
sıralama mantığına en yakın olan algoritmadır. Sıralanacak dizi sıralanmış ve
sıralanmamış parçalara ayrılarak her bir eleman sıralanmış parça içinden kontrol
edilerek uygun yere yerleştirilir. Grafiksel olarak Insertion algoritmasını
aşağıdaki aşamalar şeklinde ifade edebiliriz.
Insertion Sort algoritması
aşağıdaki gibidir. N sıralanacak dizinin eleman sayısını, ilk parametre ise
sıralanacak dizinin adresini gösteriyor.
void InsertionSort(int *Dizi, int N){
int i, j,m ;
for (i=1 ; i < N ; ++i){
if (dizi[i]
< dizi[i-1]){
m=
dizi[i];
for(j=i
; j && m < dizi[j-1] ; j--)
dizi[j]
= dizi[j-1];
dizi[j]
= m;
}
}
}
Selection
Sort(sıralama)
Bu algoritma birinci
elemandan başlayarak son elemana kadar sıralanmış parçayı artırarak işler. Önce
dizideki en küçük eleman bulunur ve dizinin ilk elemanı ile yer değiştirilir.
Sonraki aşamada sıralanmamış parça içindeki en küçük eleman bulunur ve ikinci
elemanla yer değiştirilir. Bu işlemi N defa N eleman için yaptığımızda dizi
sıralanmış olacaktır.Grafiksel olarak Selection Sort algoritmasını aşağıdaki
aşamalar şeklinde ifade edebiliriz.
Selection Sort algoritması
aşağıdaki gibidir. N sıralanacak dizinin eleman sayısını, ilk parametre ise sıralanacak
dizinin adresini gösteriyor.
void
SelectionSort(int *Dizi, int N){
int i, j,min ;
for (i=0 ; i < N ; i++){
min
= i ;
for(j
= i+1 ; j < N ; j++){
if
(dizi[i] < dizi[min])
min=j;
}
değiştir(dizi[i]
, dizi[min]); // i. ve min. elemanı yer değiştirecek fonksiyon.Bunu yazmayı
da size bırakıyorum.
}
}
Shell
Sort(sıralama)
Shell sort algoritması
Insertion algoritmasına benzer ancak bu algoritma daha hızlıdır.Çünkü sıralama
işlemini bütün dizi üzerinde değilde diziyi guruplara bölerek yapar.Insertion
sort metodunu dizinin belli bölümlerine uyguladığımızda Shell sort algoritmasını
elde ederiz.Grafiksel olarak Shell Sort algoritmasını aşağıdaki aşamalar şeklinde
ifade edebiliriz.
Shell Sort algoritması
aşağıdaki gibidir. N sıralanacak dizinin eleman sayısını, ilk parametre ise
sıralanacak dizinin adresini gösteriyor.
void
ShellSort(int * dizi , int N)
{
int i,j,h,temp;
for(h=1 ; h <= N/9 ; h=3*h+1)
;
while(h){
for(i=h ; i<N ; i +=1){
temp=dizi[i];
for(j=i ; j > h-1 &&
temp < dizi[j-h] ; j -= h)
dizi[j]=dizi[j-h];
dizi[j]=temp;
}
h /=3;
}
}
Daha
sonraki yazılarımızda diğer önemli sıralama algoritmalarını göreceğiz.
Makale:
Klasik sıralama(sorting) algoritmaları - 1 C ve Sistem Programlama Sefer Algan
|
|
|
|
|
-
-
Eklenen Son 10
-
Bu Konuda Geçmiş 10
Bu Konuda Yazılmış Yazılmış 10 Makale Yükleniyor
Son Eklenen 10 Makale Yükleniyor
Bu Konuda Yazılmış Geçmiş Makaleler Yükleniyor
|
|
|