Comb Sort (Tarak Sıralama)
Bu yazımda Comb Sort algoritması nedir? Örnekle kısaca anlatmaya çalışacağım.
Comb Sort (Tarak Sıralama)
Comb sort (Tarak Sıralaması), bilinen diğer sıralama algoritmalarına benzer bir şekilde bir dizi öğeyi sıralamak için kullanılan bir algoritmadır. Comb Sort, Bubble Sort’un gelişmiş şeklidir. Bubble Sıralama tüm bitişik değerleri karşılaştırırken, Comb sıralama tüm kaplumbağa değerlerini veya listenin sonuna yakın küçük değerleri kaldırır. Comb sort algoritması, bubble sort algoritmasından daha hızlı çalışabilir, ancak hala en iyi performansı sağlayan algoritma değildir. Özellikle, daha hızlı çalışan sıralama algoritmaları mevcuttur. Ancak Comb sort algoritması, basit ve anlaşılır bir algoritmadır ve özellikle küçük boyutlu dizilerde hızlı bir şekilde çalışabilir. Ayrıca, algoritmanın JavaScript’te uygulanması da oldukça kolaydır.
Esas olarak bubble sıralamada bir gelişme olan, karşılaştırmaya dayalı bir sıralama algoritmasıdır. Bubble sıralamada, verilen diziyi sıralamak için bitişik öğeler arasında bir karşılaştırma vardır. Bu nedenle, bubble sıralamada, karşılaştırılan öğeler arasındaki boşluk boyutu 1'dir. Tarak sıralama, 1'den büyük bir boyut aralığı kullanarak bubble sıralamayı iyileştirir. Tarak sıralamadaki boşluk, daha büyük değerle başlar ve ardından 1.3 faktörü. Bu, her fazın tamamlanmasından sonra boşluğun büzülme faktörü 1.3'e bölünmesi anlamına gelir. İterasyon, boşluk 1 olana kadar devam eder. 200.000 rasgele listede tarama sıralaması test edilerek küçültme faktörü 1,3 olarak bulundu. Tarak sıralama, kabarcık sıralamadan daha iyi çalışır, ancak ortalama durumdaki ve en kötü durumdaki zaman karmaşıklığı O(n 2 ) olarak kalır.
Comb sort algoritması büyük boyutlu dizileri sıralamak için etkili bir algoritmadır. Dilimleme faktörü ve geçiş boyutu parametreleri, algoritmanın performansını arttırmak için kullanılır. Bu algoritmanın kullanımı, bubble sort algoritmasına kıyasla daha iyi performans sağlayabilir
Küçült faktör şu şekilde hesaplanır:
1 / (1 − (1 / e ^ phi)) =1.247330950103979
Burada phi altın orandır=1.61803399
(phi Matematiksel olarak şu şekilde hesaplanır: (1 + √5) / 2) )
Bu nedenle ilk boşluk list.length/1.3 şeklindedir. Ardından, listenin başlangıcındaki değerleri ve bu boşluk değerini karşılaştırır ve buna göre değiştirirsiniz. Bu fikir kaplumbağaları fiilen öldürebilir çünkü bazıları listenin başında en başa “atlayabilir”. Boşluk daha sonra küçültme faktörü tarafından, algoritma kabarcık sıralamaya düştüğünde 1 olana kadar azaltılır. Ancak, kaplumbağalar öldürüldüğü için bubble sort verimlidir.
Comb Sort Algoritması (Sözde Kod)
combsort(list[]){
gap<-list.length; // boşluğu dizi boyutuna başlat
swapped<-true; // takasın gerçekleşip gerçekleşmediğini test etmek için bir boole değeri
while(gap>1 || swapped) // takas tamamlanana kadar döngüye gir
if (gap > 1)
gap <- (int) (gap / 1.247330950103979); // yeni boşluğu hesapla
else if(gap<1)
gap<-1; // En küçük boşluk sadece 1 olabilir
i <- 0;
swapped <- false; // hiçbir şey değiştirilmedi
while(i+gap<list.length)
if(list[i]>list[i+gap]) //değerleri değiştir
temp<-list[i];
list[i]<-list[i+gap];
list[i+gap]<-temp;
swapped<-true;
i<-i+1;
}
Örnek Çalışma
Sıralanmamış bir dizi alırsak 5, 7, 10, 3, 1, 4, 8, 2, 6, 0, 9.
Büzülme faktörü 1.3 ve listenin boyutu 11'dir.
Yalnızca uygulama amacıyla, bu algoritmayı gerçekleştirmek için farklı programlama dillerinde yazılmış örnek programları dahil ettim. Bir JAVA,C ve PHP programları içerirler
Algoritmanın Analizi
Bubble sort, Comb sort sırasında 10.000 öğeyi 1.36 saniyede sıralar. Comb sort, 10.000 öğeyi 0,0042 saniyede sıralar, C++ hızlı sıralamadan yalnızca 1,1 kat daha uzun. Bubble sort bu kadar basit bir değişikliğin onu neredeyse hızlı sıralama kadar iyi yapması şaşırtıcı. Ayrıca comb sort, zaten sıralanmış listelerin varlığında bozulmayı önlemek için herhangi bir özel koda ihtiyaç duymaz.
Çalışma Süresi
Çalışma süresi söz konusu olduğunda, Kabarcık Sıralama ile karşılaştırıldığında tarak sıralamanın nasıl biriktiğini görelim. Aşağıdaki ampirik sonuçlar, taraklı ayıklamanın kabarcıklı ayıklamaya kıyasla elde ettiği hızı göstermektedir. Tarak sıralamanın en kötü durum çalışma süresi O(n 2 ).
Sonuç olarak, Comb Sort algoritması, belirli durumlarda kullanılabilecek bir sıralama algoritmasıdır. Ancak büyük veri setleri veya hızlı sıralama gerektiren uygulamalar için daha etkili algoritmalar mevcuttur
Bu makalem de bir Comb Sort Algoritmasından örnekle kısaca bahsetmeye çalıştım.
Buraya kadar okuduğunuz için teşekkür ederim😃.Merak edip araştırdığım konuları Medium da paylaşmaya devam edeceğim. Birlikte okuyup, gelişmeye devam edelim..
