Quick Sort (Hızlı Sıralama) Algoritması

ibasoglu Algoritmalar, Sıralama Algoritmaları 0 Comments

Selamün Aleyküm Arkadaşlar;

Hızlı sıralama algoritması adından da anlaşıldığı üzere hızlı sıralama algoritmalarından birisidir. Çalışma mantığı; herhangi bir sayı seçilir. Buna Pivot denir. Ortadaki, sondaki, baştaki veya rastgele bir sayı da olabilir. Küçük olan sayılar; seçilen sayının soluna, büyük olan sayılar sağına yazılır. Küçük olan ve büyük olan sayılarda aynı şekilde sıralanır. Bir örnekle açıklayalım.

Şöyle bir dizimiz olsun.

Sondaki elemanı pivot olarak seçelim ve küçük olanları sola, büyük olanları sağa yazalım.

Sonra sağ ve sol kısımda aynı şekilde sıralanır. Tek eleman kalana kadar bu işlem devam eder. İşlemin sonunda dizi sıralanmış olur.

C#

void main(){
    int[] d = Quick_Sort(new int[]{76, 6, 4, 19, 50}, 0, 5);

    //Konsola yaz
    for (int i = 0; i < d.Length; i++){
        Console.Write(d[i] + " ");
    }
    Console.ReadKey();
}

//@parametreler dizi, index(0), diziuzunluk
int[] Quick_Sort(int[] dizi, int sol, int sag) {
    //Pivot olarak son elemanı seç
    int p = dizi[sag - 1], i = sol, j = sag - 2, temp = 0;

    if (sag - sol > 2){
        while (i < j){
            //Sol kısımdaki eleman pivot elemandan büyükse seç
            while (dizi[i] < p) { i++; }

            //Sağ kısımdaki eleman pivot elemandan küçükse seç
            while (j > 0 && dizi[j] > p) { j--; }

            if (i < j){
                temp = dizi[i];
                dizi[i++] = dizi[j];
                dizi[j--] = temp;
            }
        }
    }

    //Pivot elemanı karşılaştır ve yer değiştir
    if (p < dizi[i]){
        temp = dizi[i];
        dizi[i] = dizi[sag - 1]; 
        dizi[sag - 1] = temp;
    }

    //Solda eleman varsa
    if(i - sol > 1)
        dizi = Quick_Sort(dizi, sol, i);

    //Sağda eleman varsa
    if(sag - (i+1) > 1)
        dizi = Quick_Sort(dizi, i + 1, sag);

    return dizi;
}

Proje dosyasını buradan indirebilirsiniz.

PHP

$b = QuickSort(array(3, 2, 9, 12, 42, 50, 15), 0, 7);

//Ekrana yaz
for ($i=0; $i < count($b); $i++) { 
	echo $b[$i] . ' ';
}

//@parametreler dizi, index(0), diziuzunluk
function QuickSort($dizi, $sol, $sag){
	//Pivot olarak son elemanı seç
    $p = $dizi[$sag - 1]; 
    $i = $sol; 
    $j = $sag - 2;

    if ($sag - $sol > 2){
        while ($i < $j){
            //Sol kısımdaki eleman pivot elemandan büyükse seç
            while ($dizi[$i] < $p) { $i++; }

            //Sağ kısımdaki eleman pivot elemandan küçükse seç
            while ($j > 0 && $dizi[$j] > $p) { $j--; }

            if ($i < $j){
                $temp = $dizi[$i];
                $dizi[$i++] = $dizi[$j];
                $dizi[$j--] = $temp;
            }
        }
    }

    //Pivot elemanı karşılaştır ve yer değiştir
    if ($p < $dizi[$i]){
        $temp = $dizi[$i];
        $dizi[$i] = $dizi[$sag - 1]; 
        $dizi[$sag - 1] = $temp;
    }

    //Solda eleman varsa
    if($i - $sol > 1)
        $dizi = QuickSort($dizi, $sol, $i);

    //Sağda eleman varsa
    if($sag - ($i+1) > 1)
        $dizi = QuickSort($dizi, $i + 1, $sag);

    return $dizi;
}

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.

Comb Sort (Tarak Sıralama) Algoritması

