Algoritma Quick Sort

Algoritma Quick Sort adalah algoritma pengurutan yang berbasis pada algoritma “Divide and Conquer”. Algoritma ini memilih sebuah elemen sebagai pivot dan mempartisi array yang diberikan di sekitar pivot yang dipilih dengan menempatkan pivot pada posisi yang benar dalam array yang telah diurutkan.

Berikut adalah langkah-langkah dasar dari algoritma Quick Sort:

1. Pilih pivot. Pivot bisa dipilih dari mana saja, tetapi biasanya dipilih dari elemen pertama, terakhir, atau elemen tengah dari array.
2. Partisi array. Semua elemen yang lebih kecil dari pivot dipindahkan ke sebelah kiri pivot dan semua elemen yang lebih besar dipindahkan ke sebelah kanan pivot.
3. Ulangi langkah-langkah di atas secara rekursif untuk subarray di sebelah kiri dan kanan pivot.

Berikut adalah contoh implementasi algoritma Quick Sort dalam bahasa PHP:

<?php

function quicksort($array)
{
    if(count($array) < 2) {
        return $array;
    }

    $left = $right = array();
    reset($array);
    $pivot_key = key($array);
    $pivot = array_shift($array);

    foreach($array as $k => $v) {
        if($v < $pivot) {
            $left[$k] = $v;
        } else {
            $right[$k] = $v;
        }
    }

    return array_merge(quicksort($left), array($pivot_key => $pivot), quicksort($right));
}


$data = array(20,99,12,58,9,33,21,22, 46);
echo '<p>Before Sort</p>';
foreach($data as $d) {
    echo $d, ' ';
}
echo '<hr>';
echo '<p>After Sort</p>';
foreach(quicksort($data) as $d) {
    echo $d, ' ';
}

Output

Dalam contoh ini, fungsi `quicksort` menerima array sebagai argumen. Jika array memiliki kurang dari dua elemen, fungsi ini akan mengembalikan array tersebut karena array dengan dua elemen atau kurang sudah terurut. Jika array memiliki lebih dari dua elemen, fungsi ini akan memilih pivot (dalam hal ini elemen pertama array), memindahkan pivot ke posisi yang benar dalam array, dan mempartisi array menjadi dua subarray: satu dengan elemen yang lebih kecil dari pivot dan satu dengan elemen yang lebih besar dari pivot. Fungsi ini kemudian akan memanggil dirinya sendiri secara rekursif untuk kedua subarray tersebut.