Batu Incecay Rotating Header Image

Ekim, 2011:

Bogosort

Sıralama algoritmaları, programcılık alfabesinin ilk harflerinden bir tanesidir. Bir programcı en az bir tane sıralama algoritmasını adını yazar gibi yazabilir. Programcıların en çok kullandığı sıralama algoritmaları seçmeli sıralama (selection sort), hızlı sıralama (quick sort) ve eklemeli sıralama (insertion sort) olarak söylenebilir. Tabii ki böyle bir genelleme yapmak çok doğru değildir ve kullanılacak yere göre bu algoritmalar da değişiklik gösterir. Örneğin sıralama bir ağaçta yapılacaksa ikili ağaç sıralaması (binary tree sort) kullanılabilir veya iki dizinin birleştirilmesinde birleştirmeli sıralama (merge sort) tercih edilebilir. Ben burada çok bilinen birçok sıralama algoritmasının aksine daha az duyulan ve tercih edilmeyen bir algoritmadan bahsedeceğim: Bogosort.

Sıralama algoritmaları adından da anlaşılacağı gibi kendisine gönderilen veri yapısını sıralamak için kullanılır. Şimdi öyle bir sıralama algoritması düşünün ki bu algoritmanın gönderdiğiniz veri yapısını sıralayacağına dair bir garanti yok. En kötü zaman karmaşası sonsuz! Peki, bu nasıl oluyor? Algoritmayı kolayca anlatabilmek için bir örnek vereyim. Elimizde 1’den 10’a kadar sıralı kağıtlar var. Bu kağıtları yere atıyoruz; attığımız kağıtları yerden toplayıp sıralı olup olmadığına bakıyoruz. Eğer sıralı ise algoritma burada sona eriyor; ancak sıralı değilse kağıtları tekrar yere atıyoruz ve aynı adımları tekrarlıyoruz. Kağıtların sıralanmasında tek bir değişken var ŞANS. Eğer biraz şanslıysanız ilk denemede kağıtlar sıralı olacaktır ve işlem sona erecektir; ama şansınız o kadar da iyi değilse bu işlem sonsuza kadar sürebilir. Bu nedenle de algoritmanın zaman karmaşıklığı sonsuz. Biraz maceracı değilseniz bu algoritmayı denemeyi düşünmezsiniz; en azından sıralayabileceğiniz kesin algoritmalar dururken bu algoritmayı kullanmazsınız. Son olarak algoritmanın Türkçe karşılığını söylemekte yarar var. Bogosort’un Türkçe çevirisi “Saçma Sıralama” veya “Rastgele Sıralama”.