ibasoglu Algoritmalar, Sıralama Algoritmaları 0 Comments

Selamün Aleyküm Arkadaşlar;

Tarak sıralama algoritması kabarcık sıralama (Bubble Sort) algoritmasının geliştirilmiş halidir. Kabarcık sıralama algoritmasında ardışık olarak karşılaştırılır. Tarak sıralamasında ise aralarında 1’den fazla boşluk olabilir.

Şöyle bir dizimiz olsun. Küçükten büyüğe doğru sıralayalım.

İlk önce dizinin boyutu 1,3’e bölünür. Bölünen kısmın tam kısmı alınır.  5/1,3 = 3,8. Tam kısmı 3.

İlk eleman seçilir ve üç fazlası olan eleman karşılaştırılır.

Sonra ikinci eleman seçilir ve +3 fazlası olan eleman karşılaştırılır.

Sonra üçüncü eleman seçilir. +3 fazlası dizinin uzunluğunu aştığı için işlem yapılamaz. Boşluk sayısı tekrar 1,3’e bölünür ve tam kısmı alınır. 3 / 1,3 = 2,3 Tam kısmı 2 olarak alınır. Birinci eleman seçilir ve +2 fazla elemanla karşılaştırılır.

İkinci eleman seçilir ve +2 fazlası olan elemanla karşılaştırılır. Sonra diğer elemanlar seçilip +2 fazlası elemanlar dizinin sonuna kadar karşılaştırılır.

Dizinin sonuna geldiğinde tekrar boşluk sayısı 1,3’e bölünür. 2 / 1,3 = 1,5 tam kısmı alınır 1. Birinci eleman seçilir ve 1 fazlası yani sonraki elemanla karşılaştırılır. Sonra ikinci eleman sonraki elemanla. Diğer elemanlarda bir sonraki elemanlarla karşılaştırılır.

Sonunda dizimiz sıralanmış olur.

C#

void Main()
{
    int[] d = CombSort(new int[] {4, 10, 1, 6, 7 });
    for (int i = 0; i < d.Length; i++){
        Console.Write(d[i] + " ");
    }
    Console.ReadKey();
}

int[] CombSort(int[] dizi) {
    int bosluk = dizi.Length;
    bool degisti = false;
    while (bosluk > 1 || degisti) {
        if(bosluk > 1)
            bosluk =(int) ((float) bosluk / 1.3f);

        degisti = false;

        for (int i = 0; i + bosluk < dizi.Length; i++){
            if (dizi[i + bosluk] < dizi[i]) {
                int temp = dizi[i + bosluk];
                dizi[i + bosluk] = dizi[i];
                dizi[i] = temp;
                degisti = true;
            }
        }
    }
    
    return dizi;
}

Proje dosyasını buradan indirebilirsiniz.

PHP

$d = CombSort(array(4, 10, 1, 6, 7));
for ($i = 0; $i < count($d); $i++){
    echo $d[$i] . ' ';
}

function CombSort($dizi) {
    $bosluk = count($dizi);
    $degisti = false;
    while ($bosluk > 1 || $degisti) {
        if($bosluk > 1)
            $bosluk = intval($bosluk / 1.3);

        $degisti = false;

        for ($i = 0; $i + $bosluk < count($dizi); $i++){
            if ($dizi[$i + $bosluk] < $dizi[$i]) {
                $temp = $dizi[$i + $bosluk];
                $dizi[$i + $bosluk] = $dizi[$i];
                $dizi[$i] = $temp;
                $degisti = true;
            }
        }
    }
    
    return $dizi;
}

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.

Gnome Sort (Cüce Sıralama) Algoritması

ibasoglu Algoritmalar, Sıralama Algoritmaları 0 Comments

Selamün Aleyküm Arkadaşlar;

Cüce sıralama algoritmasının çalışma mantığı; İlk elemanı seçer sonrakiyle karşılaştırır (küçük veya büyüğe) sıralamaya göre yer değiştirir. Sonra ondan önceki eleman varsa bir öncekiyle karşılaştırır. Yer değiştirmezse tekrar kaldığı elemandan aynı şekilde devam eder.

Elimizde şöyle bir dizimiz olsun. Küçükten büyüğe doğru sıralayalım.

