Merge Sort (Birleştirmeli Sıralama) Algoritması
Selamün Aleyküm Arkadaşlar;
Merge Sort algoritması parçala (böl) ve yönet tekniğiyle yapılır. İlk önce dizi iki parçaya bölünür. Diğer parçalar kendi aralarında bölünür. Her parçadan bir tane kalana kadar bölünürler.
Elimizde şu şekilde bir dizimiz olsun.
Dizi son 1 elemanı kalana kadar kendi arasında ikiye bölünür.
Sonra bölünen kısımlar kendi aralarında sıralanarak birleştirilir.
Ve böylece dizimiz sıralanmış olur. Bu işlemi koda dökelim.
Burada özyineleme işlemi vardır. Her parça kendi arasında hep ikiye bölünmektedir. Bunun için recursive fonksiyon olarak yazalım. Dizimiz bölünerek sağ ve sol olarak iki diziye ayrılmaktadır.Bu sağ ve sol dizide bir eleman kalana kadar bölünmeye devam etmektedir.
int[] Merge_Sort(int[] d)
{
//Dizi boyutu 2'den küçükse yani 1 olmuş geriye diziyi döndür.
if (d.Length < 2)
return d;
int bol = d.Length / 2;
//Sol ve sağ kısımların tanımlanması
int[] sol = new int[bol];
int[] sag = new int[d.Length - bol];
//Sol diziyi doldur
for (int i = 0; i < bol; i++){
sol[i] = d[i];
}
//Sağ diziyi doldur
int k = 0;
for (int i = bol; i < d.Length; i++){
sag[k] = d[i];
k++;
}
//Sağ ve sol dizileri parçala
sol = Merge_Sort(sol);
sag = Merge_Sort(sag);
}
Parçalanan kısımların kendi aralarında sıralanıp birleştirme işleminin yapılması gerekir. Bunun içinde Birlestir adında bir fonksiyon yazalım. Gelen iki parça kendi aralarında karşılaştırılacak ve birleştirilecek. Bu işlemde bakılmayan elemanlar dizinin sonuna eklenecektir.
int[] birlestir(int[] sol, int[] sag) {
//Birleştirilen dizi iki dizinin toplam boyutunda olmalı
int[] a = new int[sol.Length + sag.Length];
//Sol dizi için j index sayacı, Sağ dizi için i index sayacı, a dizisi için k index sayacı tanımlanmıştır.
int i = 0, j = 0, k = 0;
//İki diziyi karşılaştır. Küçük olan elemanları a dizisine ekle eklenen dizilerin indexlerini 1 arttır.
while (j < sol.Length && i < sag.Length)
a[k++] = (sag[i] < sol[j])? sag[i++] : sol[j++];
//Sağ dizisinde eleman kaldıysa a dizisinin sonuna ekle
while (i < sag.Length)
a[k++] = sag[i++];
//Sol dizisinde eleman kaldıysa a dizisinin sonuna ekle
while (j < sol.Length)
a[k++] = sol[j++];
//Sıralanan ve birleştirilen diziyi geri döndür
return a;
}
Birleştirme işlemi için fonksiyonumuzu yazdık şimdi bu fonksiyonumuzu Merge_Sort fonksiyonunda çağıralım.
int[] Merge_Sort(int[] d)
{
//Dizi boyutu 2'den küçükse yani 1 olmuş geriye diziyi döndür.
if (d.Length < 2)
return d;
int bol = d.Length / 2;
//Sol ve sağ kısımların tanımlanması
int[] sol = new int[bol];
int[] sag = new int[d.Length - bol];
//Sol diziyi doldur
for (int i = 0; i < bol; i++){
sol[i] = d[i];
}
//Sağ diziyi doldur
int k = 0;
for (int i = bol; i < d.Length; i++){
sag[k] = d[i];
k++;
}
//Sağ ve sol dizileri parçala
sol = Merge_Sort(sol);
sag = Merge_Sort(sag);
//Parçaları sırala ve birleştir ve sıralanan diziyi geri döndür
return birlestir(sol, sag);
}
Artık Merge_Sort fonksiyonumuzu çağırarak sıralama işlemini yaptırabiliriz.
int[] d = Merge_Sort(new int[]{10, 5, 1, 2, 20, 15});
for (int i = 0; i < d.Length; i++){
Console.Write(d[i] + " ");
}
Proje dosyasını buradan indirebilirsiniz. (Büyükten küçüğe doğru sıralama yapar.)
PHP
$d = Merge_Sort(array(10, 5, 1, 2, 20, 15));
for ($i=0; $i < count($d); $i++) {
echo $d[$i] . ' ';
}
function Merge_Sort($d = array())
{
//Dizi boyutu 2'den küçükse yani 1 olmuş geriye diziyi döndür.
if (count($d) < 2)
return $d;
//Tek sayıysa 1 fazlasını al
$n = 0;
if(count($d) % 2 == 1)
$n = count($d) + 1;
else
$n = count($d);
$bol = $n / 2;
//Sol ve sağ kısımların tanımlanması
$sol = array();
$sag = array();
//Sol diziyi doldur
for ($i = 0; $i < $bol; $i++){
$sol[$i] = $d[$i];
}
//Sağ diziyi doldur
$k = 0;
for ($i = $bol; $i < count($d); $i++){
$sag[$k] = $d[$i];
$k++;
}
//Sağ ve sol dizileri parçala
$sol = Merge_Sort($sol);
$sag = Merge_Sort($sag);
//Parçaları sırala ve birleştir ve sıralanan diziyi geri döndür
return birlestir($sol, $sag);
}
function birlestir($sol, $sag) {
//Birleştirilen dizi iki dizinin toplam boyutunda olmalı
$a = array();
//Sol dizi için j index sayacı, Sağ dizi için i index sayacı, a dizisi için k index sayacı tanımlanmıştır.
$i = 0; $j = 0; $k = 0;
//İki diziyi karşılaştır. Küçük olan elemanları a dizisine ekle eklenen dizilerin indexlerini 1 arttır.
while ($j < count($sol) && $i < count($sag))
$a[$k++] = ($sag[$i] < $sol[$j])? $sag[$i++] : $sol[$j++];
//Sağ dizisinde eleman kaldıysa a dizisinin sonuna ekle
while ($i < count($sag))
$a[$k++] = $sag[$i++];
//Sol dizisinde eleman kaldıysa a dizisinin sonuna ekle
while ($j < count($sol))
$a[$k++] = $sol[$j++];
//Sıralanan ve birleştirilen diziyi geri döndür
return $a;
}
Hayırlı günler, sağlıcakla kalın.
Bu döküman www.ibasoglu.com’a aittir. Kaynak belirtmek suretiyle alıntı yapılabilir.