Yazan : Şadi Evren ŞEKER
Bu yazının amacı bora sıralamasını (şimşek sıralaması, flash sort) açıklamaktır. Bu sıralama algoritması yapısal olarak aslında araya ekleme sıralamasının (insertion sort) özel bir hali olarak kabul edilebilir. Sıralama algoritmaları arasında parçalı sıralama özelliği olan diğer sıralama algoritmaları ile aynı sınıfta kabul edilebilir.
Bora sıralamasında amaç, bir veri kümesinin bilinen bir dağılıma uygun olması durumunda bu özelliğini sıralama algoritmasında kullanmaktır. Yani şayet elimizde olan ve sıralamak istediğimiz sayılar gauss dağılımına (guassian distribution) uygunsa bu sıralama algoritması tarafından bir avantaj olarak kullanılabilir.
Parçalı sıralama algoritmaları (partial sort algorithm) dağılımdan gelen bu özelliği kullanarak sıralamadan önce bir aşamada sayıları mümkün olduğunca sonuçta olacakları yere yaklaştırmayı hedefler. Ardından herhangi bir sıralama algoritması ile işlem tamamlanır.
Örneğin elimzide tekdüze dağılıma sahip (uniform distribution) bir veri kümesi varsa, bu durumda her sayının gideceği adresi aşağıdaki şekilde hesaplayabiliriz:
Diğer bir deyişle sıralanmış halindeki konumu olan S(Ai), verilen aralıktaki ( A azami ve asgari aralığı) bulunduğu konum içerisinde asgari değere olan uzaklığı ile ölçülebilir. Sayı kümemizin 0’dan başladığını kabul edersek 1 ilave edilebilir. Ayrıca kaç sayımız olduğu, yukarıdaki m sembolü ile ifade edilmiştir.
Bu durumu bir örnek üzerinden anlatalım. Örneğin elimizde 1 ile 10 arasında 5 adet sayı olsun ve bu sayılar tekdüze dağılım (uniform distribution) özelliği gösteriyor olsun. Diyelim ki sayılarımız aşağıdaki şekilde verilmiş olsun (kolaylık olması için sadece tek sayıları alacağım):
3,5,1,7,9
Şimdi her sayıyı doğru konuma koymak için aşağıdaki şekilde bora sıralamasını kullanalım.
İlk sayımız 3, sayı aralığımızı aşağıdaki şekilde hesaplayabiliriz:
Neticede 3 sayısının 2. sırada olacağını bulduk. Benzer şekilde diğer sayıları hesaplayalım:
Sonuç olarak dizimizdeki elemanları aşağıdaki şekilde bulduğumuz sıralı yerlere yerleştiriyoruz.
| Sayı | 1 | 3 | Boş | 5 ve 7 | Boş | 9 |
| Konum | 1 | 2 | 3 | 4 | 5 | 6 |
Yukarıda görüldüğü üzere, sonuçta bulunacakları adresler, bazı sayılar için kesin olarak bulunmuş oldu, bazı sayılarda ise çakışmalar bulunuyor. Bu çakışmaları önlemek için dizi yeniden işlenebilir veya sayının bulunduğu anda müdahale edilebilir. Örneğin yukarıdaki hesaplamalar sonucunda, sonuç dizisine yazmak yerine bulduğumuz adreslerdeki sayıları verilen değerlere göre sıraladığımızı düşünelim:
1,3,7,5,9
Yukarıdaki sıralamada 7 ve 5 aynı adrese geldikleri için (collision) kötü ihtimal olan sırasız halini ele aldım. Bu durumda örneğin kabarcık sıralaması (bubble sort) kullanmamız halinde bile algoritmamız çok daha hızıl sıralama işlemini yapıp sonuca ulaşacaktır.
Elbette sayılar yukarıdaki örnekte olduğu gibi her zaman mükemmel olmayabilir, tam bir dağılım özelliği göstermeyebilir. Bu durumda son halinin üzerinden geçilerek bir sıralama işlemi yapılması gerektiği kesindir. Bu aşamada istenen bir sıralama tercih edilebilir ancak sıralanmış diziyi en az işleyen algoritmalar tercih sebebidir.