Merge Sort Nedir?

0
37 görüntülenme

Programlamada bir dizi ya da listeyi sıralamak için kullanılan bir çok sıralama algoritması vardır ancak hepsinin birbirine göre avantaj/dezavantajları olabilir.

Örneğin merge sort sıralama algoritmalarından en hızlı olanlarından biridir.

Şöyle düşünelim.

Elimizde

4-8-1-3-5-9-11 şeklinde bir sayı dizisi var. Bu sayıları küçükten büyüğe ya da tam tersi sıralamak istersek nasıl bir yol izlersiniz? Akla birden fazla çözüm yolu gelebilir.

Örneğin benim aklıma ilk gelen (bubble sort oluyor kendileri) dizinin 1. elemanını alıp diğer tüm elemanlarla karşılaştırıp en küçüğü mü diye kontrol etmek geliyor. Sonra diğer elemanlarına geçicem.

Bubble Sort

Yani 4 ü aldım sırayla 8 ile karşılaştırıyorum 8 daha büyük olduğundan diğerine geçiyorum bakıyorum 1 var 1 daha küçük o zaman en küçük sayı 1 olur diyor devam ediyorum, 3 e, 5 e 9 a ve 11 e de bakıp 1 den küçük olup olmadıklarını kontrol ettiriyorum bakıyorum ki yok en küçük 1 ve 1 i listenin başına alıyorum…

Sonrasında 2. elemana geçiyorum artık dizim şöyle oldu.

1-8-4-3-5-9-11

8 i alıyorum hepsiyle karşılaştırıyorum 8 den küçük 4 ve 3 var ve 3 olan yere 8 koyup yeni dizi oluşuyor.

1-3-4-8-5-9-11

Listenin 3. elemanına geçiyorum. 4  ten sonrakileri kontrol ettiriyorum ve daha küçük bir sayı yok değişiklik olmayacak listede.

1-3-4-8-5-9-11

Listenin 4. elemanına geçiyorum. 8 den küçük 5 var o zaman 5 ile de yer değiştiyorum.

1-3-4-5-8-9-11

Sonra diğer elemanı yani 8 i alıp 9 ve 11 ile karşılaştırıyorum ama nafile zaten küçük yok, sonrasında 9 u alıyorum ondan da küçüğü yok o zaman son elemanına gelince listenin zaten liste küçükten büyüğe sıralandı.

Bu basit gibi görünse de liste elemanları çok olunca 1000-10 bin gibi. O zaman bu sıralama algoritmasının yavaş kaldığını görürsünüz.

O zaman merge sort u gündeme alabilirsiniz.

Merge Sort

Merge sort algoritması basit olarak bir diziyi ardışık olarak en küçük alt dizilerine kadar bölen sonra da onları sıraya koyarak bireştiren özyineli (kendini tekrar eden) bir algoritmadır.

Merge sort ta işleyiş de kısaca şöyledir:

  • Sıralı olmayan diziyi ortadan eşit olarak iki alt diziye ayırır.
  • Bu ayırma işlemi, alt diziler en çok iki elemanlı olana kadar devam eder.
  • Alt dizileri kendi içinde sıralar.
  • Sıralı iki alt diziyi tek bir sıralı dizi olacak şekilde birleştirir.

Örnek Kod:

Private Sub DoMergeSort(ByVal array() As Integer, ByVal Lower As Integer, ByVal Higher As  Integer)

If Lower >= Higher Then Return
Dim length As Integer = Higher – Lower + 1
Dim middle As Integer = Math.Floor((Lower + Higher) / 2)
DoMergeSort(array, Lower, middle)
DoMergeSort(array, middle + 1, Higher)
Dim temp(array.Length – 1) As Integer
For i As Integer = 0 To length – 1
temp(i) = array(Lower + i)
Next
Dim m1 As Integer = 0
Dim m2 As Integer = middle – Lower + 1
For i As Integer = 0 To length – 1
If m2 <= Higher – Lower Then
If m1 <= middle – Lower Then
If temp(m1) > temp(m2) Then
array(i + Lower) = temp(m2)
m2 += 1
Else
array(i + Lower) = temp(m1)
m1 += 1
End If
Else
array(i + Lower) = temp(m2)
m2 += 1
End If
Else
array(i + Lower) = temp(m1)
m1 += 1
End If
Next
End Sub

 

CEVAP VER

Lütfen mesajınızı giriniz.
Lütfen isminizi giriniz

Güvenlik Kodu * Time limit is exhausted. Please reload CAPTCHA.

This site uses Akismet to reduce spam. Learn how your comment data is processed.