Bubble Sort ve Binary Search: Basit Anlatım ve Kod Örnekleri

Algoritma nedir, neden bu iki örnek?

Sıralama ve arama, programlamanın en temel yapı taşlarındandır. Bir listeyi artan sıraya koymak (sıralama) ya da bir değer listede var mı diye bakmak (arama) birçok gerçek problemde tekrar tekrar karşınıza çıkar. Bu yazıda “basit programlama örnekleri” arayanlar için iki klasik yaklaşımı ele alıyoruz:

• Bubble sort: Öğretici, kolay anlaşılır bir sıralama algoritması.
• Binary search: Sıralı bir dizide çok hızlı arama yapan yöntem.

Not: Büyük veri kümelerinde üretim kullanımında çoğu zaman dilin yerleşik sıralama/arama araçları daha uygundur; bubble sort daha çok eğitim amaçlı anlatılır. Bu yaklaşım, algoritma dersleri ve kaynaklarında da sıkça vurgulanır. Bu çerçeve için MIT’nin algoritma ders notları iyi bir başlangıç referansıdır: MIT OpenCourseWare 6.006 ders notları.

Hız kavramı: Big-O ve karmaşıklıkların kısa özeti

Algoritmaların performansını konuşurken sıkça Big-O notasyonu kullanılır. Bu, giriş boyutu n büyüdükçe çalışma süresinin yaklaşık nasıl büyüdüğünü anlatır.

• O(n): n iki katına çıkarsa iş miktarı yaklaşık iki katına çıkar.
• O(n²): n iki katına çıkarsa iş miktarı yaklaşık dört katına çıkabilir.
• O(log n): n çok büyüse bile artış yavaştır; “bölerek arama” mantığı.

Bu yazıda karmaşıklık ifadelerini, ilgili algoritmaların yaygın kabul gören tanımlarıyla uyumlu şekilde kullanıyoruz (ör. bubble sort için O(n²), binary search için O(log n)).

Uzay (space) karmaşıklığı notu

• Bubble sort: Tipik uygulamada ek bellek ihtiyacı sabittir (auxiliary/extra space). Kaynak
• Binary search (iteratif): Döngülü sürüm de sabit ek bellekle çalışır. Kaynak

1) Bubble Sort: Mantık, adımlar, karmaşıklık

Bubble sort ne yapar?

Bubble sort, diziyi birden çok turda dolaşır. Yan yana duran iki öğe yanlış sıradaysa yer değiştirir. Büyük öğeler her turda sağa doğru “yüzdüğü” için bu adı alır. Tanım, stabilite ve karmaşıklık özetleri için: Bubble sort (Wikipedia).

Zaman karmaşıklığı ve stabilite

• Ortalama ve en kötü durum: Bubble sort için yaygın olarak O(n²) kabul edilir. Kaynak
• Stabilite: Bubble sort stabil bir sıralama algoritmasıdır; yani eşit anahtarlı öğelerin göreli sırası korunur. Kaynak

“Stabil sıralama” özellikle şu gibi durumlarda önemlidir: Öğrencilerin puanını sıralarken, puanı aynı olanları kayıt sırasına göre korumak isteyebilirsiniz.

Örnek: Python ile bubble sort

Aşağıdaki örnek, listeyi kopyalayıp sıralar (orijinal listeyi bozmamak için). Eğitim amaçlı netlik hedeflenmiştir.

Python (bubble sort)
def bubble_sort(arr):
  a = arr[:] # kopya
  n = len(a)
  for i in range(n):
    for j in range(0, n - 1 - i):
      if a[j] > a[j + 1]:
        a[j], a[j + 1] = a[j + 1], a[j]
  return a

Bu sürüm her turda sağ taraftaki en büyük değeri “yerine oturtur”; bu yüzden iç döngü aralığı n - 1 - i ile kısalır.

Erken çıkış optimizasyonu (en iyi durumda daha hızlı)

Liste zaten sıralıysa, normal bubble sort yine de iç içe döngüleri çalıştırır. Sık kullanılan bir iyileştirme: Bir turda hiç yer değiştirme olmadıysa algoritmayı erken bitirmek. Bu yaklaşım pratik anlatımlarda sık geçer. Örnek ve açıklama için: GeeksforGeeks — Bubble Sort.

Python (erken çıkışlı bubble sort)
def bubble_sort_early_exit(arr):
  a = arr[:]
  n = len(a)
  for i in range(n):
    swapped = False
    for j in range(0, n - 1 - i):
      if a[j] > a[j + 1]:
        a[j], a[j + 1] = a[j + 1], a[j]
        swapped = True
    if not swapped:
      break
  return a

Ne zaman bubble sort kullanılır?

• Öğrenme amaçlı: Döngüler, karşılaştırma, swap ve temel karmaşıklık sezgisi öğretir.
• Çok küçük veri: Basitlik bazen yeterli olabilir; ancak bu bir performans garantisi değildir.
• Üretimde çoğu zaman değil: Büyük listelerde genellikle standart kütüphanelerdeki sıralama fonksiyonları tercih edilir. Bu tür “yerleşik sıralama” tercihinin pratik gerekçeleri algoritma derslerinde sık konuşulur. MIT OCW 6.006

2) Binary Search: Sıralı dizide hızlı arama

Binary search ne zaman çalışır?

Binary search (ikili arama), yalnızca sıralı bir dizide doğru şekilde uygulanabilir. Mantık: Orta elemanı kontrol eder, hedef daha küçükse sol yarıya, büyükse sağ yarıya geçer. Bu sayede arama alanı her adımda yarıya iner. Tanım ve karmaşıklık özeti: Binary search (Wikipedia).

