gokhanca

Bilgisayar programlamada en çok kullanılan algoritmalardan biri de sıralama algoritmalarıdır. Burada, en sık kullanılan bazı sıralama algoritmaları anlatılmıştır.

1.YER DEĞİŞTİRME SIRALAMASI (EXCHANGE SORT)

Bir dizideki her bir indisi kendisinden sonraki indislerle sınar. Küçüklük veya büyüklük kuralına uygun karşılaştırma varsa indislerdeki veriler yer değiştirilir. Bu sıralamada aslında tüm indisler asimetrik olarak karşılaştırılmaktadır. Mesela; 3 elemanlı bir dizi için (1 ile 2) , (1 ile 3) ve (2 ile 3) karşılaştırılır ve yeterlidir. 5 elemanlı bir sıralama örneği aşağıda görülmektedir.

Yukarıdaki örnekte 5 elemanlı bir dizi sıralanmak istensin. Her elemanı en az şekilde ve tamamen birbiriyle eşleştirmek için yarım matris dizaynında olduğu gibi hareket edilir. Yani, 1.elemanı (2,3,4,5 ile) , 2.elemanı (3,4,5) ile , 3.elamanı (4,5) ile ve 4.elamanı (5) ile karşılaştırırız. Eğer karşılaştırma işleminde şart sağlanıyorsa karşılaştırılan iki veri yer değiştirilir.

'Yukarıdaki Örneğin Kodları
FOR i = 1 to 4
FOR j = i + 1 to 5
IF Dizi(i) < Dizi(j) THEN
' Değiştirme İşlemi Yapılır
END IF
NEXT
NEXT

N Elemanlı Liste İçin Genel Yazımı
FOR i = 1 to N - 1
FOR j = i + 1 to N
IF Dizi(i) < Dizi(j) THEN
'Değiştirme İşlemi Yapılır
END IF
NEXT
NEXT

Burada Dizi(i) < Dizi(j) ifadesi; "ilk seçilen eleman, ikinci seçilen elemandan küçükse yer değiştir" demektir. Böylece en sonunda Büyükten-Küçüğe sıralanmış bir dizi elde edilir. İlk seçilen eleman her zaman ikinci eçilen elemandan önde olduğu için yer değişiminde büyük sayılar öne oğru hareket edecektir. Eğer Küçükten-Büyüğe bir sıralanma istenirse Dizi(i) > Dizi(j) şeklinde değişiklik yapılır.

2. KABARCIK SIRALAMASI (BUUBLE SORT)

Yer değiştirme sıralamasında olduğu gibi anlaşılması kolay bir algoritmadır. Kabarcık Sıralaması yönteminin yer değiştirme yöntemine göre farkı, her geçişte listenin komşu olan elemanlarını kontrol etmesidir.

Yukarıdaki şekilde de görüldüğü gibi 6 elemanlı bir dizi küçükten-büyüğe sıralanmak istenmektedir. Kabarcık Algoritması her seferinde komşu iki elemanı kontrol eder. 1 ile 2 , 2 ile 3 , 3 ile 4 ..vs. Eğer alttaki sayı, üstteki sayıdan küçükse yer değiştirma işlemi yapılır. Dizi bu şekilde bir kere tarandığında, dizideki en büyük değer en alta gelir (mor kare). Daha sonra tekrar aynı tarama yapılır. Ama bu sefer en sona kadar değil 5. elemana kadar gidilir. Bu şekilde tüm liste sürekli taranır. Eğer son taramada bir değişiklik olmamışsa tarama işlemi bitirilir. Sonuçta küçükten büyüğe sıralanmış bir dizi elde edilir.

'Taramanın nerede biteceğini tutan değişken
SonIndex = 5
DO
'Değişiklik Sayısı Sıfırlanıyor
DegisiklikSayisi = 0

FOR i = 1 TO SonIndex
IF Dizi ( i ) > Dizi ( i + 1 ) THEN
DegisiklikSayisi = DegisiklikSayisi + 1
END IF
NEXT

SonIndex = SonIndex - 1

LOOP WHILE DegisiklikSayisi = 0

N Elemanlı Liste İçin Aşağıdaki Değişikliği Yapın
SonIndex = N - 1

 

3. SEÇMELİ SIRALAMA (SELECTION SORT)

Bu algoritmada dizinin başından veya sonundan başlanabilir. Davranış şekli (Küçükten-Büyüğe) şöyledir: 1. eleman seçilir. Dizi içindeki en küçük terim bulunarak 1. eleman ile yer değiştirilir. Artık 1. indiste en küçük vardır. 2. eleman seçilir. Diğer sayılar içinden en küçük terim bulunur ve 2. ile yer değiştirilir. Bu şekilde dizinin sonuna kadar tek tarama ile yer değiştirme işlemi yapılır.

Yukarıdaki şekilde 8 elemanlı sırasız bir dizi verilmiştir. Amacımız Küçükten-Büyüğe sıralamak olsun. 1.adımda; 1.eleman, dizideki en küçük eleman ile yer değiştirilir. 2.adıma geçeriz. Artık 1.eleman en küçük olarak bellidir. Değiştirilmez (Mor kareler yerleri sabit olan sayılardır). 2.elemanı dizi içindeki en küçük elemanla yer değiştiririz. Bu şekilde bu kuralı baştan sona uygularsanız. Dizi sıralanmış olur. 4.adımda 4.sayıya kadar yerleştirmenin gerçekleştiğine dikkat edin.

'Taramanın nerede biteceğini tutan değişken
SonIndex = 5
FOR i = 1 TO 7
' En Küçük Eleman i.Eleman Olarak Varsayılır.
min = i
' Gerçek En Küçük Eleman Aranır
FOR j = i + 1 TO 8
IF dizi(j) < dizi(min) THEN min = j
NEXT

' En Küçük Bulundu. Değişiklik Yapılır.
SWAP dizi(i), dizi(min)
NEXT

' N Elemanlı Liste İçin
FOR i = 1 TO N-1
min = i
FOR j = i + 1 TO N
IF dizi(j) < dizi(min) THEN min = j
NEXT j
SWAP dizi(i), dizi(min)
NEXT

 

4.BÄ°RLEÅžMELÄ° SIRALAMA (MERGE SORT)

Bu algoritma iki sıralı diziyi tek bir dizide sıralamak için kullanılır. N elemanlı, sıralı bir A dizisi ile M elemanlı, sıralı bir B dizisini; (M + N) elemanlı bir C dizisine sıralı olarak yerleştirir. Bu işi teorik olarak önce A'yı sonra da B'yi, C dizisi içine yazdırarak ve C dizisini sıralatarak da bulabiliriz. Ama bu algoritma etkin olmaz. Zaten sıralanmış olan dizileri bozmuş oluruz. Bunun daha kolay yapılabilmesi için aşağıdaki işlemler yapılır.