Merge Sort (Birleştirme Sıralaması)

Herkese merhaba bu yazımızda sıralama algoritmalarından seçerek sıralama algoritmasına değineceğiz.Bu yazıyı okumadan önce sıralama algoritmalarını adım adım incelemek için buraya tıklayınız ve site üzerinden sıralama algoritmalarını inceleyiniz.

Merge sort algoritmasının temelinde bir bilgisayar felsefesi olan “parçala fethe(Divide and conquer)t” felsefesi yer alır.Diğer sıralama algoritmalarına kıyasla zaman karmaşıklığı az bir algoritmadır.Bloğunda yer alan algoritmalara kıyasla en iyi diyebileceğimiz sıralama algoritmalar ındandır.

Algoritmanın genel çalışma mantığı bir problemi olası tüm parçalara bölmek ve bu parçaların hepsini tek başına çözmek ve ardından birleştirerek problemin sonucuna ulaşmaktır.

Conquer

Her iki diziyi özyineli bir fonksiyon ile sıralama işlemi baz alır daha sonra combine kısmında bu 2 dizi birleştirilir ve çözüme ulaşılır.

Combine

Küçük parçaları birleştirerek en güzel çözümü sunmaktır.

Sıralama problemi örneklerinde n elemanlı sayı dizisini n/2 elemanlı 2 diziye bölerek(Divide) çözmek temeldeki amaçtır.

Aslında algoritma shell sort algoritmasına benzer şekilde çalışır.

Algoritmayı Çalıştırmak

Bir sayı dizisini tek eleman kalacak şekilde parçalara ayırırız.Her ayırma işleminde shell sort’da olduğu gibi ayrılan grupları kendi içerisinde sıralamayız bu işlemi en son yaparız..Buraya kadar olan işlemlerin hepsi shell sort algoritması ile aynıdır.

Diziyi tek eleman kalıncaya kadar parçaladığımızda dururuz ve derin bir nefes alırız daha sonra ağaç yapısı seklinde düşünerek üst çocuklara doğru ilk elemana bakarak sıralama işlemini bitiririz.

Karmaşıklık

T(n) n elemanlı diziyi sıralama (n/2)*2 algoritmanın karmaşıklığını verir burada orta nok. Bulma ve 2 alt parça değerlerinin karmaşıklığı ise

Tetta(1) Orta Noktayı bulmak.

2 alt parça ⇒ 2(T)(n/2)

N adet birleştirme ⇒ Tetta(n) şeklinde değerlerdir.

Son

Umarım faydalı bir yazı olmuştur.Herkese başarılar.