Bahasa Singkong menyediakan fungsi-fungsi untuk kebutuhan sorting: sort_number, sort_boolean, sort_string, sort_array, sort_hash, sort_date, sort_rect_array_of_number_by_index, dan reverse. Dengan demikian, tutorial ini lebih ditujukan untuk kepentingan mempelajari algoritma.
Di dalam buku Dasar-dasar Algoritma, Struktur Data, dan Pemrograman dengan Bahasa Singkong, kita membahas contoh algoritma dengan langkah demi langkah bubble sort, kemudian mempelajari pemrograman dengan mengimplementasikan bubble sort tersebut dengan bahasa Singkong.
Pada tutorial ini, mari kita contohkan algoritma sorting lain, yaitu insertion sort, dimana kita memiliki bagian terurut dan belum terurut, dan kita akan sisipkan ke posisi yang tepat sampai semua terurut. Mirip seperti mengurutkan dalam permainan kartu.
Kita siapkan fungsi insertion_sort_detail yang akan menampilkan langkah demi langkahnya. Dengan contoh ARRAY yang sama, yaitu [4, 2, 1, 5, 3], dan ARRAY yang sama sekali tidak terurut dari kecil ke besar, yaitu [5, 4, 3, 2, 1].
Berikut adalah isi fungsinya:
var insertion_sort_detail = fn(a) {
var n = len(a)
println(a)
var i = 1
repeat {
println("Memroses indeks " + i + ", nilai " + a[i])
var j = i
var t = a[j]
repeat {
if (j < 1) {
println(" Mencapai awal array")
return null
}
println(" Membandingkan posisi sebelumnya")
println(" Apakah " + t + " >= " + a[j-1] + "?")
if (t >= a[j-1]) {
println(" Ya, sementara terurut")
return null
}
println(" Tidak, sebelum: " + a)
println(" " + a[j-1] + " -> " + a[j])
set(a, j, a[j-1])
println(" Setelah: " + a)
var j = j - 1
println(" Posisi: " + j + ", saat ini: " + a[j])
}
set(a, j, t)
println("Setelah di-insert: " + t + " " + a)
var i = i + 1
if (i >= n) {
println("Mencapai akhir array")
return null
}
}
return a
}
Dan, berikut adalah contoh outputnya, dengan ARRAY [4, 2, 1, 5, 3]: println(insertion_sort_detail([4, 2, 1, 5, 3]))
[4, 2, 1, 5, 3] Memroses indeks 1, nilai 2 Membandingkan posisi sebelumnya Apakah 2 >= 4? Tidak, sebelum: [4, 2, 1, 5, 3] 4 -> 2 Setelah: [4, 4, 1, 5, 3] Posisi: 0, saat ini: 4 Mencapai awal array Setelah di-insert: 2 [2, 4, 1, 5, 3] Memroses indeks 2, nilai 1 Membandingkan posisi sebelumnya Apakah 1 >= 4? Tidak, sebelum: [2, 4, 1, 5, 3] 4 -> 1 Setelah: [2, 4, 4, 5, 3] Posisi: 1, saat ini: 4 Membandingkan posisi sebelumnya Apakah 1 >= 2? Tidak, sebelum: [2, 4, 4, 5, 3] 2 -> 4 Setelah: [2, 2, 4, 5, 3] Posisi: 0, saat ini: 2 Mencapai awal array Setelah di-insert: 1 [1, 2, 4, 5, 3] Memroses indeks 3, nilai 5 Membandingkan posisi sebelumnya Apakah 5 >= 4? Ya, sementara terurut Setelah di-insert: 5 [1, 2, 4, 5, 3] Memroses indeks 4, nilai 3 Membandingkan posisi sebelumnya Apakah 3 >= 5? Tidak, sebelum: [1, 2, 4, 5, 3] 5 -> 3 Setelah: [1, 2, 4, 5, 5] Posisi: 3, saat ini: 5 Membandingkan posisi sebelumnya Apakah 3 >= 4? Tidak, sebelum: [1, 2, 4, 5, 5] 4 -> 5 Setelah: [1, 2, 4, 4, 5] Posisi: 2, saat ini: 4 Membandingkan posisi sebelumnya Apakah 3 >= 2? Ya, sementara terurut Setelah di-insert: 3 [1, 2, 3, 4, 5] Mencapai akhir array [1, 2, 3, 4, 5]
Langkah-langkahnya akan lebih panjang dengan ARRAY [5, 4, 3, 2, 1]: println(insertion_sort_detail([5, 4, 3, 2, 1]))
[5, 4, 3, 2, 1] Memroses indeks 1, nilai 4 Membandingkan posisi sebelumnya Apakah 4 >= 5? Tidak, sebelum: [5, 4, 3, 2, 1] 5 -> 4 Setelah: [5, 5, 3, 2, 1] Posisi: 0, saat ini: 5 Mencapai awal array Setelah di-insert: 4 [4, 5, 3, 2, 1] Memroses indeks 2, nilai 3 Membandingkan posisi sebelumnya Apakah 3 >= 5? Tidak, sebelum: [4, 5, 3, 2, 1] 5 -> 3 Setelah: [4, 5, 5, 2, 1] Posisi: 1, saat ini: 5 Membandingkan posisi sebelumnya Apakah 3 >= 4? Tidak, sebelum: [4, 5, 5, 2, 1] 4 -> 5 Setelah: [4, 4, 5, 2, 1] Posisi: 0, saat ini: 4 Mencapai awal array Setelah di-insert: 3 [3, 4, 5, 2, 1] Memroses indeks 3, nilai 2 Membandingkan posisi sebelumnya Apakah 2 >= 5? Tidak, sebelum: [3, 4, 5, 2, 1] 5 -> 2 Setelah: [3, 4, 5, 5, 1] Posisi: 2, saat ini: 5 Membandingkan posisi sebelumnya Apakah 2 >= 4? Tidak, sebelum: [3, 4, 5, 5, 1] 4 -> 5 Setelah: [3, 4, 4, 5, 1] Posisi: 1, saat ini: 4 Membandingkan posisi sebelumnya Apakah 2 >= 3? Tidak, sebelum: [3, 4, 4, 5, 1] 3 -> 4 Setelah: [3, 3, 4, 5, 1] Posisi: 0, saat ini: 3 Mencapai awal array Setelah di-insert: 2 [2, 3, 4, 5, 1] Memroses indeks 4, nilai 1 Membandingkan posisi sebelumnya Apakah 1 >= 5? Tidak, sebelum: [2, 3, 4, 5, 1] 5 -> 1 Setelah: [2, 3, 4, 5, 5] Posisi: 3, saat ini: 5 Membandingkan posisi sebelumnya Apakah 1 >= 4? Tidak, sebelum: [2, 3, 4, 5, 5] 4 -> 5 Setelah: [2, 3, 4, 4, 5] Posisi: 2, saat ini: 4 Membandingkan posisi sebelumnya Apakah 1 >= 3? Tidak, sebelum: [2, 3, 4, 4, 5] 3 -> 4 Setelah: [2, 3, 3, 4, 5] Posisi: 1, saat ini: 3 Membandingkan posisi sebelumnya Apakah 1 >= 2? Tidak, sebelum: [2, 3, 3, 4, 5] 2 -> 3 Setelah: [2, 2, 3, 4, 5] Posisi: 0, saat ini: 2 Mencapai awal array Setelah di-insert: 1 [1, 2, 3, 4, 5] Mencapai akhir array [1, 2, 3, 4, 5]
Untuk fungsi tanpa detil langkah, berikut adalah isi dari insertion_sort:
var insertion_sort = fn(a) {
var n = len(a)
var i = 1
repeat {
var j = i
var t = a[j]
repeat {
if (j < 1) {
return null
}
if (t >= a[j-1]) {
return null
}
set(a, j, a[j-1])
var j = j - 1
}
set(a, j, t)
var i = i + 1
if (i >= n) {
return null
}
}
return a
}
Terima kasih telah membaca :)