Sıralama Algoritmaları: Merge Sort

Sıralama algoritmalarından daha önce Insertion Sort‘ u paylaşmıştım. Bu gün de vize çalışmalarıma paralel olarak paylaştığım sıralama algoritmalarından Merge Sort’ u paylaşıyorum. Yazının devamında önce Merge Sort’ un açıklamasını, ardından da Csharpta yazılmış örnek uygulamasını bulablirsiniz.

Merge Sort algoritması, divide and conquer(parçala ve yönet) metodunu kullanarak verileri sıralar. Şöyle ki algoritma, verileri tek eleman kalıncaya kadar recursive fonksiyonlar yardımıyla sürekli ikiye böler. Tek kalan elemanları ise kendi aralarında sıralı bir şekilde birleştirmeye başlar. Tek kalan elemanlar birleştiğinde de dizi sıralanmış olur. Şekil üzerinde incelediğiniz zaman daha iyi anlayacağınızı umuyorum.
Merge Sort sıralama algoritmasına da göz atacak olursak, algoritmayı mergeSort ve merge olmak üzere iki metodla gerçekleştirebiliriz..

1. mergeSort metodunun algoritması:
[cc lang = ‘java’]
mergeSort(A,p,r)
if(p2. merge metodunun algoritması:
[cc lang = ‘java’]
merge(A,p,q,r)
n1 ‹– q – p + 1
n2 ‹– r – q
n1+1 boyutlu L ve n2+1 boyutlu R dizileri oluştur
for i ‹– 1 to n1
do L[i] ‹– A[p + i – 1]
for j ‹– 1 to n2
do R[j] ‹– A[q + j]
L[n1 + 1] ‹– ?
R[n2 + 1] ‹– ?
i ‹– 1
j ‹– 1
for k ‹– p to r
do if L[i] <= R[i] then A[k] ‹-- L[i] i ‹-- i + 1 else A[k] ‹-- R[j] j ‹-- j + 1 [/cc] Sıralama algoritmasını da verdikten sonra Csharp kodlarını inceleyebilirsiniz. Kodlar algoritmanın veriliş sırasıyla aynı sırada aşağıdadır. 1. mergeSort metodu’ nun Csharp kodu
[cc lang = ‘csharp’]
private int[] a = { 6, 3, 5, 1, 8, 2, 4, 7 };
private int[] b = new int[8];
public void mergeSort(int ilk, int son)
{
if (ilk < son) { int orta = (ilk + son) / 2; mergeSort(ilk, orta); mergeSort(orta + 1, son); merge(ilk, orta + 1, son); } } [/cc] 2. merge metodu’ nun Csharp kodu
[cc lang = ‘csharp’]
public void merge(int ilk, int orta, int son)
{
int ilkIndis = ilk;
int sonIndis = orta – 1;
int index = son – ilk + 1;
while ((ilk <= sonIndis) && (orta <= son)) { if (a[ilk] <= a[orta]) { b[ilkIndis] = a[ilk]; ilkIndis++; ilk ++; } else { b[ilkIndis] = a[orta]; ilkIndis++; orta++; } } while (ilk <= sonIndis) { b[ilkIndis] = a[ilk]; ilk++; ilkIndis++; } while (orta <= son) { b[ilkIndis] = a[orta]; orta++; ilkIndis++; } for (int i = 0; i < index; i++) { a[son] = b[son]; son--; } } [/cc]    

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir