Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinde özellikle eğitim amacıyla kullanılan bir sıralama algoritmasıdır. Algoritmanın çalışması oldukça basittir, bogosort, verilen bir diziyi sıralamak için rast gele bir dizilim üretir ve sıralı olup olmadığına bakar, şayet sıralıysa algoritma sona erer, şayet sıralı değilse rastgele olarak yeni bir dizilim elde eder, ta ki sayılar sıralanana kadar sayıları rastgele dizmeye devam eder.
Bu algoritma basitçe bir dizinin sıralı olana kadar rastgele dizilmesi olarak ifade edilebilir. Algoritmaya rastgele sıralama (random sort) veya maymun sıralaması (monkey sort) veya çifteli tüfek sıralaması (shotgun sort) anlamında isimlerde verilmektedir.
Bu algoritmanın gerçek hayatta kullanılabilirliği işlem süresinin uzunluğundan dolayı yoktur. Ancak eğitim amaçlı olarak literatürde geçmektedir.
Algoritmanın en iyi ihtimali O(n) olarak düşünülebilir çünkü şayet verilen dizi sıralıysa sadece dizinin sıralı olduğunu kontrol etmek için n tane elemanın üzerinden bir kere geçilmesi yeterlidir.
Buna karşılık en kötü ihtimalle sonsuza kadar çalışabilecek bir algoritmadır. Algoritmanın ortalama performansı için biraz istatistik bilgilerimizi tazelememiz gerekir.
Bilindiği üzere bir dizideki n elemanın farklı dizilim sayısına permütasyon ismi verilir. Bir dizideki n elemanın n! Tane farklı dizilme ihtimali bulunur.
Bu durumda her dizilimin n elemanlı bir kontrolden geçeceğini düşünürsek algoritmanın ortalama performansı (Average case) O(n n!) olarak bulunur.