Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde kullanılan ve tek boyutlu bir veri yapısı üzerinde (örneğin dizi (array) ) sıralama yapmaya yarayan bir algoritmadır. Algoritmanın çalışması birleştirme sıralaması (merge sort) veya hızlı sıralama (quick sort) algoritmalarına benzetilebilir. Bunun sebebi algoritmanın, sıralamak istenen sayıları 2/3 oranında iki parçaya bölmesi ve kalan sayıları kendi aralarında sıralamasıdır.

Algoritmanın açıklaması ve kodlanması

Bu anlamda algoritmanın çalışması aşağıdaki adımlarla izah edilebilir:

• Dizinin sonundaki sayı, başındaki sayıdan küçükse bu sayıların yerini değiştir (swap)
• Şayet işlem yapılan elaman sayısı 3 veya daha fazlaysa
  • Elemanların ilk 2/3′ünü serseri sıralamasına ver
  • Elamanların kalan 1/3′ünü serseri sıralamasına ver
  • Elamanların ilk 2/3′ünü tekrar serseri sıralamasına ver

Yukarıdaki algoritmadan görüleceği üzere dizinin serseri sıralaması sırasında (stooge sort) 2/3. Elemandan itibaren iki parçaya bölündüğü düşünülebilir. Algoritmanın kodlaması aşağıdaki şekilde yapılabilir:

Yukarıdaki algoritmanın çalışması sonucu aşağıda verilmiştir:

Görüldüğü üzere sıralama algoritması kodun 15. Satırında, sıralama işlemi yapılan sayı aralığının 2/3′üncü elemanını bulmaktadır. Ardından kodun 16. Satırında ilk 2/3 ve kodun 17 satırında kalan 1/3 elemanlar sıralanmakta. En sonunda ise tekrar elemanların ilk 2/3′ü sıralanmaktadır.

Örnek çalışma

Yukarıdaki algoritmayı kullanarak örneğin aşağıdaki dizinin sıralanmasını adım adım göstermeye çalışalım.

Dizimiz şu şekilde verilsin:

{15,11,4,6,8,3}

İlk adımda, dizinin ilk ve son değerleri karşılaştırılacak ve son değer, ilk değerden küçük olduğu için yer değiştirilecek:

{3,11,4,6,8,15}

Ardından diziyi 2/3 nispetinde iki parçaya bölecek ve ayrı ayrı sıralamaya çalışacak. K değeri burada 6/3 = 2 , 5-2 = 3 olarak bulunur.

{{3,11,4,6} {8,15}}

İlk parçadaki ilke eleman olan 3, son eleman olan 6′dan küçük dolayısıyla sorun yok ve listeyi gene parçalıyoruz.K değeri bu sefer 3/3 = 1 , 3-1 =2 olarak bulunur:

{{{3,11,4},{6}} {8,15}}

Yeni parça için bir problem bulunmuyor çünkü 3<4 durumu bulunuyor. Parçalama işlemine devam ediyoruz : 3/3 = 1 , 2-1 = 1 olarak bulunuyor:

{{{{3,11},{4}},{6}} {8,15}}

Yukarıdaki kodda, 3 elemandan düşük sayıya ulaştığımız için, artık bir alt satırda bulunan ve geri kalan 1/3′lük elemanları sıralayan kısma geçebiliriz. Bu adımda sadece 4′ten oluşan sayılar sıralanacak ki bu değer de zaten 4′tür. (kodun 17. Satırı)

Ardından kodun 18. Satırına devam edip ilk 2/3 elemanı sıralıyoruz:

{{{{3,11},{4}},{6}} {8,15}}

Özyineli olarak çalışan kodumuz üç farklı sıralama işlemini bitirip, bu işlemleri çağıran ve özyineli yığınında (recursion stack) bir üst seviyede duran fonksiyonu çalıştırıyor. Bu durumda bir üst parça için geri kalan 1/3 sıralanıyor:

{{{{3,11},{4}},{6}} {8,15}}

Sonra kodun ilk 2/3′ü tekrar sıralanıyor:

{{{3,4,11},{6}} {8,15}}

Aynı işlem bir üst seviyeye çıkılarak devam ediyor:

{{{3,4,11},{6}} {8,15}}

{{3,4,6,11}, {8,15}}

{3,4,6,8,11,15}

Algoritma performansı.

Algoritma problemi iki parçaya böler. Birinci parça 1/3 ikinci parça ise 2/3 eleman içermektedir ve 2/3 eleman içeren kısım iki kere işlenir. Bu durumda performans için O(n^{log(3) / log(1.5)}) = O(n^2.8) denilebilir.

485 views