Batu Incecay Rotating Header Image

selection sort

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.