Cyber-Warrior.Org \ Doküman \ Programlama

1. SIRALAMA

Genellikle siralama (sorting) islemlerini veritabaninda kullaniriz.

Isim bilgileri harf sirasinda, telefon bilgileri alan kodlarina siraliolarak

istenebilir. Programimiz bu olanaklarisaglamalidir. Çok gerekli olan bu

islemlerin algoritmasikarmasik olabilir. Programinizin siralama hizida

önemlidir. Örnegin 15 ismin siralanmasidakikalarca sürmemelidir.

Bu bölümde göreceginiz bilgisayar bilimi çalismalari, en kisa sürede en etkili sekilde

siralama için düzenlenmistir.

Büyük O Gösterimi

Bir algoritmanin etkinligini ölçmek için bilgisayar programcilari“Büyük O

Gösterimi”ni tasarlamislardir. Büyük O, bir algoritmanin yönetmesi gereken bilgi

miktarinin islenme hiziniölçer.

Programcilar genellikle aynimiktardaki verinin, farklialgoritmalardaki islem süresini

bilmek isterler. Ortalama ve en kötü durum senaryosu üretirler. “Büyük O” sayesinde

program için en uygun algoritma seçilir.

Mesela isimlerin siralanacagibir algoritmada, isimlerin sayisiprogramin hizini

etkiler. Bu O(n) ile gösterilir. “O” siralama büyüklügü, “n” de nesne sayisidir. “n”

boyutundaki bir problemin çözümünde geçen adim sayisiT(n) = 4n² - 2n + 2 olarak

bulunabilir.

1.1. Ekleme Siralamasi

Ekleme siralamasi(insertion sort) aslinda bir kart oyunundaki kartlarin siralanmasina

benzetilebilir. Daginik durumdaki kartlardan iki tanesini elinize alirsiniz, üçüncüsünü

digerlerinin yaninda uygun bir yere eklersiniz. Her kart aldiginizda digerlerinin içinden

uygun olan yere eklersiniz. Böylece kartlar siralihâle gelir.

Bu yöntem ile basitçe program, karisik olan sayilarisu adimlar ile siralar:

1. Ilk iki eleman listeden alinip, karsilastirilir, gerekirse yerleri degistirilir.

2. Bir sonraki eleman alinip, önceki siralielemanlar içinde uygun yere eklenir.

3. Ikinci adim siralama bitene dek tekrar edilir.

Ekleme siralamasinda önce diziye* rastgele degerler yükleriz. Dizinin ikinci

elemanindan baslayan bir ana döngü içinde programiyazariz. Bir sonraki dizi elemanigeçici

olarak bir degiskene aktarildiktan sonra, bu degeri aktif dizi elemaniile karsilastiririz. Eger

“geçici deger” küçük ise baska bir döngüde, siraliolan kisimda bu degerin yeri bulunur. Dizi

siralanana dek bu islem devam eder.

1.2. Balon Siralamasi

Balon siralamasinda (bubble sort) karisik durumdaki sayilar suyun içindeki balonlar

gibi hareket ederek yerlerini bulurlar. Sayilar tekrarliolarak kontrol edilerek yakin sayilar bir

araya getirilir.

1. Ilk iki eleman karsilastirilir, gerekirse yerleri degistirilir.

2. Listede bir sonraki elemana gidilerek, bir önceki eleman ile karsilastirilir.

3. Liste sonuna kadar 2. adim tekrar edilir.

4. 1 ve 3. adim, tüm listenin siralamasibitene dek tekrar edilir.

Önce veri listesi hazirlanir. Ön sartlibir ana döngü içine, sinirlariilk elemandan

sondan bir önceki elemana kadar olan bir döngü yapilir. Seçili elemanin degeri ile dizinin

sonraki elemaninin degeri karsilastirilir. Eger büyük ise iki dizi elemaniyer degistirilir. Dizi

sonuna kadar tarama ve yer degistirme islemleri devam eder. Bu döngü tekrar edilir ve

degisiklik kalmamisise ana döngü sonlandirili

1.3. Kabuk Siralamasi

Karisik durumdaki listede, en sondaki elemanien basa getirmek zaman kaybidir. Bu

