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.
indisA = 1: indisB = 1: indisC = 1
' Dizilerden biri sonlanana kadar DO-LOOP döngüsü çalışır.
DO
IF A(indisA) < B(indisB) THEN
C(indisC) = A(indisA)
indisA = indisA + 1
ELSE
C(indisC) = B(indisB)
indisB = indisB + 1
END IF
indisC = indisC + 1
LOOP WHILE NOT (indisA > 5 OR indisB > 6)
' Dizilerden biri önce biteceÄŸi için diÄŸer dizi aynen yazılır.
IF indisA > 5 THEN
FOR j = indisB TO 6
C(indisC) = B(j)
indisC = indisC + 1
NEXT
ELSE
FOR j = indisA TO 5
C(indisC) = A(j)
indisC = indisC + 1
NEXT
END IF
indisA = 1: indisB = 1: indisC = 1
DO
IF A(indisA) < B(indisB) THEN
C(indisC) = A(indisA)
indisA = indisA + 1
ELSE
C(indisC) = B(indisB)
indisB = indisB + 1
END IF
indisC = indisC + 1
LOOP WHILE NOT (indisA > N OR indisB > M)
IF indisA > N THEN
FOR j = indisB TO M
C(indisC) = B(j)
indisC = indisC + 1
NEXT
ELSE
FOR j = indisA TO N
C(indisC) = A(j)
indisC = indisC + 1
NEXT
END IF
| < Önceki | Sonraki > |
|---|
Yorumlar
RSS beslemesi, bu iletideki yorumlar için.