Başlangıç algoritmaları: Bubble sort ve binary search (örnek kodlar)

Giriş

Temel algoritmalar, programlamanın yapı taşlarıdır. Bu yazıda iki temel algoritma — bubble sort (sıralama) ve binary search (arama) — ele alınacaktır. Bubble sort, ardışık elemanları karşılaştırıp gerektiğinde takas yaparak diziyi sıralarken; binary search sıralanmış dizilerde hedef elemanı hızlıca bulmak için arama alanını yarıya indirir. Tanımlar ve kısa açıklamalar için kaynaklara bakabilirsiniz: Bubble Sort — Davut Kara ve Algoritmalar İnteraktif Öğrenme Platformu (sıralama ve arama).

Bubble Sort: Tanım ve çalışma prensibi

Temel fikir

Bubble sort, dizideki komşu (ardışık) elemanları karşılaştırır ve doğru sırada değilse yerlerini değiştirir. Bu karşılaştırma-takas işlemi, dizinin sonuna kadar tekrarlanır; her geçiş (pass) sonunda en büyük eleman dizinin sonuna "kabarcık" gibi yükselir. Bu temel tanım için kaynak: Davut Kara - Bubble Sort ve adım adım açıklamalar için örnek rehberler mevcuttur.

Adım adım örnek

Başlangıç dizisi: [5, 2, 1, 4, 3]

1. Pass 1: karşılaştırmalar sonucu dizi → [2, 1, 4, 3, 5]
2. Pass 2: dizi → [1, 2, 3, 4, 5]
3. Pass 3: zaten sıralı olduğu için değişiklik olmaz (optimizasyonla erken çıkılabilir).

Python örneği (optimize edilmiş)

Python örneği:
def bubble_sort(a):
n = len(a)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
swapped = True
if not swapped:
break
return a

Zaman ve mekan karmaşıklığı

Genel olarak bubble sort'un zaman karmaşıklığı ortalama ve kötü durumda O(n^2)'dir; en iyi durumda (dizi zaten sıralı ve erken çıkış kullanılıyorsa) O(n) olabilir. Bellek kullanımı (mekan karmaşıklığı) sabittir, O(1), çünkü sıralama yerinde gerçekleştirilir. Bu tip karmaşıklık değerlendirmeleri ve karşılaştırmalar için kaynak: Algopit - Sıralama Algoritmaları.

Avantajlar ve dezavantajlar

• Avantajlar: Çok basit ve anlaşılır; küçük dizilerde veya eğitim amaçlı kullanılabilir.
• Dezavantajlar: Büyük veri setlerinde verimsizdir (O(n^2)). Daha verimli sıralama algoritmaları tercih edilir.

Binary Search: Tanım ve çalışması

Önkoşul

Binary search, yalnızca sıralanmış dizilerde (veya sıralanmış veri yapılarına erişimde) doğru çalışır. Ortadaki elemanla hedef karşılaştırılır; hedef daha küçükse sağ yarı atlanır, daha büyükse sol yarı atlanır; arama alanı yarıya indirilir. Bu çalışma şekli ve faydaları hakkında genel referans: Algopit - Arama ve Sıralama.

Iteratif Python örneği

Python (iteratif):
def binary_search(a, target):
low, high = 0, len(a) - 1
while low <= high:
mid = (low + high) // 2
if a[mid] == target:
return mid # bulundu — indeks döner
elif a[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1 # bulunamadı

Rekürsif Python örneği

Python (rekürsif):
def binary_search_recursive(a, target, low, high):
if low > high:
return -1
mid = (low + high) // 2
if a[mid] == target:
return mid
elif a[mid] < target:
return binary_search_recursive(a, target, mid + 1, high)
else:
return binary_search_recursive(a, target, low, mid - 1)

Zaman ve mekan karmaşıklığı

Binary search'un zaman karmaşıklığı O(log n) olarak bilinir; arama alanı her adımda yarıya indirildiği için boyut logaritmik şekilde azalır. Mekan karmaşıklığı iteratif sürüm için O(1), rekürsif sürüm için çağrı yığını nedeniyle O(log n) seviyesinde olabilir. Bu karmaşıklık bilgileri için kaynak: Algopit.

Yaygın hatalar ve düzeltme ipuçları

• Dizi sıralı değilse binary search yanlış sonuç verir — her zaman verinin sıralı olduğundan emin olun.
• Indeks aralıkları (low/high) yanlış ayarlanırsa off-by-one (bir eksik/fazla) hataları çıkar; test veyahut açık sınır kuralları kullanın ([low, high] vs [low, high)).
• Rekürsif versiyonda üst sınırların doğru geçildiğinden ve çıkış koşullarının iyi belirlendiğinden emin olun.

Bubble Sort ve Binary Search: Karşılaştırma (aynı amaçta değiller)

Önemli not: Bubble sort bir sıralama algoritmasıdır; binary search ise bir arama algoritmasıdır. Bu yüzden doğrudan "hangisi daha iyi?" sorusu anlamsız olabilir. Karşılaştırma yapılacaksa amaç ve bağlam düşünülmelidir:

• Bubble sort: Küçük veri setlerini sıralamak ve eğitim amaçlı kullanışlıdır. Zaman karmaşıklığı O(n^2) olduğundan büyük veriler için önerilmez (Algopit, Davut Kara).
• Binary search: Sıralı bir veri üzerinde hızlı arama yapmak için uygundur; arama maliyeti O(log n)'dir.

Pratik öneriler, kontrol listesi ve alıştırmalar

Kısa kontrol listesi (başlarken)

• Veri sıralı mı? Değilse önce sıralamayı düşünün veya başka bir arama yöntemi kullanın.
• Veri boyutu nedir? Küçükse basit algoritmalar yeterli olabilir; büyükse daha verimli yöntemlere bakın.
• Yerinde sıralama mı isteniyor? Bellek kısıtları var mı?
• Test yazın: Kenar durumları (boş dizi, tek eleman, hedef bulunmayan durum) için test ekleyin.

Pratik alıştırmalar

1. Bubble sort fonksiyonunuzu farklı uzunluklarda rasgele dizilerle çalıştırıp çalışma süresini ölçün.
2. Sıralı bir dizi üzerinde hem iteratif hem rekürsif binary search yazın ve davranışlarını karşılaştırın.
3. Off-by-one hatasını test etmek için sınır değerler (ilk/son eleman) ile testler oluşturun.

Sonuç

Bubble sort ve binary search, programlama öğreniminin ilk adımlarında sık karşılaşılan iki temel kavramdır. Bubble sort sıralama mantığını basitçe gösterir; binary search ise sıralanmış verilerde verimli arama yapmanın örneğidir. Karmaşıklık analizleri ve kullanım önerileri için rehber kaynaklar: Davut Kara - Bubble Sort ve Algopit. Başlangıç seviyesindeyseniz, hem kodu elle çalıştırarak adımları takip etmek hem de küçük testler yazarak doğruluğu kontrol etmek öğrenmeyi hızlandırır.

Kaynaklar: Davut Kara (Bubble Sort) ve Algopit (Sıralama ve Arama algoritmaları) referans alınmıştır.