İlk önce birinci eleman seçilir. Sonraki elemanla karşılaştırılır.

3-5’den küçük olduğu için yer değiştirir. Birinci elemandan önce eleman olmadığı için ikinci eleman seçilir.

1-5’den küçük olduğu için yer değiştirir. Önceki elemanlar olduğu için son eleman işaretlenir. Önceki elemanlar karşılaştırılır.

1-3’den küçük olduğu için yer değiştirir. Bakılacak eleman kalmadığı için işaretlenen eleman ve sonraki eleman karşılaştırılır.

10-5’den küçük olmadığı için yer değiştirilmez. Diğer eleman seçilir ve karşılaştırılır.

7-10’dan küçük olduğu için yer değiştirir. ve son karşılaştırılan eleman işaretlenir. 7 olan elaman önceki elemanla karşılaştırılır.

7-5’den küçük olmadığı için işaretlenen eleman sonda olduğunda sıralama işlemi tamamlanır.

Özet olarak bir eleman sonraki elemanla karşılaştırılır. Yer değiştirilirse; önceki elemanlar yer değiştirilene kadar bakılır. Yer değiştirme olmadığı zaman dizide kalınan son elemandan devam edilir.

C#

void Main()
{
    int[] d = Gnome_Sort(new int[] {5, 3, 1, 10, 7});

    for (int i = 0; i < d.Length; i++){
        Console.Write(d[i] + " ");
    }

    Console.ReadKey();
}

int[] Gnome_Sort(int[] dizi){
    int i = 0, j = 1;
    while (i < dizi.Length - 1 ) {
        if (i == -1)
            i = j;

        if (dizi[i + 1] > dizi[i])
            i = j++;
        else {
            int temp = dizi[i];
            dizi[i] = dizi[i + 1];
            dizi[i + 1] = temp;
            i--;
        }
    }

    return dizi;
}

Proje dosyasını buradan indirebilirsiniz.

PHP

$d = Gnome_Sort(array(5, 3, 1, 10, 7));

for ($i = 0; $i < count($d); $i++){
    echo $d[$i] . ' ';
}

function Gnome_Sort($dizi){
    $i = 0; $j = 1;
    
    while ($i < count($dizi) - 1 ) {
        if ($i == -1)
            $i = $j;

        if ($dizi[$i + 1] > $dizi[$i])
            $i = $j++;
        else {
            $temp = $dizi[$i];
            $dizi[$i] = $dizi[$i + 1];
            $dizi[$i + 1] = $temp;
            $i--;
        }
    }

    return $dizi;
}

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.

Pigeonhole Sort (Güvercin Yuvası Sıralama) Algoritması

ibasoglu Algoritmalar, Sıralama Algoritmaları 0 Comments

Selamün Aleyküm Arkadaşlar;

Güvercin yuvası algoritması minimum ve maksimum sayılar arasındaki veriler için bir dizi oluşturup bu dizide sayıları sayıp, buna göre sıralama işlemi yapar. Pek kullanılmaz. Bunun sebebi sıralamanın hızlı şekilde nadiren oluşmasıdır.

Örnekle açıklayacak olursak eğer, şöyle bir dizimiz olsun.

Bu dizimizde 9 ve 19 arasında sayılar var. Arasındaki sayılar kadar güvercin yuvası oluşturuyoruz.

Sıfırıncı index dizideki minimum değeri, sonuncu index ise maksimum değeri temsil eder.

Şimdi A dizimizdeki sayılardan kaç tane varsa B dizimizde (+1 arttıralım) saydıralım.

Şimdi ise B dizisine baştan itibaren bakılır. hangi eleman 0’dan büyük ise o eleman sırasıyla diziye eklenir. Değeri -1 azaltılır. 0 olana kadar diziye eklenir. Sonra diğer elemanlara bakılır. Sonunda dizimiz sıralanmış olur.

void Main()
{
    int[] d = Pigeonhole_Sort(new int[] { 12, 16, 19, 10, 9});

    //Diziyi konsola yaz
    for (int i = 0; i < d.Length; i++){
        Console.Write(d[i] + " ");
    }

    Console.ReadKey();
}

