Sıralama algoritmalarını ele aldığımız makale serimizin bu bölümünde Merge Sort yani sıralama algoritmalarını ele alacağız.
Sıralamak istediğimiz diziyi orta noktasından eşit olarak iki alt diziye ayırdığımızı düşünelim. Ardından bu ayrılan dizileri de en fazla iki elemanlı olana kadar tekrar ayırmaya devam ederiz. Alt dizileri kendi içerisinde sıralar ve sıralı iki alt diziyi birleştirerek yek bir sıralanmış dizi elde ederiz. Bu yüzden bu yöntem de böl ve yönet yöntemlerinden bir tanesidir.
Özetle diziyi ikiye böleriz, çıkan dizileri de ikiye böleriz. Elde edilen parçalar 2 veya daha küçük eleman sayısına ulaştıysa dururuz ulaşmadıysa bölmeye devam ederiz. Elde ettiğimiz her bir parçayı kendi içinde sıralarız. Her bölünmüş parçayı sırasına göre birleştiririz. Tek bir bütün olana dek parçaları birleştirmeye devam ederiz. Tek bir bütün olduğunda dizi sıralanmış olacaktır.
Örnek:
36,26,42,4,10,80,11 sayılarından oluşan diziyi Merge Sort algoritması kullanarak sıralayalım.
- Diziyi ikiye bölerek yeniden yazarız.
- 36,26,42,4 ve 10,80,11
- Şimdi sol ve sağdaki dizileri tekrar ikiye böleriz.
- 36,26 – 42,4 ve 10,80 – 11
- şimdi tek eleman kalana kadar bir kez daha bölüyoruz.
- 36 – 26 – 42 – 4 – 10 – 80 – 11 oluyor.
- şimdi ikili ikili sıralayarak birleştiriyoruz.
- 26,36 – 4,42 – 10,80 – 11
- şimdi bu ikilileri birleştiriyoruz.
- 4,26,36,42 – 10,11,80
- şimdi bu son dizileri birleştiriyoruz ve sıralanmış dizimizi elde ediyoruz.
- 4,10,11,26,36,42,80
Zaman Karmaşıklığı:
Recursive bir fonksiyon olduğu için sürekli kendini çağırarak diziyi hep ikiye bölmektedir. Her bölünmüş dizinin Merge işlemi için de dizinin uzunluğu olan N işlem yapıldığından karmaşıklık maliyeti O(n*logn) olacaktır.
Bu konuyla ilgili sorularınızı alt kısımda bulunan yorumlar alanını kullanarak sorabilirsiniz.
Referanslar
Algoritmalara Giriş: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
TAGs: Merge Sort, Sorting Algorithms
