3 Kasım 2019 Pazar

C Programlama MergeSort

Merge Sort Nasıl Çalışır?

Divide and Conquer yaklaşımının en temel örneklerinden biri olan Merge Sort, sıralayacağımız diziyi her seferinde ikiye bölüp ayrı ayrı sıraladıktan sonra birleştirme mantığına dayanmaktadır. Biraz daha ayrıntılı anlatmam gerekirse: Algoritmamız iki fonksiyondan oluşuyor. Birincisi girilen diziyi ikiye bölüp ayrı ayrı sıralamayı sağlarken diğeri sıralanmış iki diziyi birleştirmemizi sağlıyor.
Kaba bir kod paylaştıktan sonra algoritma analizini yapmaya devam edelim.


Merge Sort Analizi

Merge dediğimiz fonksiyon kendi içinde sıralanmış L[] ve R[] dizilerini birleştiriyor. Ancak burdaki önemli ayrıntı dizileri birleştirirken sıralama bozulmadan birleşiyor. Yani merge fonksiyonu tamamlandığında L[] ve R[] dizilerinin toplam uzunluğunda sıralı bir dizi oluşuyor. Nasıl birleştirdiği hakkında elimden geldiğince açıklamaya çalışayım.
Birleştirme işleminin 3 while döngüsüyle yapan Merge fonksiyonu, 1. while döngüsünde L ve R dizisini beraber gezerek öncelikli olarak küçük elemanı cevabımızın saklandığı arr dizisine atıyor. Daha sonra elimizde fazladan L veya R dizisinde eleman kalmış olabilir ancak biz biliyoruz ki 1. while tamamlanınca L ve R dizilerinden en az birisi tamamen gezilmiş ve cevaba aktarılmıştır. Eğer L dizisinde fazlalık kaldıyse 2. while kalan bütün L dizisini cevaba aktarıyor. Aynı şekilde R dizisinde eleman kaldıyse 3. while R’nin tamamının cevaba atıyor. Böylelikle merge fonksiyonu tamamlandığında L ve R dizisi sıralı bir şekilde arr dizisinde birleşmiş oluyor.
Mergesort fonksiyonundan bahsetmek gerekirse, her seferinde gelen dizinin önce ilk yarısını sıralıyor daha sonra ikinci yarısını sıralıyor. Böylelikle elinde iki tane sıralı dizi oluyor. Daha sonra az önce anlattığımız Merge fonksiyonunu kullanarak bu iki sıralı diziyi doğru bir şekilde birleştiriyor.
 Karmaşıklık Hesabı
Bu özyinelemeli (recursive) bir fonksiyon olduğu için sürekli kendini çağırarak hep diziyi ikiye bölüyor. Böylelikle en fazla log2(N) kere bölme işlemi yapılmış oluyor. Her bölünmüş dizinin Merge işlemi içinde dizinin uzunluğu olan N işlem yapıldığı için bu algoritmanın karmaşıklık maliyeti büyük O notasyonunda O(N * log(N)) oluyor. Önceki gördüğümüz sıralama algoritmalarına nazaran çok daha verimli olan Merge sort sayesinde çok kısa sürede 1 000 000 uzunluğundaki dizileri bile sıralayabiliyoruz.

Hiç yorum yok:

Yorum Gönder