int[] Pigeonhole_Sort(int[] Dizi)
{
    //Min ve max değerleri bul
    int min = Dizi[0], max = Dizi[0];
    foreach (int x in Dizi){
        min = Math.Min(x, min);
        max = Math.Max(x, max);
    }

    //Yuvaları tanımla
    int[] yuvalar = new int[max - min + 1];

    //Sayıları say
    foreach (int x in Dizi)
        yuvalar[x - min]++;

    //Diziyi Sırala
    int k = 0;
    for (int i = 0; i < yuvalar.Length; i++)
        while (yuvalar[i]-- > 0)
            Dizi[k++] = i + min;

    return Dizi;
}

Proje dosyasını buradan indirebilirsiniz.

PHP

$d = Pigeonhole_Sort(array(12, 16, 19, 10, 9));

//Diziyi ekrana yaz
for ($i = 0; $i < count($d); $i++){
    echo $d[$i] . ' ';
}

function Pigeonhole_Sort($Dizi)
{
    //Min ve max değerleri bul
    $min = $Dizi[0]; $max = $Dizi[0];
    foreach ($Dizi as $x){
        $min = min($x, $min);
        $max = max($x, $max);
    }

    //Yuvaları tanımla ve sıfırla
    $yuvalar = array();
    for ($i=0; $i < count(max - min + 1); $i++) { 
    	$yuvalar[$i] = 0;
    }

    //Sayıları say
    foreach ($Dizi as $x)
        $yuvalar[$x - $min]++;

    //Diziyi Sırala
    $k = 0;
    for ($i = 0; $i < count($yuvalar); $i++)
        while ($yuvalar[$i]-- > 0)
            $Dizi[$k++] = $i + $min;

    return $Dizi;
}

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.

Radix Sort (Taban veya Basamağa Göre Sıralama) Algoritması

ibasoglu Algoritmalar, Sıralama Algoritmaları 0 Comments

Selamün Aleyküm Arkadaşlar;

Radix sıralama algoritması ilk önce birler basamağındaki rakamı veya harfi karşılaştırıp bir sıralama yapar. Sonra o sıralamanın onlar basamağına göre tekrar dizilimini yapar. En fazla hangi basamaklı sayı varsa o basamağa kadar bu şekilde sıralama devam eder. Son basamak sıralamasında dizi sıralanmış olur.

Şöyle bir dizimiz olsun. Küçükten büyüğe doğru sıralayalım.

İlk önce birler basamağına göre sıralama yapılır.

Sonra onlar basamağına göre sıralama yapılır.

Sonra yüzler basamağına göre sıralama yapılır.

Son olarak en büyük sayı binler basamağında olduğu için binler basamağına göre sıralama yapılır.

Ve sonunda dizi sıralanmış olur.

Aslında her basamakta rakamlar arsındaki uzaklığa bakılır ve sıralama yapılır. Yani aslında basamaklar arasındaki rakamlara göre sayarak sıralama yapılır. Couting Sort (buradan bakabilirsiniz) sıralamasını kullanarak yazabiliriz. Sayı yerine rakamları sayacağımız için 0-9 uzunluğunda bir diziye ihtiyacımız var. Sayıları sayıp uzaklığına göre dizimize yerleştiririz. Tabiki bu son basamağa kadar tekrar edecektir. Dilerseniz while döngüsüyle veya recursive bir fonksiyonla yazabilirsiniz.

void Main()
{
int[] d = Radix_Sort(new int[]{1000, 32, 353, 21, 421});

//Konsola yaz
for (int i = 0; i < d.Length; i++){
    Console.Write(d[i] + " ");
}

Console.ReadKey();

}

int[] Radix_Sort(int[] dizi, int b = 1) {
    int[] a = new int[10];
    int[] c = new int[dizi.Length];

    int i = 0, ra = 0, p =  b * 10, k = 0;

    //Rakamlara göre say
    for (i = 0; i < dizi.Length; i++){
        ra = (dizi[i] % p) / b;

        //Kaçıncı basamağındaysa en büyük sayıyı al
        if(dizi[i] / p > k)
            k = dizi[i] / p;
        a[ra]++;
    }

    //n = n + (n - 1)
    for (i = 1; i < a.Length; i++){
        a[i] += a[i - 1];
    }

    //a daki indexlere göre sayıları sırala
    for (i = dizi.Length -1; i >= 0; i--){
        ra = (dizi[i] % p) / b;
        c[--a[ra]] = dizi[i];
    }

    //Sayı sıfırdan büyükse 
    if(k > 0)
        return Radix_Sort(c, p);
    return c;
}

