2 Algoritma Pernyortiran Sederhana Pada Javascript
Tags: algorithms, javascript, computerscience, indonesia
Published: 2021-02-16 00:23:29

# 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 :

| Engine | Algoritma |
|-------------|---------|
| V8 | Quicksort atau Insertion Sort (untuk array kecil) |
| Firefox | Merge Sort |
| Safari | Quicksort, Merge Sort, atau Selection Sort (tergantung dari tipe Array) |

Bisa dilihat sejarah implementasi algoritma pernyortiran di salah satu engine yaitu v8 pada method `sort()` [disini](https://github.com/v8/v8.dev/blob/main/src/blog/array-sort.md).

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](https://upload.wikimedia.org/wikipedia/commons/9/9c/Insertion-sort-example.gif)

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 :

```js
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](https://stackabuse.s3.amazonaws.com/media/selection-sort-in-javascript-1.gif)

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 :

```js
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](https://stackabuse.com/sorting-arrays-in-javascript/#:~:text=Like%20many%20other%20popular%20languages,Firefox%3A%20Merge%20sort)