• Zaman karmaşıklığı: Tipik olarak O(log n). Kaynak
• Ön koşul: Girdi dizisi sıralı olmalı. Kaynak

İteratif (döngülü) binary search: Daha az sınır şaşırtmacası için şablon

Binary search’te en sık sorun yaşanan yerler sınır indeksleridir. Kaynaklar, farklı pseudocode varyantlarının karışıklık yaratabildiğini ve sınır durumlarda “off-by-one” türü hataların yaygın olduğunu tartışır. Kaynak

Aşağıdaki şablon, aralığı inclusive (her iki uç dahil) tutar: low ve high ikisi de geçerli indeks olabilir.

Python (iteratif binary search, index döndürür)
def binary_search(a, target):
  low = 0
  high = len(a) - 1
  while low <= high:
    mid = (low + high) // 2
    if a[mid] == target:
      return mid
    elif a[mid] < target:
      low = mid + 1
    else:
      high = mid - 1
  return -1

Bu fonksiyon hedef bulunamazsa -1 döndürür. İsterseniz bu davranışı dilinize uygun şekilde None veya özel bir sonuç nesnesiyle de ifade edebilirsiniz.

JavaScript örneği

JavaScript (iteratif binary search)
function binarySearch(a, target) {
  let low = 0;
  let high = a.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (a[mid] === target) return mid;
    if (a[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

Java örneği

Java (iteratif binary search)
static int binarySearch(int[] a, int target) {
  int low = 0;
  int high = a.length - 1;
  while (low <= high) {
    int mid = low + (high - low) / 2; // bazı ortamlarda taşma riskini azaltmak için yaygın kalıp
    if (a[mid] == target) return mid;
    if (a[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

Not: Orta indeksin hesaplanması, bazı dillerde/ortamlarda “uygulama tuzağı” olarak tartışılır; bu yüzden low + (high - low) / 2 kalıbı sık kullanılan bir alternatiftir. Binary search (Wikipedia)

Sınır durumlarını yakalamak için test listesi

Binary search’in hassas noktası genellikle aralık güncellemeleridir. Aşağıdaki test senaryoları, sınır sorunlarını yakalamaya yardımcı olur: Binary search (Wikipedia).

• Boş dizi: [] içinde arama.
• Tek eleman: [5] içinde 5 ve 3 arama.
• İki eleman: [3, 10] içinde 3 ve 10 arama.
• İlk ve son eleman: Hedef en başta veya en sonda.
• Bulunmayan hedef: Arada kalacak bir değer (örn. [1, 4, 8] içinde 6).
• Tekrarlı değerler: [1, 2, 2, 2, 3] içinde 2 arama (hangi indeks döneceğinizi önceden tanımlayın).

Bubble sort vs binary search: Ne zaman hangisi?

Bu iki algoritma farklı sorunları çözer: biri sıralar, diğeri (sıralıysa) arar. Yine de pratikte sık birlikte kullanılır: Önce veriyi sıralar, sonra birçok arama yaparsınız.

Pratik ipuçları: Daha okunabilir örnek kodlar

1) Sıralı olma şartını açık yazın

Binary search fonksiyonunuzun docstring/yorum satırında “girdi sıralı olmalıdır” notunu mutlaka belirtin. Bu, algoritmanın tanımı gereği bir ön koşuldur. Kaynak

2) Dönüş değerini standardize edin

Bulunamadığında ne döndüreceğinizi netleştirin:

• İndeks döndüren fonksiyon: bulunamadığında -1.
• Bool döndüren fonksiyon: true/false.
• Konum döndüren fonksiyon: ek olarak “ekleme noktası” (insertion point) gibi daha gelişmiş sözleşmeler.

Bu yazıdaki örnekler, basitlik için indeks veya -1 yaklaşımını kullanıyor.

3) Yerleşik sıralamayı tanıyın (pratikte çoğu zaman daha iyi)

Gerçek uygulamalarda performans, bakım kolaylığı ve köşeli durumlar açısından çoğu dilin standart kütüphanesindeki sıralama fonksiyonları tercih edilir. Bubble sort ise daha çok kavram öğretmek için kullanılır. Bu ayrımın algoritma eğitiminde yaygın oluşu için MIT’nin ders materyallerine göz atabilirsiniz: MIT OCW 6.006.

4) Kısa kontrol listesi

• Binary search çağırmadan önce: “Liste sıralı mı?”
• low/high güncellemeleri: mid’in kendisini aralıktan çıkarıyor musunuz? (mid+1 / mid-1)
• Döngü koşulu: inclusive aralıkta low <= high kullanıyor musunuz?
• Testler: boş/tek/iki eleman + ilk/son + bulunmayan hedef.
• Bubble sort: performans hedefi varsa yerleşik sort’u değerlendirdiniz mi?

Sonuç

Bubble sort ve binary search, algoritmik düşünmenin iki temel örneğidir: biri basit karşılaştırma ve yer değiştirme ile sıralama yapar; diğeri sıralı veride arama alanını yarıya indirerek hız kazanır. Bubble sort’un O(n²) yapısı nedeniyle büyük listelerde genellikle uygun olmadığı; binary search’in ise sıralı girdi şartıyla O(log n) çalıştığı temel çıkarımlardır. Detay ve tanımlar için referanslar: Bubble sort, Binary search, ayrıca örnek/optimizasyon anlatımı için GeeksforGeeks.

Bu temeller oturduğunda, bir sonraki adım olarak daha verimli sıralamalar (ör. merge sort/quick sort) ve “binary search ile ilk/son görülen indeks bulma” gibi varyasyonlara geçmek çok daha kolay olur.