AlgoPit

Bubble Sort Algoritması

Bubble Sort Açıklaması

Bubble Sort, en basit sıralama algoritmalarından biridir. Her geçişte, komşu elemanları karşılaştırarak, büyük elemanların dizinin sonuna doğru kabarcık gibi yükselmesini sağlar. ## Çalışma Prensibi: 1. Dizinin başından başlayarak, her bir elemanı sağındaki komşusuyla karşılaştırır. 2. Eğer soldaki eleman, sağdakinden büyükse, yerlerini değiştirir. 3. Bu işlem, dizinin başından sonuna kadar tekrarlanır. 4. Her tam geçiş sonrası, en büyük eleman dizinin sonuna yerleşir. 5. Bir sonraki geçişte, son eleman zaten yerleştiği için, bir önceki elemana kadar karşılaştırma yapılır. 6. Hiçbir takas işlemi gerçekleşmediğinde, dizi sıralanmış demektir ve algoritma sonlanır. ## Optimizasyonlar: 1. **Erken Çıkış**: Eğer bir geçişte hiçbir takas yapılmamışsa, dizi sıralanmış demektir. 2. **Sınır Takibi**: Her geçişte, bir önceki geçişte yerleştirilen elemanlar için gereksiz karşılaştırma yapılmaz. Bubble Sort, eğitim amaçlı ve küçük veri setleri için uygundur, ancak büyük veri setleri için verimli değildir.

Kod Örnekleri

Bubble Sort algoritmasının farklı programlama dillerindeki uygulamaları aşağıda verilmiştir. Her örnek, algoritmanın optimize edilmiş versiyonunu içerir ve detaylı açıklamalarla sunulmuştur.

Bubble Sort - JavaScript
1/**
2 * Bubble Sort implementation for JavaScript arrays
3 * @param {Array} arr - The array to sort
4 * @returns {Array} - A new sorted array
5 */
6function bubbleSort(arr) {
7  // Create a copy to avoid modifying the original array
8  const result = [...arr];
9  const n = result.length;
10  
11  // Outer loop - each pass places one element in its final position
12  for (let i = 0; i < n - 1; i++) {
13    // Optimization: track if any swaps occurred during this pass
14    let swapped = false;
15    
16    // Inner loop - compare adjacent elements and swap if needed
17    for (let j = 0; j < n - i - 1; j++) {
18      if (result[j] > result[j + 1]) {
19        // Destructuring swap - cleaner than using a temp variable
20        [result[j], result[j + 1]] = [result[j + 1], result[j]];
21        swapped = true;
22      }
23    }
24    
25    // If no swaps occurred, the array is already sorted
26    if (!swapped) break;
27  }
28  
29  return result;
30}

Kendi Verilerinizle Test Edin

Aşağıya kendi verilerinizi girerek Bubble Sort algoritmasını test edebilirsiniz. Virgülle ayrılmış sayılar girin (örn: 5,3,8,4,2) veya rastgele bir dizi oluşturun.

Bubble Sort Demo

Verdiğiniz dizi Bubble Sort algoritması ile sıralanacaktır.

Sıralanmış Dizi: null

Not: Bubble Sort büyük veri setleri için verimli değildir. 1000'den fazla eleman içeren diziler için daha verimli algoritmalar tercih edin.

Algoritma Analizi

Zaman ve Alan Karmaşıklığı

Zaman Karmaşıklığı

  • En İyi Durum: O(n) - Dizi zaten sıralıysa, algoritma tek bir geçişte tamamlanır (erken çıkış optimizasyonu ile).
  • Ortalama Durum: O(n²) - İç içe iki döngü kullanır ve ortalamada n²/2 karşılaştırma gerektirir.
  • En Kötü Durum: O(n²) - Dizi tersine sıralıysa, her eleman için bir takas gerekir, n(n-1)/2 karşılaştırma yapılır.

Alan Karmaşıklığı

O(1) - Bubble Sort yerinde (in-place) bir sıralama algoritmasıdır. Giriş dizisinin boyutundan bağımsız olarak sabit miktarda ekstra bellek kullanır.

Kararlılık (Stability)

Bubble Sort kararlı bir algoritma olduğundan, eşit değere sahip elemanların göreceli sırası korunur. Bu özellik, ikincil sıralama kriterleri olan uygulamalarda önemlidir.

Avantajlar ve Dezavantajlar

Avantajlar

  • Anlaşılması ve uygulanması son derece kolaydır.
  • Ekstra bellek alanı gerektirmez (O(1) alan karmaşıklığı).
  • Kararlı bir algoritma olduğundan, eşit değerli elemanların sırası değişmez.
  • Erken çıkış optimizasyonu ile zaten sıralı veriler için O(n) karmaşıklığa sahiptir.
  • Çok küçük veri setleri için basit ve verimli olabilir.

Dezavantajlar

  • Büyük veri setleri için O(n²) zaman karmaşıklığı nedeniyle oldukça verimsizdir.
  • Selection Sort ve Insertion Sort gibi diğer basit algoritmalardan genellikle daha yavaştır.
  • Takas işlemi sayısı fazladır, bu da performansı düşürür.
  • Modern uygulamalarda, daha iyi performans sunan algoritmalar (Quick Sort, Merge Sort vb.) tercih edilir.

İlgili Algoritmalar

Bubble Sort'a benzer veya alternatif olarak kullanılabilecek diğer sıralama algoritmaları:

Insertion Sort

Küçük veri setleri için verimli ve kısmen sıralı veriler için O(n) performans sunar.

Selection Sort

Bubble Sort'a benzer karmaşıklığa sahip, ancak takas işlemi sayısı daha azdır.

Cocktail Sort

Bubble Sort'un iki yönlü bir varyasyonu, daha hızlı yakınsama sağlayabilir.