Membuat Algoritma Insertion Sort di Kotlin
Membuat Algoritma Insertion Sort di Kotlin – Pada artikel ini kita akan membahas bagaimana membuat algoritma insertion sort di kotlin. Setelah sebelumnya kita membahas mengenai algoritma bubble sort, sekarang kita akan membuat algoritma insertion sort menggunakan bahasa pemrograman Kotlin. Insertion Sort merupakan sebuah algoritma pengurutan dengan cara membandingkan dan mengurutkan dua data pertama pada array, kemudian membandingkan data para array berikutnya apakah sudah berada di tempat seharusnya atau belum. Algoritma insertion sort dapat dianalogikan sebagai proses pengurutan kartu yang berada di tangan kita. Simak artikel ini lebih lanjut untuk memahami mengenai bagaimana membuat algoritma insertion sort di kotlin.
Daftar Isi
Konsep Insertion Sort
Algoritma insertion sort merupakan algoritma sederhana yang cukup efisien untuk mengurutkan sebuah list yang hampir terurut. Cara kerja algoritma ini adalah dengan mengambil elemen list satu-per-satu dan memasukkannya di posisi yang benar.
Insertion sort ini memiliki beberapa keuntungan:
- Implementasi yang sederhana
- Paling efisien untuk data berukuran kecil
- Proses di tempat (memerlukan O(1) memori tambahan)
- Stabil
- Merupakan online algorithmic, yang berarti bisa langsung melakukan sort setiap ada data baru
Pada tahun 2004 Bender, Farach-Colton, and Mosteiro menemukan pengembangan baru dari algoritma ini, disebut library sort atau gapped insertion sort yang menggunakan beberapa gap kosong di sepanjang array. Dengan algoritma ini, pergeseran elemen dilakukan sampai gap tersebut dicapai. Algoritma ini cukup baik dengan kompleksitas O(n). Akan tetapi, kita hanya akan membuat implementasi insertion sort saja di Kotlin.
Kompleksitas Waktu Insertion Sort
- Kompleksitas terbaik: n
- Rata-rata Kompleksitas: n^2
- Kompleksitas terburuk: n^2
Source code algoritma insertion sort di kotlin
fun main(){
val unsortedList = mutableListOf(5, 3, 4, 1, 2)
println("Unsorted List")
for (k in unsortedList) print("$k ")
val sortedList = insertionSort(unsortedList)
println("\nSorted List")
for (k in sortedList) print("$k ")
}
fun insertionSort(items:MutableList<Int>):List<Int>{
if (items.isEmpty() || items.size<2){
return items
}
for (idxCount in 1 until items.count()){
val item = items[idxCount]
var i = idxCount
while (i>0 && item<items[i-1]){
items[i] = items[i-1]
i -= 1
}
items[i] = item
}
return items
}
Hasil yang diperoleh
Dari source code diatas, kalian akan mendapatkan hasil keluaran seperti dibawah ini.
Unsorted List 5 3 4 1 2 Sorted List 1 2 3 4 5
Temukan source code Kotlin menarik lainnya hanya di Inpows.
Baca Juga
Membuat Algoritma Bubble Sort di Kotlin
Membuat Algoritma Binary Search Menggunakan Kotlin
Membuat Algoritma Linear Search di Kotlin
Capitalize Every Word in String Menggunakan Kotlin Extension