Algoritma Insertion Sort

Posted by Admin on 22 Mei 2019, 12:46 insertion sort, algoritma insert sort, insertion sort php

Algoritma insertion sort adalah algoritma pengurutan yang menggunakan dua buah list untuk proses pengurutannya. dua list tersebut yaitu yaitu sorted list dan unsorted list.

Pada kondisi awal, semua bilangan yang hendak diurutkan berada dalam kondisi “unsorted list”. Lalu, index “0” dari unsorted list dipindahkan ke sorted list. Kemudian berlanjut ke index “1” dan seterusnya. Lalu, index “0” dan “1” yang sudah dipindahkan akan dibandingkan berdasarkan nilai terkecil. Index yang memiliki terkecil itu selanjutnya akan menjadi index 0 atau index paling awal. Begitu juga yang terjadi pada index seterusnya, dimana tiap index yang baru saja dimasukan dari unsorted list ke sorted list akan dibandingkan dengan semua index yang sudah duluan masuk ke sorted list. Proses ini akan berulang sampai semua index yang ada di unsorted list berpindah ke sorted list dan dibandingkan. Barulah kita dapat melihat hasil pengurutan tersebut.

Simulasi

Contoh Perhitungan

Langkah 1. Terdapat array dengan 5 elemen seperti di bawah ini:

Selanjutnya data pada index 0 dan 1 akan dipindahkan ke sorted list. Setelahnya, data pada index 0 dan 1 di sorted list akan dibandingkan untuk mencari index yang memiliki nilai terkecil. Dari data di atas, terlihat bahwa nilai pada index 0 lebih kecil dari nilai index 1. Maka pada sorted list, tidak terjadi perubahan posisi. Hasilnya dapat dilihat pada gambar di bawah ini :

Langkah 2. Data pada index 2 dipindahkan ke sorted list. Lalu, data tersebut dibandingkan dengan data-data pada index 0 dan 1. Pada contoh kali ini, hasilnya data pada index 2 memiliki nilai lebih kecil ketimbang data di index 0 dan 1. Hasilnya, data yang baru masuk sortde list tersebut diposisikan ke index 0 dan data-data sebelumnya bergerak mundur. Hasil komparasinya akan seperti gambar berikut:

Langkah 3. Data pada index 3 masuk ke sorted list dan dibandingkan dengan data-data yang sudah ada di sorted list. Karena nilai data pada index 3 lebih kecil daripada nilai data di index 0 sampai 2, maka data pada index 3 diposisikan ke index 0 dan data-data lainnya bergerak mundur. Jadinya akan seperti berikut:

Langkah 4. Langkah terakhir adalah memasukkan data pada index 4 di unsorted list ke dalam sorted list. Setelah dibandingkan, nilai pada data index 4 lebih kecil ketimbang nilai data pada index 1 sampai 3. Hasilnya, data index 4 akan diposisikan ke index 2 dan data setelahnya akan bergerak mundur. Maka, hasilnya akan seperti gambar di bawah ini:

Dengan hasil tersebut, maka proses pengurutan dengan metode insertion sort sudah selesai.

Source Code PHP Algoritma Insertion Sort

function insertion_sort($array)
{
    for ($i = 0; $i < count($array); $i++) {
        $val = $array[$i];
        $j = $i-1;
        while ($j>=0 && $array[$j] > $val) {
            $array[$j+1] = $array[$j];
            $j--;
        }
        $array[$j+1] = $val;
    }
 
    return $array;
}

Cara Pemakaian

$angka = array(3,2,5,1);
$hasil = insertion_sort($angka);
print_r($hasil);

Demo Program dapat dilihat disini

Referensi : https://dosenit.com/kuliah-it/pemrograman/contoh-algoritma-insertion-sort