Birer Birer Kontrol Etme
Doğrusal Arama: Hepsini Tek Tek Kontrol Et
Düşün ki 10 kart ters yatmış, 1'den 10'a kadar numaralandırılmış, rastgele sıralanmış.
7 numaralı kartı bulmak istiyorsun.
Bulana kadar kartları birer birer, soldan sağa çevirirsin.
| Senaryo | Gerekli Çevirme Sayısı |
|---|---|
| En iyi durum | 1 çevirme (şanslı ilk deneme!) |
| En kötü durum | 10 çevirme (son kartti) |
| Ortalama | yaklaşık 5 çevirme |
Şimdi 100 kart hayal et. Ortalama: yaklaşık 50 çevirme.
1.000 kart? Ortalama: yaklaşık 500 çevirme.
Deseni görüyor musun? Kartları iki katına çıkart, işi iki katına çıkart. İş düz bir çizgide büyür.
Bilgisayar bilimciler buna doğrusal arama diyorlar — doğrusal, işin bir çizgi gibi büyümesi anlamına gelir: sabit & tahmin edilebilir.
Doğrusal arama HERHANGİ bir listede çalışır, sıralı olsun ya da olmasın. Bu onu basit yapar. Ama yavaş olabilir.
Kaç Ad?
Rastgele sırada yazılmış 20 adlı bir sınıf listeniz var.
Zoe adını bulmak gerekiyor.
Adları birer birer, listenin başından aşağıya doğru kontrol edersin.
Listeyi Yarıya Böl
İkili Arama: Ortaya Atla
İkili aramanın bir kuralı vardır: liste önce sıralanmalıdır.
20 adlı listeniz A'dan Z'ye gidiyorsa, ikili arama kullanabilirsiniz.
Nasıl çalışır: ortadaki ada aç (ad #10). Sor: Zoe bu addan önce mi yoksa sonra mı?
Z alfabenin sonuna yakın gelir, bu yüzden Zoe ortanın SONRASINDA gelir. İlk yarıyı at. Şimdi sadece 11-20 adları kaldı.
Bu 10 adın ortasını kontrol et (ad #15). Z, M'den sonra gelir, bu yüzden Zoe ad #15'ten sonra gelir. 11-14 adlarını at. Şimdi 16-20 adları var.
Yarıya kesmeye devam et. Her kontrol kalan adların yarısını kaldırır.
| Liste Boyutu | İkili Arama ile En Fazla Kontrol |
|---|---|
| 20 ad | en fazla 5 kontrol |
| 1.000 ad | en fazla 10 kontrol |
| 1.000.000 ad | en fazla 20 kontrol |
Bunu 1.000.000 adla doğrusal arama ile karşılaştır: ortalama 500.000 kontrol.
İkili arama listeyi her seferinde yarıya keser. Yarıya kesmeyi tekrar tekrar yapmak 1'e çok hızlı ulaşır — bu yüzden bu kadar hızlı kalır.
Sıralanmış Listede 'incir' Bul
İşte 8 kelimeli sıralanmış bir liste:
1. elma 2. muz 3. kiraz 4. hurma 5. mürver meyvesi 6. incir 7. üzüm 8. kavun
İkili arama kullanarak incir'i bulmak istiyorsun.
Hatırla: ortayı kontrol et, hedefinin önce mi sonra mı olduğunu sor, sonra listeyi yarıya böl.
Komşuları Sırayla Değiştir
Kabarcık Sıralaması: Komşuları Karşılaştır & Değiştir
Kabarcık sıralaması, bir seferde iki komşu öğeyi karşılaştırarak listeyi sıraya koyar.
İki komşu yanlış sıradaysa — onları değiştir.
Hiçbir şeyin değiştirilmesi gerekene kadar listenin içinden geçmeye devam et.
Örnek: [5, 3, 8, 1] sırala
Geçiş 1:
- 5 ve 3'ü karşılaştır. 5 > 3, bu yüzden değiştir → [3, 5, 8, 1]
- 5 ve 8'i karşılaştır. 5 < 8, değiştirme yok → [3, 5, 8, 1]
- 8 ve 1'i karşılaştır. 8 > 1, bu yüzden değiştir → [3, 5, 1, 8]
Geçiş 2:
- 3 ve 5'i karşılaştır. Tamam → [3, 5, 1, 8]
- 5 ve 1'i karşılaştır. 5 > 1, değiştir → [3, 1, 5, 8]
- 5 ve 8'i karşılaştır. Tamam → [3, 1, 5, 8]
Geçiş 3:
- 3 ve 1'i karşılaştır. 3 > 1, değiştir → [1, 3, 5, 8]
- 3 ve 5'i karşılaştır. Tamam. 5 ve 8'i karşılaştır. Tamam.
Bitti! [1, 3, 5, 8] ✓
Fark et: en büyük sayı her geçişte listenin sonuna kabarcık gibi ulaşır. Kabarcık sıralaması adını böyle alır.
Kabarcık sıralaması işe yarar. Büyük listeler için en hızlı değildir, ama anlaması kolaydır — öğrenmek için mükemmeldir.
Kabarcık Sıralaması ile [4, 2, 7, 1] Sırala
Kabarcık sıralaması kullanarak bu listeyi sırala: [4, 2, 7, 1]
Her geçişten sonra listeyi göster. Bitirmek için kaç geçiş gerektiğini say.