Nasıl Sıralama Analizi Yapılmaz

Veri Yapıları ve Algoritmalar (COMP231) dersinin bu haftaki projesinde sıralama algoritmalarının implementasyonu ve analizi yapılması istendi. Proje Quick sort ile beraber ders kitabı olarak kullandığımız Cormen’in Introduction to Algorithms kitabındaki Merge sort algoritmasının yazımını bize bırakmış ve Insertion sort ile beraber birtakım yardımcı fonksiyonları hazır olarak vermişti.

Güzel bir pazar günü başlangıcında quick sort’u yazıp diğer kısımlarını akşama bırakmış idim. Sanırım eğlence akşam vaktini bu işe ayırmamla başladı. Gece 10.30 – 3.30 arası Cormen’in Merge sort algoritmasını yazmakla,  toplamda 4 tane algoritmanın analizini yapıp anlamlı veri elde eden programcığı yazmakla ve gnuplot öğrenmekle geçti. Sonunda gnuplot ile sonucu elde ettim ancak twitter’da bahsettiğim üzere bir problem vardı. Gecenin o vaktinde artık ekrana bakacak halim kalmadığı ve proje teslimine 5 saat kaldığı için projenin o hali ile gönderip sabah labda bakmaya karar verdim.

Sabah problemi reb’e söylemem ile beraber durumun hocaların bulunduğu e-posta listesine atılması bir oldu :) Şimdi bulduğum sonucu ve olması gereken sonucu yan yana koyalım.

İlk analizde görüyoruz ki harika bir gariplikte O(n^2) çalışması gereken insertion sort O(n) çalışmakta. Normalde O(n . lgn) çalışması gereken merge sort neredeyse O(n^2) çalışıyor gibi görünüyor.

Tabi ki hata bu veriyi üreten kodda meydana geliyor. Sıralama algoritmalarının çalışmasında herhangi bir sıkıntı mevcut değil. Sakin kafa ile düşününce anlıyoruz ki durum tamamiyle mutation, yani bir dizinin (array) ortak kullanımından kaynaklanıyor. Alınan kahve oranı ve gecenin ilerleyen saatleri ile yazılan kod kalitesi arasında bir ilişki olabileceğini düşünürsek ilk veriyi üreten kodun kirli bir biçimde yazıldığına şaşırmamak gerek. Kod tek bir liste alıp o liste üzerinde tek tek sıralama algoritmalarını çalıştırıyor. Yani ilk sıralamadan sonra elimizde sıralı bir liste oluyor ve devamındaki 3 algoritma sıralı liste üzerinde sonuç veriyor. Durum böyle olunca, insertion sort çalışması gereken bir biçimde sıralı liste üzerinde O(n) zamanda çalışıyor. Merge sort sıralanmamış liste üzreinde ilk olarak çalıştırıldığı için onun dışındaki diğer algoritmalar da aynı şekilde sıralı listeler üzerinde sonuç veriyor.

Sabah veri üreten programığı düzgün bir biçimde yazdıktan sonra doğru olan yukarıdaki sonuçları elde ettim. Sağda görüldüğü üzere insertion sort O(n^2) zamanda çalışıyor ve diğer algoritmalar yok denecek kadar az bir sürede işlemi tamamlıyor. Soldaki grafikte ise kalan algoritmaların analizi mevcut. Görüldüğü gibi 25.000.000 elemanlı listeye kadar analizi mevcut ki bu kadar büyük bir rakamda insertion sort’u beklemek çok uzun süreceği için çıkarmak zorunda kaldım.

Yanlış veriyi üreten programcığı buradan görebilirsiniz. Farkedeceğiniz üzere getAnalysis metodu tek bir liste üzerinde işlem yapmakta. Düzgün ve temiz haline ise buradan ulaşılabilir. getAnalysis artık bir metod ve liste alarak, önce listeyi kopyalıyor, ardından da zamanı döndürüyor. Bu işlemi 4 algoritma için tekrarlayıp zamanlarını aldıktan sonra dosyaya yazdırıyorum.

Ne öğrendim? 

Temel olarak yorgunken bir problemin içinden çıkılamadığında dinlenilmesi gerektiğini öğrendim. İşin teknik kısmında ise mutation konusunda dikkatli olunması gerektiğini, sıralama algoritmalarının nasıl davrandığını düzgün bir biçimde aklımda yazdım. Tabi sonucunda bölüm içerisinde eğlence konusu olmam ve “Eren The Sorter” olarak adlandırılmamın kaçışı olmadı :)

Not: Grafikleri geç bir saatte oluşturduğum için yazım yanlışı yaptım. Grafiklerin sadece başlığının düzeltilmiş hali ile uğraşacak ve görselleri tekrar yükleyecek gücü bulamadığım için grafikleri okurken comprasion kelimesini comparison şeklinde okumanızı rica ediyorum efem.