Algoritmaların Tasarımı ve Analizi #05 | Hızlı Sıralama ve Bölme

Eğitmen: Dr. Süleyman Burak ÇELİK

Geçen derste birleştirmeli sıralamada iki düzenli parçanın önündeki değerleri karşılaştırıp tek bir çıktı oluşturduk. Bugün hızlı sıralamayı inceleyeceğiz. Yine küçük problemlere başvuracağız, fakat bu kez asıl işi küçük çağrılardan önce, diziyi bölme aşamasında yapacağız. Dayanak, korunan bölgeler ve denge. Algoritmaların çalışma adımlarını gerçek konuşmayla eşleşen şemalar ve özgün örneklerle adım adım inceliyoruz. Bu derste: 1. Tararken üç bölgeyi ayır 2. İlk üç değer: 7, 2 ve 6 3. Kalan tarama ve dayanağın yerleşmesi 4. Bölme tamam; sıralama henüz tamam değil 5. Bölmenin doğruluğunu ayrı kanıtla 6. Boş parçalar hata değildir 7. Denge, toplam işi belirler 8. Eşit değerler de dengesizlik yaratabilir 9. Sıra sizde: bölme sonucu mu, tam sıra mı? Bölümler: 0:00 Hızlı sıralama: önce doğru böl 0:55 Dayanak, karşılaştırma eşiğimizdir 1:51 Tararken üç bölgeyi ayır 2:45 İlk üç değer: 7, 2 ve 6 3:35 Kalan tarama ve dayanağın yerleşmesi 4:32 Bölme tamam; sıralama henüz tamam değil 5:27 Bölmenin doğruluğunu ayrı kanıtla 6:20 Boş parçalar hata değildir 7:12 Denge, toplam işi belirler 8:10 Eşit değerler de dengesizlik yaratabilir 9:06 Sıra sizde: bölme sonucu mu, tam sıra mı? 10:06 İki yöntem, aynı böl ve yönet fikri 11:00 Doğru bölme ile iyi dengeyi ayır Kaynak kitap: Jeff Erickson — Algorithms, 1. baskı (2019, CC BY 4.0), §1.5–1.6. Kavram ve konu sırası kaynak kitaptan izlenir; anlatım, şemalar ve sayısal örnekler özgündür. Ekrandaki sayılar açık varsayımlı öğretim modelleridir; gerçek cihaz ölçümü değildir. Kitap: https://jeffe.cs.illinois.edu/teaching/algorithms/ (yasal ve ücretsiz kaynak). Hedef kitle: bilgisayar mühendisliği ve yazılım öğrencileri.