Pembukaan

Halo, kali ini saya akan menjelaskan dua algoritma penyortiran sederhana yaitu Insertion Sort (penyortiran penyisipan) dan Selection Sort (penyortiran pemilihan).

Namun sebelum itu saya akan menjelaskan apa itu algoritma pernyortiran dan mengapa kamu perlu mengetahui algoritma ini.

Isi

Algoritma Pernyortiran

Algoritma Pernyortiran adalah algoritma untuk menempakatkan elemen pada urutan tertentu, ini bisa saja secara ascending (dari terkecil ke terbesar), descending (dari terbesar ke terkecil) maupun acak.

Kenapa kamu perlu mengetahui algoritma ini? algoritma ini adalah algoritma yang membantu untuk menentukan jarak dari yang terdekat ke terjauh, urutan huruf dari yang terkecil maupun terbesar dan urutan angka dari yang terkecil maupun terbesar.

Untuk programmer Javascript seperti saya mungkin jarang menggunakan algoritma ini karena sudah disediakan built in method sort() pada Javascript, namun tahukah kamu kalau beberapa Javascript Engine yang membangun built in method sort menggunakan beberapa dari algoritma pernyortiran yang berbeda, contohnya :

Bisa dilihat sejarah implementasi algoritma pernyortiran di salah satu engine yaitu v8 pada method sort() disini.

Karena hal itu pula saya memutuskan untuk menggunakan Javascript sebagai contoh implementasi algoritma ini, sebelumnya saya berencana menggunakan C++ tapi karena ingin memberitahu tentang algoritma built in method ini jadi why not? kata saya.

Oke sekarang saya akan menjelaskan dua algoritma pernyortiran sederhana dibawah ini.

Insertion Sort

Insertion Sort adalah metode penyisipan yang membangun array terakhir dari penyortiran setiap value yang diurutkan satu persatu.

Rumus insertion sort yang digunakan adalah :

O(n + j), dimana j adalah nilai dari inversi (pembalikkan)

Perulangan for dimulai dari index pertama, dengan pengecekan insertion sort yang dimulai secara inversi dari sebelum index arr[n] dan seterusnya sampai index nol.

Untuk pengecekan pada javascript saya menggunakan perulangan while didalam perulangan for untuk setiap index yang berada sebelum index arr[n] dimulai secara inversi dengan variabel bantuan j yang berisi n - 1.

Perulangan while didalam for disini untuk mengecek apakah variabel bantuan memiliki hasil ya atau tidak dari j >= 0 dan arr[j] > arr[n] , jika iya maka arr[j + 1] nilainya diganti dengan arr[j] dan lanjutkan proses pengecekan didalam perulangan while didalam for tersebut sembari mengurangi value dari j sebesar 1, jika tidak maka tidak ada yang berubah dari value array(arr[n]) tersebut.

Jika disederhanakan :

1. array dengan index yang memiliki nilai perulangan (arr[n]).
2. pengecekan dimulai dari index sebelum arr[n].
3. n adalah nilai dari perulangan for.
4. perulangan while didalam for berakhir pada arr[arr.length - 1].
5. variabel bantuan j yang berisi n - 1.
6. pengecekan value dimulai secara inversi dari index sebelum arr[n] sampai index nol di perulangan while didalam for.

Jika proses perulangan for selesai maka akan didapatkan hasil akhir restrukturisasi array pada algoritma insertion sort ini.

Contoh kode yang bisa kamu pelajari :

function insertionSort(arr){
    for(n = 1; n < arr.length; n++){
        let current = arr[n];
        let j = n - 1;

        while(j >= 0 && arr[j] > current){
            arr[j + 1] = arr[j];
            j = j - 1;
        }

        arr[j + 1] = current;
    }

    return arr;
}

let sortedArray = insertionSort([5,13,4,7,8]);
console.log(sortedArray);

Selection Sort

Selection Sort adalah metode penyortiran dengan cara mengurutkan nilai didalam Array dari yang terkecil sampai ke yang terbesar ataupun sebaliknya.

Rumus selection sort yang digunakan adalah :

О (n^2)

Perulangan for dimulai dari index nol, dengan pengecekan selection sort yang dimulai secara berurutan dari index arr[n] dan seterusnya sampai index terakhir.

Untuk pengecekan pada javascript saya menggunakan perulangan for didalam for untuk setiap index yang berada setelah index arr[n] dimulai secara berurutan dengan variabel bantuan min yang berisi n.

Perulangan for didalam for disini untuk mengecek apakah variabel bantuan min memiliki hasil yang lebih besar dari nilai arr[n + 1] atau tidak , jika iya maka nilai dari arr[min] dan min diganti dengan nilai tersebut, jika tidak maka tidak ada yang berubah dari value array(arr[min]) tersebut.

Jika disederhanakan :

1. array dengan index yang memiliki nilai perulangan (arr[n]).
2. pengecekan dimulai dari index nol.
3. n adalah nilai dari perulangan for.
4. perulangan for berakhir pada arr[arr.length - 1].
5. variabel bantuan min yang berisi n.
6. pengecekan value mulai dari arr[n + 1] sampai index terakhir di perulangan for didalam for.

Contoh kode yang bisa kamu pelajari :

function selectionSort(arr) { 
    for(let n = 0; n < arr.length; n++) {
        let min = n;

        for(let j = n+1; j < arr.length; j++){
            if(arr[j] < arr[min]) {
                min=j; 
            }
        }

        if (min !== n) {
            let current = arr[n]; 
            arr[n] = arr[min];
            arr[min] = current;      
        }
    }

    return arr;
}

let sortedArray = selectionSort([5,13,4,7,8]);
console.log(sortedArray);

Penutup

Sekian tulisan yang saya bisa bagikan , semoga bermanfaat.

Referensi tulisan ini :

• Wikipedia
• StackAbuse