sebeple programcilar kabuk siralamasi(shell sort) algoritmasinigelistirmislerdir.

“Böl ve yönet” mantigiile tüm dizinin siralanmasiyerine, küçük parçalar halinde dizi

siralanir. Küçük listeler siralandiktan sonra, listeler birlestirilir.

Aslinda kabuk siralamasi balon ve ekleme siralamasini hizlandirmak için

gelistirilmistir. Yani farklibir siralama algoritmasidegildir.

1. Büyük liste küçük listelere bölünür.

2. Küçük liste balon veya ekleme siralamasiile siralanir.

3. Resim 1.7’deki örnekte 15 ve 29 rakamisiralanmasina gerek yoktur. 16 ve 4

rakamisiralanir, 78 ise isleme girmez.

4. 3. adimda sadece 4 ve 16’nin yeri degisir, tekrar dizi küçük listelere bölünür.

5. Dizide 15, 78 ve 16 siralanir, 4 ve 29 rakamlarinin siralanmasina gerek yoktur.

6. Liste siralamasitamamlanana kadar 2 ve 4. adimlar tekrarlanir

Basla

Sayisal Dizi Veriler(5)

Sayisal i, Geçici, Dur, Geç, X, Sinir

Yaz; "Siralanacak veriler:"

Döngü i = 1, 5, 1

Veriler(i) = Rasgele(100)

Yaz; Veriler(i)

Döngü Bitti

X = tamsayi(5 / 2)

Iken (X > 0)

Dur = 0

Sinir = 5 – X

Iken (Dur = 0)

Geç = 0

Döngü i = 1, Sinir, 1

Eger (Veriler(i) > Veriler(i + X)) Ise

Geçici = Veriler(i)

Veriler(i) = Veriler(i + X)

Veriler(i + X) = Geçici

Geç = 1

Eger Bitti

Döngü Bitti

Sinir = Geç – X

Eger Geç = 0 Ise Dur = 1

Iken Bitti

X = tamsayi(X / 2)

Iken Bitti

Yaz; "Sirali liste:"

Döngü i = 1, 5, 1

Yaz; Veriler(i)

Döngü Bitti

Bitir

1.4. HizliSiralama

Hizlisiralama (quick sort) diger yöntemlere göre daha çok kullanilir. Bu yöntemde

listenin ortasindan bir eleman alinir, elemanin degerine göre sol veya sagdaki degerler yer

degistirir.

Liste yariya bölündükten sonra, her ayrilan parça tekrar yariya bölünür. Alt parçalar

kendi aralarinda siralanir. Küçük parçalar birlestirilerek tüm listenin siralihali olusturulur.

1. Listenin ortasindan bir eleman seçilir. Seçili elemandan büyük olan elemanlar

saga, küçük olanlar sola yer degistirilir.

2. 1. adim listenin her yarisiiçin tekrar edilir.

3. Küçük listeler birlestirilir, siraliliste elde edilir.

Kendini tekrar eden fonksiyonlara “tekrarlamali- recursive” fonksiyon denir. Basit

olarak fonksiyonun kendini çagirmasidir. “Hizlisiralama”da bu yöntem kullaniliyor. Bu

sebeple siralama için alt program yapmamiz gereklidir.

1.5. Siralama Algoritmalari

Ekleme, balon, kabuk ve hizlisiralama yöntemleri ile karisik listelerin degisik

metotlar ile siralanabildigini gördünüz.

Genellikle küçük listelerde ekleme siralamasi, neredeyse siraliolan bir listede balon

siralamasi, hiz gerektiren yerlerde hizlisiralama kullanilir. Fakat kodlamak için gereken

zamandan tasarruf etmek için, programcilar dilin içine “hazir” bulunan siralama komutlarini

tercih ederler. Örnegin, su sekilde bir komut olabilir:

sirala diziAdi, ilkEleman, sonEleman

Dilin kendi komutunu kullanmaniz tavsiye edilir, fakat komut yavasliga neden oluyor

ise, kendi algoritmaniziolusturunuz.

ALINTIDIR!!!

kaynak=megep.meb.gov.tr