Proje dosyasını buradan indirebilirsiniz.

PHP

$d = Radix_Sort(array(56, 1002, 24, 1, 256));

for ($i=0; $i < count($d); $i++) { 
	echo $d[$i] . ' ';
}

function Radix_Sort($dizi, $b = 1) {
    $a = array();
    $c = array();

    $i = 0; $ra = 0; $p =  $b * 10; $k = 0;

    //a dizisini 0'la
    for ($i=0; $i < 10; $i++) { 
    	$a[$i] = 0;
    }

    //Rakamlara göre say
    for ($i = 0; $i < count($dizi); $i++){
        $ra = intval(($dizi[$i] % $p) / $b);

        //Kaçıncı basamağındaysa en büyük sayıyı al
        if(intval($dizi[$i] / $p) > $k)
            $k = intval($dizi[$i] / $p);
        $a[$ra]++;
    }

    //n = n + (n - 1)
    for ($i = 1; $i < count($a); $i++){
        $a[$i] += $a[$i - 1];
    }

    //a daki indexlere göre sayıları sırala
    for ($i = count($dizi) - 1; $i >= 0; $i--){
        $ra = intval(($dizi[$i] % $p) / $b);
        $c[--$a[$ra]] = $dizi[$i];

    }

    //Sayı sıfırdan büyükse 
    if($k > 0)
        return Radix_Sort($c, $p);
    return $c;
}

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.

Merge Sort (Birleştirmeli Sıralama) Algoritması

ibasoglu Algoritmalar, Sıralama Algoritmaları 0 Comments

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.

Bubble Sort (Baloncuk veya Kabarcık Sıralama) Algoritması

ibasoglu Algoritmalar, Sıralama Algoritmaları 0 Comments

Selamün Aleyküm Arkadaşlar;

Bubble Sort algoritması seçilen 1. elemanın, bir sonraki elemanla karşılaştırılıp; sonra diğer elemanların, bir sonraki elemanla karşılaştırılarak devam eder. Karşılaştırılan eleman ve sonraki eleman küçük veya büyükse (sıralamaya göre) yer değiştirir. Bu döngü sona geldiğinde sıralama olmadıysa veriler sıralanana kadar baştan sona devam eder.

Bir A dizimiz olsun. Bu diziyi büyükten küçüğe doğru sıralayalım.

İlk eleman seçilip bir sonraki elemanla karşılaştırılır. Sonraki eleman küçükse yer değiştirilir. Sonra ikinci eleman seçilip sonraki eleman karşılaştırılır. Sonra üçüncü eleman seçilir bu şekilde devam eder.

Sıralama tamamlandığında döngü sonlandırılır.

Burada dikkat edilirse ilk döngüde en büyük olan sayı sona gelir.

İkinci döngüde ise sondaki sayının bir küçüğü sondan ikinci olur.

Dizi sayısına n dersek:

n, (n-1), (n-2) … şeklinde döngü tekrarlanır.

Bu algoritmayı koda dökersek eğer ilk önce eleman seçmek için bir döngü yazalım. Bir sonraki elemanla karşılaştırıldığı için döngü dizi uzunluğunun – 1 sonucuna kadar dönmelidir. Elemanları karşılaştırıp sonraki eleman, seçilen elemandan küçükse yer değiştirmelidir.

int[] a = new int[]{17, 3, 1, 5, 45}

for (int i = 0; i < a.Length - 1; i++)
{
    if (a[i + 1] < a[i]) {
        int temp = a[i];
        a[i] = a[i + 1];
        a[i + 1] = temp;
    }
}

Tabiki bu döngü bir defa dönmeyeceği için bir sonsuz döngünün içinde yazmamız gerekir. Veriler sıralanana kadar bu döngü hep tekrarlanmalıdır. Bunun için bir kontrol yazmalıyız. Yer değişmediği zaman döngüden çıkmalıdır.

