Algoritma verimliliği ve adım sayısı; doğrusal (sıralı) arama ve ikili arama (sıralı listede yarıya bölme); sıralama algoritmaları: kabarcık (bubble) sıralama ve seçmeli (selection) sıralama; adım adım izleme; algoritma karmaşıklığına giriş (n, log n, n²); gerçek hayatta arama ve sıralama (sözlük, rehber, arama motorları).
Doğrusal arama ve ikili arama
Doğrusal (sıralı) arama: Listenin başından başlayarak elemanları tek tek kontrol eder.
- Liste sıralı olmak zorunda değil.
- En kötü durumda n adım (1 milyon elemanda 1 milyon kontrol)
İkili arama (binary search): Sıralı listede ortadaki elemana bakar; aranan küçükse sol yarıda, büyükse sağ yarıda devam eder.
- Her adımda arama alanı yarıya iner.
- 1000 elemanda en fazla yaklaşık 10, 1 milyon elemanda yaklaşık 20 adım!
- ⚠️ Liste sıralı olmalıdır.
Örnek: [3, 8, 12, 17, 21, 25, 30, 34, 41] listesinde 30’u ara:
- Orta = 21 → 30 > 21 → sağ yarı [25, 30, 34, 41]
- Orta = 30 → bulundu (2 adım; doğrusal aramada 7 adım)
Sıralama algoritmaları
Kabarcık sıralama (bubble sort): Yan yana iki elemanı karşılaştırır, sıra yanlışsa yer değiştirir; her turda en büyük eleman sona “kabarcık gibi” çıkar.
[5, 3, 8, 1] →
- 1. tur: (5,3) değiş → [3,5,8,1] · (5,8) kalır · (8,1) değiş → [3,5,1,8]
- 2. tur: (3,5) kalır · (5,1) değiş → [3,1,5,8]
- 3. tur: (3,1) değiş → [1,3,5,8]
Seçmeli sıralama (selection sort): Listedeki en küçük elemanı bulup başa yerleştirir; kalan kısım için tekrarlar.
[5, 3, 8, 1] → en küçük 1 başa: [1,3,8,5] → kalanların en küçüğü 3: [1,3,8,5] → 5: [1,3,5,8]
Python’da hazır: liste.sort() veya sorted(liste) (çok daha hızlı algoritmalar kullanır)
| Tur | Liste |
|---|---|
| Başlangıç | 5, 3, 8, 1 |
| 1. tur | 3, 5, 1, 8 |
| 2. tur | 3, 1, 5, 8 |
| 3. tur | 1, 3, 5, 8 |
Algoritma verimliliği
Aynı problemi çözen algoritmalar hız ve bellek bakımından farklıdır. Verimlilik, eleman sayısı (n) arttıkça adım sayısının nasıl arttığına bakılarak karşılaştırılır.
| Algoritma | Yaklaşık adım | n = 1000 için |
|---|---|---|
| İkili arama | log₂ n | ≈ 10 |
| Doğrusal arama | n | 1000 |
| Kabarcık / seçmeli sıralama | n² | ≈ 1 000 000 |
Gerçek hayatta: Sözlükte kelime ararken ortadan açıp sağa-sola gitmek ikili aramaya benzer; arama motorları milyarlarca sayfayı önceden sıralanmış ve dizinlenmiş veride arar.
Kavramlar
- doğrusal arama
- elemanları sırayla kontrol etme
- ikili arama
- sıralı listeyi yarıya bölerek arama
- kabarcık sıralama
- komşuları yer değiştirerek sıralama
- verimlilik
- algoritmanın hız ve bellek kullanımı
- karmaşıklık
- adım sayısının n’e bağlı artışı
- Doğrusal arama: tek tek bakar, n adım, sıralı olması gerekmez
- İkili arama: sıralı listede yarıya bölme, log₂ n adım
- Kabarcık sıralama: komşuları karşılaştırıp yer değiştirme
- Seçmeli sıralama: en küçüğü bulup başa koyma
- Basit sıralamalar yaklaşık n² adım
- Verimlilik n büyüdükçe adım sayısındaki artışla ölçülür
Örnek soru ve çözümü
Grafiğe göre 1000 elemanlı bir listede doğrusal arama ile ikili arama en kötü durumda kaçar adım yapar? Hangisi için ön koşul vardır?
Doğrusal arama 1000, ikili arama yaklaşık 10 adım. İkili arama için listenin sıralı olması gerekir.
Çözümlü örnekler
1. İkili arama hangi tür listede kullanılabilir? Kolay
ÇözümSıralı listede.
2. [2, 9, 4, 7] listesini seçmeli sıralamayla sıralarken ilk turdan sonra liste ne olur? Orta
ÇözümEn küçük eleman 2 zaten başta: [2, 9, 4, 7]; ikinci turda 4 öne gelir: [2, 4, 9, 7].
3. 1 024 elemanlı sıralı bir listede ikili arama en fazla kaç adımda sonuç verir? Neden? Zor
ÇözümYaklaşık 10–11 adım. Her adımda alan yarıya iner: 1024 → 512 → … → 1; 2¹⁰ = 1024.
Sık yapılan hatalar
- Sırasız listede ikili arama yapmaya çalışmak.
- Kabarcık sıralamanın tek turda bittiğini sanmak.
- Küçük listelerde verimliliğin her zaman fark yarattığını düşünmek.
Biliyor muydun?
Bir telefon rehberinde 1 milyon kişi olsa bile ikili aramayla aradığınız kişiyi yaklaşık 20 adımda bulabilirsiniz — tek tek bakmak 1 milyon adım sürerdi!