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

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.

SnapCrab_No-0073

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

SnapCrab_No-0075

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.

SnapCrab_No-0076

 

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.