Bogo Sort - Saçma Sıralama

28 Temmuz 2023 • ☕️ 3 dk okuma • 🏷 bilgisayar, yazılım, algoritma, sıralama

Yazar tarafından şu dillere çevrildi: English

Bogo Sort (Saçma sıralam veya Permutation Sort olarak da bilinir), sıralanması gereken bir diziyi rastgele permütasyonlar oluşturarak doğru sıralama bulunana kadar karşılaştırmalar yaparak sıralamaya çalışan, son derece etkisiz ve rastgele bir sıralama algoritmasıdır. Bogo Sort, şaka amaçlı bir algoritma olarak ortaya çıkmıştır ve pratik kullanım için uygun değildir.

Çalışma Mantığı ve Algoritma Adımları:

Bogo Sort’un çalışma mantığı oldukça basittir, ancak etkisiz bir şekilde çalışır:

Rastgele bir permütasyon oluşturulur.
Dizinin sıralı olup olmadığı kontrol edilir.
Eğer dizi sıralı değilse, adım 1’e geri dönülür ve yeni bir rastgele permütasyon oluşturulur.
Dizi sıralı olduğunda algoritma sonlanır.

Artı Yönleri:

Eğlenceli ve ilginç bir algoritma olarak görülebilir.
Herhangi bir dizi üzerinde çalışabilir, çünkü sıralı olup olmadığı umursanmaz.

Eksi Yönleri:

Bogo Sort, rastgele permütasyonlar oluşturduğu için son derece verimsizdir. Neredeyse her adımda diziyi doğru sıralamak için gerekli olan adımların sayısı ortalama ve en kötü durumlarda astronomik olabilir.
Pratik kullanım için uygun değildir. Dizinin boyutu arttıkça algoritmanın çalışma süresi hızla artar.
İyi bir zaman ve hafıza karmaşıklığına sahip değildir.

Zaman ve Algoritma Karmaşıklığı Karşılaştırması:

Bogo Sort’un ortalama ve en kötü durum zaman karmaşıklığı oldukça yüksektir. Ortalama durumda n! kadar adım gerekebilir. En iyi durumda bile O(n) zaman karmaşıklığı sağlayamaz.

Diğer sıralama algoritmaları, genellikle daha etkili ve pratik sonuçlar sunar:

Bubble Sort, Selection Sort gibi temel sıralama algoritmaları en azından O(n^2) zaman karmaşıklığına sahiptir, ancak Bogo Sort’un hızından daha iyidirler.
Merge Sort, Quick Sort gibi daha verimli algoritmalar O(n log n) zaman karmaşıklığına sahiptirler ve daha büyük dizilerde bile hızlı sonuçlar sağlarlar.
Bazı özel durumlar için optimize edilmiş algoritmalar, daha hızlı sonuçlar elde etmek için kullanılabilir (örneğin, Counting Sort veya Radix Sort gibi).

Genel olarak, Bogo Sort daha çok eğlence veya eğitim amaçlı bir algoritma olarak görülmektedir ve gerçek dünya uygulamalarında tercih edilen bir sıralama algoritması değildir.

GoLang’de Bogo Sort uygulaması:

package main

import (
	"fmt"
	"math/rand"
	"sort"
	"time"
)

func isSorted(arr []int) bool {
	n := len(arr)
	for i := 1; i < n; i++ {
		if arr[i] < arr[i-1] {
			return false
		}
	}
	return true
}

func shuffle(arr []int) {
	n := len(arr)
	rand.Seed(time.Now().UnixNano())
	for i := n - 1; i > 0; i-- {
		j := rand.Intn(i + 1)
		arr[i], arr[j] = arr[j], arr[i]
	}
}

func bogoSort(arr []int) {
	for !isSorted(arr) {
		shuffle(arr)
	}
}

func main() {
	arr := []int{4, 2, 7, 1, 9, 3, 5}
	fmt.Println("Original Array:", arr)

	bogoSort(arr)
	fmt.Println("Sorted Array:", arr)

	// Checking with built-in sorting for verification
	sortedArr := []int{4, 2, 7, 1, 9, 3, 5}
	sort.Ints(sortedArr)
	fmt.Println("Sorted Array (using built-in sort):", sortedArr)
}

Bu örnekte, bogoSort fonksiyonu Bogo Sort algoritmasını uygular. isSorted fonksiyonu bir dizinin sıralı olup olmadığını kontrol eder. shuffle fonksiyonu diziyi karıştırır. Ana main fonksiyonda bir dizi oluşturulur, bu dizi önce Bogo Sort ile sıralanır, sonra doğrulama için Go’nun yerleşik sıralama fonksiyonu kullanılarak sıralanır.

Program çalıştırıldığında çıktısı aşağıdaki gibi olacaktır.

Original Array: [4 2 7 1 9 3 5]
Sorted Array: [1 2 3 4 5 7 9]
Sorted Array (using built-in sort): [1 2 3 4 5 7 9]

Programın çalışır haline şuradan erişilebilir.

hkucuk