int[] a = new int[]{17, 3, 1, 5, 45}

while (true) {
	bool degisti = false;

	for (int i = 0; i < a.Length - 1; i++)
	{
	    if (a[i + 1] < a[i]) {
	        int temp = a[i];
	        a[i] = a[i + 1];
	        a[i + 1] = temp;
	        degisti = true;
	    }
	}

	if (!degisti)
        break;
}

n, n-1, n-2… şeklinde kodu düzenleyelim. Bir daha sıralanmış verileri kontrol etmemesi gerekir.

int[] a = new int[]{17, 3, 1, 5, 45}
int n = a.Length;

while (true) {
	bool degisti = false;

	for (int i = 0; i < n - 1; i++)
	{
	    if (a[i + 1] < a[i]) {
	        int temp = a[i];
	        a[i] = a[i + 1];
	        a[i + 1] = temp;
	        degisti = true;
	    }
	}

	n--;

	if (!degisti)
        break;
}

Proje dosyasını buradan indirebilirsiniz.

PHP

$a = array(17, 3, 1, 5, 45);
$n = count($a);

while (true) {
	$degisti = false;

	for ($i = 0; $i < $n - 1; $i++)
	{
	    if ($a[$i + 1] < $a[$i]) {
	        $temp = $a[$i];
	        $a[$i] = $a[$i + 1];
	        $a[$i + 1] = $temp;
	        $degisti = true;
	    }
	}

	$n--;

	if (!$degisti)
        break;
}

//Ekrana sıralanmış diziyi yaz
for ($i=0; $i < count($a); $i++) { 
	echo $a[$i] . ' ';
}

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.

Couting Sort (Saymalı Sıralama) Algoritması

ibasoglu Algoritmalar, Sıralama Algoritmaları 2 Comments

Selamün Aleyküm Arkadaşlar;

Saymalı sıralama algoritması verilerin aralığını kullanarak sıralama yapar. Saymalı sıralama algoritması Harold H. Seward tarafından 1954 yılında yazılmıştır.

Elimizde şu şekilde bir A dizisi olsun:

İlk önce dizideki en büyük değer bulunur.  Dizideki en büyük değer 7’dir. 7 + 1 uzunluğunda bir başka dizi tanımlanır. Biz bunu B dizisi olarak tanımlayalım. Sonra B dizisinin tüm değerleri 0 yapılır.

Sonra A dizisiyle aynı uzunlukta başka bir dizi tanımlanır. Biz bunu C dizisi olarak tanımlayalım.

Sonra A dizisi birinci elemanından itibaren seçilir. Birinci elemanın değeri B dizinde index numarasını gösterir. B dizisindeki veri +1 arttırılır.

Sonra B dizisine n = n + (n-1) uygulanır. Yani bir elemanın değeri bir önceki elemanın değeriyle toplanır ve elemana yazılır.

A dizisinin sondan itibaren elemanı seçilir. Değeri B dizisinin indeksini verir. B elemanının değerinin bir eksiği,  C dizisindeki indeksi verir. C dizisindeki (B elemanının değeri – 1) indeksine, seçilen elemanın değeri yazılır. B elemanının değeri 1 azaltılır.

Böylelikle A dizisindeki elemanlar, C dizisinde sıralanmış olur.

C# Kod yapısı da aşağıdaki gibidir.

int[] a = new int[]{7, 3, 5, 1};

//En büyük değerin indeksini al
int enb = 0;
for (int i = 1; i < a.Length; i++)
{
    if (a[i] > a[enb])
        enb = i;
}

//B ve C dizilerini tanımla
int[] b = new int[a[enb] + 1];
int[] c = new int[a.Length];

//dizideki elemanları say
for (int i = 0; i < a.Length; i++)
{
    b[a[i]] += 1;
}

//n = n + (n - 1)
for (int i = 1; i < b.Length; i++)
{
    b[i] += b[i - 1];
}

//C dizisine sırala
for (int i = a.Length - 1; i >= 0; i--)
{
    c[b[a[i]]-- - 1] = a[i];
}

Proje dosyasını buradan indirebilirsiniz.

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.