Böl ve Fethet Algoritması : Merge Sort

Böl ve fethet (Divide and Conquer) algoritmaları, büyük bir problemi daha küçük alt problemlere ayırarak çözüme ulaşan bir yaklaşımdır. Bu algoritmalar genellikle üç aşamadan oluşur:

1. Bölme (Divide): Problem, daha küçük ve yönetilebilir alt problemlere bölünür.
2. Çözme (Conquer): Alt problemler bağımsız olarak çözülür.
3. Birleştirme (Combine): Alt problemlerin çözümleri birleştirilerek ana problemin çözümü elde edilir.

Bu yöntem, özellikle sıralama, arama, matris çarpımı ve en iyi rota hesaplamaları gibi birçok bilgisayar bilimi probleminde etkili bir şekilde kullanılır.

Böl ve Fethet Algoritması ile Maksimum Elemanı Bulma

Bir dizideki en büyük elemanı bulmanın en temel yöntemi O(n²) karmaşıklığa sahip olan çift döngülü karşılaştırma yöntemidir. Ancak, Böl ve Fethet Algoritması kullanılarak bu işlem O(nlogn) veya hatta O(log n) zaman karmaşıklığında gerçekleştirilebilir.

Klasik Yöntem: O(n²) Karmaşıklık

İki iç içe geçmiş döngü kullanarak maksimum elemanı bulmak, her elemanın diğerleriyle karşılaştırılmasını gerektirir:

Bu yöntem verimsizdir, çünkü her eleman gereksiz yere defalarca karşılaştırılır.

Böl ve Fethet Algoritması ile Maksimum Bulma: O(n) Karmaşıklık

Böl ve Fethet Algoritması ile maksimum elemanı bulmanın temel mantığı, diziyi sürekli ikiye bölerek en büyük elemanı belirlemektir. Bu yöntem, T(n) = 2T(n/2) + O(1) rekürans denklemi ile ifade edilir ve O(n) zaman karmaşıklığına sahiptir.

Benzer bir algoritma kullanarak minimum elemanı da bulmak mümkündür. Bu sefer maksimum yerine her alt dizideki minimum eleman döndürülür ve sonuca ulaşılır.

Merge Sıralama Algoritması

Merge Sıralama Algoritması, Böl ve Fethet stratejisini kullanan kararlı ve verimli bir sıralama algoritmasıdır. Algoritmanın temel çalışma prensibi şu şekildedir:

1. Dizi iki eşit parçaya bölünür.
2. Her iki parça ayrı ayrı sıralanır.
3. Sıralı iki parça, birleştirme adımıyla tekrar bir araya getirilerek tam sıralı bir dizi elde edilir.

Bu süreç, dizinin tek elemanlı alt parçalara ayrılmasına kadar devam eder ve daha sonra parçalar sıralanarak birleştirilir.

Merge Sıralama Algoritmasının Çalışma Mantığı

Merge Sıralama Algoritması şu adımları takip etmektedir:

1. Bölme Aşaması:
2. 1. Dizi, ortadan ikiye bölünür.
   2. Bu işlem, dizi tamamen bölünene kadar devam eder.
2. Çözme Aşaması:
3. 1. Tek elemanlı diziler doğal olarak sıralıdır.
   2. Rekürsif (özyineleme) çağrılar tamamlandığında, sıralama işlemi başlar.
3. Birleştirme Aşaması:
4. 1. İki sıralı alt dizi, karşılaştırmalı olarak birleştirilir.
   2. Daha küçük elemanlar önce alınarak sıralı bir yapı oluşturulur.

Merge Sıralama Algoritması adımları örneği

Merge Sıralama Algoritması C++ Kodu

Merge Sıralama Algoritmasının Zaman ve Uzay Karmaşıklığı

Merge Sıralama Algoritmasının en önemli özelliklerinden biri, her durumda O(nlogn) zaman karmaşıklığına sahip olmasıdır.

• En iyi durum (Best Case): O(n log n)
• Ortalama durum (Average Case): O(n log n)
• En kötü durum (Worst Case): O(n log n)

Uzay karmaşıklığı ise O(n) olup, birleştirme aşamasında ek bellek kullanımı gerektirir. Bu nedenle, Merge Sıralama Algoritması genellikle dahili (in-place) sıralama gerektirmeyen büyük veri kümeleri için uygundur.

Merge Sıralama Algoritmasının Zaman Karmaşıklığı Neden O(NlogN)?

Merge Sıralama Algoritması, Böl ve Fethet prensibiyle çalışan bir sıralama algoritmasıdır. Algoritmanın zaman karmaşıklığını anlamak için iki temel aşama incelenmelidir.

1. Bölme Aşaması (Divide)
2. Birleştirme Aşaması (Merge)

1. Bölme Aşaması (Divide) - O(log N)

Merge Sıralama Algoritması, her adımda diziyi ikiye bölerek küçük parçalara ayırır.

• İlk aşamada dizimiz N elemanlıdır.
• Sonraki aşamada ikiye bölünerek N/2 büyüklüğünde 2 dizi oluşur.
• Daha sonra her biri N/4 elemanlı 4 diziye bölünür.

Bu süreç tek bir eleman kalana kadar devam eder. Bir diziyi sürekli ikiye bölündüğünde bu işlem logN derinliğine ulaşır.

Örneğin:

Eğer dizi 8 elemanlıysa, bölme aşamaları şu şekildedir:

1. 8 eleman → 4 eleman → 2 eleman → 1 eleman (4 seviye)
2. Genel durumda: log₂(N) seviye olur

Bu nedenle, bölme aşaması O(log N) zaman alır.

2. Birleştirme Aşaması (Merge) - O(N)

Bölme işlemi tamamlandıktan sonra, her bir alt dizi sıralanarak birleştirilir.

• İlk aşamada tek tek sıralı olan elemanlar birleştirilir → O(N) sürede yapılır.
• İkinci aşamada daha büyük diziler birleştirilir, yine toplam O(N) işlem yapılır.

Tüm seviyelerde toplam O(N) işlem yapılır.

Merge Sort’un Avantajları ve Dezavantajları

Avantajları

• Kararlıdır (Stable Sorting): Aynı değerlere sahip elemanlar sıralama sonrası da aynı relatif konumlarını korur.
• Büyük veri kümeleri için uygundur: Performansı her durumda O(n log n) olduğundan, büyük veri kümelerinde kararlı bir performans sunar.
• Bağımsız alt problemlere bölünebilir: Paralel hesaplamalar için uygundur.

Dezavantajları

• Ek bellek kullanımı: Yardımcı diziler kullandığından, O(n) ek bellek gereksinimi vardır.
• Küçük veri kümelerinde verimsiz olabilir: Küçük diziler için ek bellek kullanımı gerektirdiğinden, Eklemeli Sıralama (Insertion Sort) gibi algoritmalardan daha yavaş olabilir.

Merge Sort’un Uygulama Alanları

Merge Sort, büyük veri setlerinde ve kararlı sıralama gerektiren uygulamalarda yaygın olarak kullanılır:

• Veritabanı sıralama işlemleri
• Dosya sıralama ve büyük veri işleme
• Paralel hesaplamalar ve çok iş parçacıklı sistemler
• Bağlı listeler üzerinde sıralama işlemleri