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.
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 :
- array dengan index yang memiliki nilai perulangan (arr[n]).
- pengecekan dimulai dari index sebelum
arr[n]
. - n adalah nilai dari perulangan
for
. - perulangan
while
didalamfor
berakhir padaarr[arr.length - 1]
. - variabel bantuan
j
yang berisin - 1
. - pengecekan value dimulai secara inversi dari index sebelum
arr[n]
sampai index nol di perulanganwhile
didalamfor
.
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 :
- array dengan index yang memiliki nilai perulangan (arr[n]).
- pengecekan dimulai dari index nol.
- n adalah nilai dari perulangan
for
. - perulangan
for
berakhir padaarr[arr.length - 1]
. - variabel bantuan
min
yang berisin
. - pengecekan value mulai dari
arr[n + 1]
sampai index terakhir di perulanganfor
didalamfor
.
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
Top comments (6)
Thanks for sharing! Baru tau beda browser algoritma sortingnya beda.
Sama sama bro ^_^
sempet kesulitan mengerti, terimakasih ilmunya 😃
Sama sama, terima kasih sudah baca tulisan saya ya bro, semoga sehat selalu di masa pandemi ini ^_^
Shorting Bubble ketika dulu pelajaran algoritma.. ini materi pamungkas.. saya dulu kurang mengerti.. tapi penjelasan ini menarik.. mantap
Makasih bro ^_^