Batu Incecay Rotating Header Image

algoritma analizi

Kaba Kuvvet Sıralama Algoritmaları

Bu yazımda Kaba Kuvvet (Brute Force) algoritmaları hakkında genel bilgi sahibi olup kaba iki farklı kaba kuvvet algoritması olan Seçmeli Sıralama (Selection Sort) ve Kabarcık Sıralama (Bubble Sort) algoritmalarına ve bu algoritmaların analizlerine göz atacağız. Bu yazıyı okumadan önce algoritma analizi hakkında genel bilgi edinmek için bir önceki yazımı buradan okuyabilirsiniz.

Kaba kuvvet (brute force) algoritmalar adından da anlaşılabileceği gibi olabildiğince basit algoritmalardır. Basit olmalarına rağmen etkin değildirler. Etkinliği kötü olsa da az elemanlı gruplarda rahatlıkla kullanılabilirler; ancak gruplar büyüdükçe etkinlik de üstel olarak azalacağından daha etkin algoritmalar tercih edilmelidir.

Seçmeli sıralama algoritması her bir iterasyonda en küçük elemanı seçerek bu elemanı dizinin başına getirir. Bu sayede tüm iterasyonlar bittiğinde dizi küçükten büyüğe sıralanmış bir hal alır. (Diziyi büyükten küçüğe sıralamak için her iterasyonda en büyük değerin bulunması yeterlidir.) Algoritmayı sözel olarak açıklayacak olursak; dizinin ilk elemanı en küçük eleman olarak kabul edilir ve bu eleman dizinin diğer tüm elemanları ile karşılaştırılır. Dizide daha küçük bir eleman bulunduğunda bu elemanın yeri tutulmaya başlanır. Bu sayede dizinin tüm elemanları gezildiğinde en küçük eleman bulunmuş olur ve dizinin en başına getirilir. Daha sonra ikinci, üçüncü, dizinin son elemanına kadar aynı işlem yapıldığında dizi sıralanmış olur. Kısaca her zaman dizinin kalan en küçük elemanını bulmak ve bunu en başa getirmek hedeflenmiştir. Seçmeli sıralamanın algoritması şu şekildedir:secmeliSiralamaGelelim seçmeli sıralama algoritmasının analizine. Yukarıdaki algoritmaya baktığımızda bu algoritmadaki temel işlem karşılaştırma işlemidir ( if A[j] < A[min] ). Algoritmadaki döngüleri birer toplam sembolüne dönüştürürsek algoritmadaki temel işlem sayısını şu şekilde hesaplayabiliriz: secmeliAnalizToplam sembolü formüllerini kullanarak sonucu hesapladığımızda temel işlemin n(n-1)/2 kez kullanıldığı sonucuna erişiyoruz. Algoritmanın biraz iyileştirilmiş (her küçük olduğunda swap işlemi yapan) halini anlatan Macar halk dansına buradan erişebilirsiniz.

Bugün inceleyeceğimiz bir diğer algoritma da kabarcık sıralama algoritması. Kabarcık sıralama algoritmasını sözlü olarak anlatmaya çalışırsak; dizinin başından yan yana olan tüm ikililerin karşılaştırılması şeklindedir. Bu karşılaştırma sonucunda ikiliden daha büyük olan eleman dizinin sonuna doğru ilerler (küçükten büyüğe sıralama yapılırken). Bu sayede ilk iterasyon bittiğinde dizinin en büyük elemanı en sona yerleşmiş olur. Bu nedenle de her iterasyonda en baştan başlayarak en sona kadar değil en sondan birer öncesine kadar bu işlem devam etmektedir. Kabarcık sıralama algoritması şu şekildedir:kabarcikSiralamaKabarcık sıralama algoritması için de temel işlem seçmeli sıralama algoritmasında olduğu gibi karşılaştırma işlemidir (f A[j+1] < A[j] ).  Temel işleme göre algoritmanın analizi şu şekildedir:

kabarcikAnaliz

Kabarcık sıralama algoritmasında da temel işlem sayısı n(n-1)/2 kadardır. Kabarcık algoritmanın Macar halk dansı ile anlatılışını buradan izleyebilirsiniz.

Seçmeli sıralama ve kabarcık sıralama algoritmalarının analizlerini incelediğimizde ilk toplam sembolünü açtığımızda birbirleri ile aynı olduğunu görebiliriz. Seçmeli sıralama algoritmasında her seferinde bir eleman sonrasından başlayıp dizinin sonuna kadar giderken; kabarcık sıra algoritmasında her seferinde en baştan başlayıp dizinin sondan daha önceki elemanlarına gittiğimiz görülmektedir. Daha basit bir şekilde ifade etmek gerekirse seçmeli sıralama algoritmasında her iterasyonda en küçük eleman belirlenirken, kabarcık sıralama algoritmasında her iterasyonda en büyük eleman belirlenmiş olur. Böylece iterasyonlar sıralandığında iki algoritmada da aynı şekilde bir sıralama yapılmış olur.

