Merge Sort önceden anlattığımız sıralama algoritmalarından farklıdır. (daha önce bubble, selection ve insertion sort anlatmıştık) Aşağıdaki resme bakarak biraz fikir edinmeniz mümkün.
 |
| Merge Sort Örneği |
Merge Sort Nedir?
Birleştirme Sıralaması olarak da bilinen Merge Sort Divide and Conqueror algoritması esasını kullanır. Bu mantığa göre mevcut veri yapımız alt parçalara bölünür. En küçük parçaya indirgendikten sonra birleştirilmeye başlanır. Ancak birleştirme işlemi yaparken sıralama esası uygulanır, yani birleştirilen parçalar kendi içerisinde sıralanırlar. İşlem sona geldiğinde tek parça sıralı bir dizi elde edilir.
Merge Sort Örneği
Örnek dizimizde 8 eleman olsun, 23 9 11 67 21 19 44 37
Merge Sort Bölme İşlemi
Öncelikli olarak küçük parçalara ayırırız.
1. Adım: 23 9 11 67 || 21 19 44 37
2. Adım: 23 9 || 11 67 || 21 19 || 44 37
3. Adım: 23 || 9 || 11 || 67 || 21 || 19 || 44 || 37
Dikkat ederseniz her adımda diziyi ikiye böldük. Aklınıza şu gelebilir, dizi 8 elemanlı değil de 2'nin kuvveti olmayan bir eleman sayısına sahipse merge sort uygulanabilir mi diye. Cevap tabii ki! mesela 11 7 17 gibi üç elemandan oluşan bir dizi 11 7 || 17 şeklinde ikiye ayrılır. (yukarıdaki resimde cevabı var aslında)
Merge Sort Birleştirme İşlemi
1. Geçiş:
1. Adım: 23 ve 9 karşılaştırılır 9 23 şeklinde sıralanır.
2. Adım: 11 ve 67 karşılaştırılır 11 67 şeklinde sıralanır.
3. Adım: 21 ve 19 karşılaştırılır 19 21 şeklinde sıralanır.
4. Adım: 44 ve 37 karşılaştırılır 37 44 şeklinde sıralanır.
dizimiz şu hale gelir; 9 23 || 11 67 || 19 21 || 37 44
2. Geçiş:
1. Adım: 9 || 23 ile 11 || 67 karşılaştırılır.
not: Bu karşılaştırma işlemi şöyle yapılır; ilk dizinin ilk elemanı ile karşıdaki dizinin ilk elemanı kontrol edilir. Küçük olan bir üst diziye yazılır.
9 sayısı 11 den küçüktür bu yüzden başa 9 gelir.
11 sayısı ile 23 karşılaştırılır. 11 küçük olduğundan 9 11 dizisi oluşur.
23 sayısı ile 67 karşılaştırılır. 23 küçük olduğundan 9 11 23 dizisi oluşur.
67 tek kaldığından diziye direkt eklenir. 9 11 23 67 dizisi oluşur.
2. Adım: 19 || 21 ile 37 || 44 dizisi karşılaştırılır. 2. geçiş 1. adımda anlattığım sistem aynen gerçekleşir.
sonuç olarak 19 21 37 44 dizisi oluşur.
2 Adımın sonucunda 9 11 23 67 || 19 21 37 44 dizisi oluşur.
3. Geçiş:
1. Adım: 9 11 23 67 dizisi ile 19 21 37 44 dizisi karşılaştırılır.
9 ile 19 karşılaştırılır. 9 başa gelir.
19 ile 11 karşılaştırılır. 11 ikinci eleman olur. 9 11
19 ile 23 karşılaştırılır. 19 üçüncü eleman olur. 9 11 19
21 ile 23 karşılaştırılır. 21 dördüncü eleman olur 9 11 19 21
23 ile 37 karşılaştırılır. 23 beşinci eleman olur. 9 11 19 21 23
37 ile 67 karşılaştırılır. 37 altıncı eleman olur. 9 11 19 21 23 37
67 ile 44 karşılaştırılır. 44 yedinci eleman olur. 9 11 19 21 23 37 44
67 ile karşılaştırılacak eleman kalmadığından sekizinci eleman olur. 9 11 19 21 23 37 44 67
Not: Merge sort birleştirme işleminde 1. Geçiş 4 adımken, 2. geçiş 2 adım, 3. geçiş ise 1 adımdır. Bunları daha sonra soracağım size ;) Hadi kolay gelsin.
Eğer Merge Sort C kodu nasıl yazılır merak ediyorsanız ilgili makalemize bakabilirsiniz.
Etiketler: Birleştirme Sıralaması, böl ve fethet algoritması, Divide and Conqueror, divide and conqueror algoritması, merge sort, siralama algoritmaları