C Programlama #26 | Dizileri Sıralamak: Kabarcık Sıralaması

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

Sınıf fotoğrafı için altı öğrenci boy sırasına dizilecek. Yirmi altıncı derste bir diziyi sıralayan ilk algoritmayı, kabarcık sıralamasını adım adım kuruyor, iki iyileştirmesini ve neden yavaş olduğunu görüyoruz. Boylar 172, 165, 180, 158, 176 ve 169; kabarcik fonksiyonu diziyi alıyor ve dönünce dizi 158, 165, 169, 172, 176, 180 sırasında. Fonksiyon yalnızca iki iş yapıyor: yan yana iki elemanı karşılaştırmak ve sıraları yanlışsa yerlerini değiştirmek. Önce yer değiştirmenin kendisi: a = b; b = a; yazınca lldb izi ikisinin de 165 olduğunu gösteriyor, 172 kayboluyor. Çözüm üçüncü bir değişken: gecici önce 172'yi saklıyor, sonra c 165'i, en son d saklanan 172'yi alıyor. Birinci turu ikili ikili izliyoruz: 172 ile 165 yer değiştirir, 172 ile 180 kalır, 180 sırayla 158, 176 ve 169 ile yer değiştirir; altı elemanda beş karşılaştırma sonunda en büyük değer, 180, bir kabarcık gibi sona yükselir. Büyük bir değer tek turda birçok adım ilerlerken 158 gibi küçük bir değer en fazla bir adım geri gelir. Üçüncü turdan sonra dizi sıralı ama temel algoritma bunu bilmiyor: beş tur, her turda beş karşılaştırma, 5 · 5 = 25 karşılaştırma ve yalnızca 4 + 2 + 2 = 8 yer değiştirme. İki iyileştirme: her tur sonda bir elemanı yerine koyduğu için iç döngü kısalır (5 + 4 + 3 + 2 + 1 = 15), yer değiştirme olmayan turda durulur (bayrak degisti; 5 + 4 + 3 + 2 = 14). En kötü durum ters sıralı dizidir: n eleman için n · (n - 1) / 2 karşılaştırma; 10 eleman için 10 · 9 = 90, 90 / 2 = 45; 100 eleman için 4950; 1000 eleman için 499500; 10 bin eleman için yaklaşık 50 milyon. Eleman sayısı 10 kat artınca iş yaklaşık 100 kat artıyor. Ekrandaki her çıktı, kodun gerçekten derlenip çalıştırılmasından geliyor. Bu derste: 1. İki değeri yer değiştirmek: neden üçüncü bir değişken gerekir (lldb izi) 2. Birinci tur: komşu çiftler, en büyük değer sona yükselir 3. Tur tur sıralama: 25 karşılaştırma, 8 yer değiştirme 4. İki iyileştirme: kısalan iç döngü (15) ve erken durma (14) 5. Neden yavaş: ters sıralı dizide n · (n - 1) / 2 karşılaştırma Bölümler: 0:00 Dizileri sıralamak 0:16 Sınıf fotoğrafı: boy sırası 0:49 İki değeri yer değiştirmek 1:35 Birinci tur 2:28 Tur tur 3:10 İki iyileştirme 3:51 Kolay ama yavaş 4:37 Bugünün dört kuralı 5:02 Sonraki ders: ortalama, medyan, mod Kaynak kitap: Paul Deitel, Harvey Deitel — C How to Program, 9. baskı (2022), §6.8. Konu sırası ve kavramlar kaynak kitaptan izlenir; anlatım, örnekler ve ekranlar özgündür. Hedef kitle: C'ye yeni başlayan tüm mühendislik ve bilgisayar/yazılım öğrencileri. Ön koşul: C Programlama #01–#25.

Bu videoyu izlemek için Premium üyelik gerekir.