Kaba kuvvet olan iki algoritmada da görüldüğü gibi etkinlik dizinin eleman sayısının karesi ile doğru orantılıdır. Bu nedenle dizinin eleman sayısı arttığında etkinlik azalacaktır. Bu nedenle de daha etkin algoritmalara ihtiyaç vardır.

Algoritma Analizi

Algoritma, bir problemi çözmek için kesin ve açık bir şekilde belirtilmiş bir dizi talimat olarak tanımlanabilir. Bir algoritma etkin (effective), belirli (definite), doğru (correct) ve sonlu (finite) olmalıdır.

Örneğin n elemanlı bir A dizisindeki girdi değeri bulan ve bulunduğu konumu geri döndüren (değer bulunamıyorsa -1 döndüren) algoritma şu şekildedir:

AramaAlgorithm

Biz algoritmanın etkinliğini tam olarak hesaplamak istiyoruz. Bu noktada öncelikle o algoritmadaki temel işlemi bulmalıyız. Yukarıda verdiğimiz arama algoritmasındaki temel işleme bir bakalım. Bu algoritma için temel işlem karşılaştırma işlemi. ( if A[i] = girdi] ) Temel işlemi bulduktan sonra bizi sonuca götürecek konu bu temel işlemin ne kadar tekrarlandığı.

Birkaç örnek üzerinden gidelim. Aşağıda aynı 7 elemana sahip ancak elemanları farklı şekilde sıralanmış 3 dizi var. Bu diziler üzerinde 1 değerini arayalım.

1, 6, 8, 9, 5, 7, 3                     7, 5, 9, 8, 1, 6, 3                      9, 8, 7, 6, 5, 3, 1

Algoritmayı 3 dizi için de uyguladığımızda karşılaştırma sayıları sırasıyla 1, 5, 7 şeklinde olacaktır. Gördüğünüz üzere algoritmanın etkinliği girdiye göre değişiyor; ancak biz girdiden bağımsız çalışıyoruz. Elimizde sadece algoritma var ve bu algoritmanın etkinliğini girdiden bağımsız olarak hesaplamamız gerekiyor. Bu noktada ne yapacağız? Bir algoritmayı analiz ederken; aksine bir söylem yoksa en kötü durumu hesaplarız. Ben burada en iyi, ortalama ve en kötü durumu hesaplayıp nasıl hesaplandığını göstereceğim.

En iyi durum en kolayı… Arama algoritmasını düşündüğümüzde en iyi durum nedir? Tabii ki ilk terimin minimum olmasıdır. Bu durumda da temel işlem yani karşılaştırma işlemi sadece bir kez yapılır. Yani sonuç 1’dir.

En kötü durum için işler biraz daha karmaşıklaşıyor. En kötü durum bizim örneklerimizde de görüldüğü gibi for döngüsüne her girdiğinde temel işlemimiz olan karşılaştırma işleminin yapılıp, dizinin son eleman olması (aranan elemanın dizide bulunamaması durumu da olabilir). Bunu da toplam sembolü ile şu şekilde belirtebiliriz. Döngü n kere döneceğine göre:

toplam olup, temel işlemin yapılma sayısını verecektir. Son örnekte de gördüğümüz gibi bu algoritma için en kötü durum tüm dizinin sonuna gelinmesidir. Bu durumda en kötü durum dizinin boyutu kadar olacaktır.

Son olarak gelelim ortalama durumuna… Aranan elemanın dizide bulunma ihtimali p olsun. Bu durumda hesaplamayı şu şekilde yapabiliriz.

Aranan elemanın dizinin 1. elemanı olması ihtimali                           : p/n
Aranan eleman dizinin 1. elemanı ise yapılan karşılaştırma sayısı          : 1
Aranan elemanın dizinin 2. elemanı olması ihtimali                           : p/n
Aranan eleman dizinin 2. elemanı ise yapılan karşılaştırma sayısı          : 2
Aranan elemanın dizinin 3. elemanı olması ihtimali                           : p/n
Aranan eleman dizinin 3. elemanı ise yapılan karşılaştırma sayısı          : 3


Aranan elemanın dizinin n. elemanı olması ihtimali                           : p/n
Aranan eleman dizinin n. elemanı ise yapılan karşılaştırma sayısı          : n
Aranan elemanın dizide BULUNMAMA ihtimali                                   : 1 – p
Aranan eleman dizide BULUNMUYORSA yapılan karşılaştırma sayısı       : n

Basit bir aritmetik ortalama alırsak:

ortalama

Eğer aranan elemanın dizide mutlaka bulunacağını kabul edersek; yani p = 1 olursa;
Ortalama karşılaştırma işlem sayısı: (n+1)/2 olur. Yani yaklaşık olarak dizinin eleman sayısının yarısıdır.

Basit bir algoritmanın en iyi, ortalama ve en kötü temel işlem sayılarını hesaplamayı görmüş olduk. Sonraki yazılarımda da bilinen bazı algoritmaları (örneğin ikili arama algoritması) analiz etmeye çalışacağım.