Home > programming > Assembler: Membuat Insertion Sort+Minimum Sort

Assembler: Membuat Insertion Sort+Minimum Sort

Ini bakal panjang dan membosankan, sumpah. Jika tidak tertarik atau berkepentingan saya harap tidak memaksakan diri membacanya.

Program ini mempunyai kemampuan mengurutkan masukan baik berupa integer, real maupun karakter. Proses pengurutan dapat dilakukan dengan insertion sort maupun minimum sort.

#########################################################################
# author    :     Kuncoro Dwi Atmojo     nama program:             >>> SuperSorter <<<                                                   #
##########################################################################
#>>>>>>>>>>>>>>>>               main program                    <<<<<<<<<<<<<<<<<<<<<<<<#
#>>>>                  program meminta masukan N bilangan/karakter                 <<<<<#
#>>>>>>>>             program mengurutkan bilangan/karakter                      <<<<<<<#
#>>>>>>>>>>             tersebut dengan insertion sort/minimum sort         <<<<<<<<<<<<#

############# penggunaan register #######################################################
#$s1    :nilai N, jumlah input                                                            #
#$s0    :counter untuk pengisian N bilangan/karakter                                    #
#$s2    :pilihan integer, pecahan atau karakter                                            #
#$s3    :counter untuk menampilkan isi array yang terurut                                #
#$t1    :index untuk menggeser nilai yang lebih besar dari masukan baru                    #
#$t3    :index dari masukan baru, selalu bertambah setiap ada masukan                    #
#$t4    :nilai masukan pengguna                                                            #
#$t5    :index dari nilai yang dibandingkan dengan masukkan baru                        #
#$t6    :nilai dalam array yang akan dibandingkan, nilai dari array dengan indeks $t5    #
#$t7    :index array yang akan ditampilkan                                                #
#$t8    :temp karakter yang akan diprint                                                #
#$f2    :masukan baru berupa pecahan                                                    #
#$f4    :pecahan yang akan dibandingkan dengan masukan baru                                #
###############     kamus     ###########################################################
.data
arrint: .word 0:300
arrfloat: .space 2048
arrchar: .space 1024
##############   algoritma   #################
.text
.globl main
main:                                            # main program
jal inisial                                    # menanyakan jenis masukkan, metode sorting yang dipakai, jumlah N
beq $t0,98, main_minsort                    # jika memilih metode minimum sort (b), selanjutnya ke main_minsort

main_insort:                                # main untuk insertion sort
li $s0, 1
li $t3, 0                                # index masukan, jika char maka t3 +1, int maka t3+4, double maka t3+8
muter:
jal input                        # minta masukan
jal insort                        # langsung mengurutkan setiap masukan
addi $s0,1
ble $s0, $s1, muter                # terus minta masukan hingga s0 sama dengan N
jal tampilkan                            # menampilkan hasilnya ke layar
j keluar                                # keluar program

main_minsort:                                 # main untuk minimum sort
li $s0, 1
li $t3, 0                                # index masukan, jika char maka t3 +1, int maka t3+4, double maka t3+8
jal input_minsort                    # meminta masukan, memasukkan ke dalam array tanpa mengurutkannya
addi $s0,1
ble $s0, $s1, input_minsort            # terus minta masukan hingga s0 sama dengan N
jal minsort                            # mengurutkan isi array dengan metode minimum sort
jal tampilkan                            # menampilkan hasil urutan ke layar
j keluar                                # keluar dari program
#>>>>>> end of main program <<<<<<#

#>>>>>> inisial <<<<<<<<<#
.data
str0: .asciiz ”   ~~~ program mengurutkan N masukan ~~~\n   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n”
str1: .asciiz “\n N:”
str7: .asciiz “anda ingin memasukkan integer, pecahan atau karakter(i/p/k)? ”
str8: .asciiz “\n pilih metode pengurutan:\n a. insertion sort\n b. minimum sort\n”
str9: .asciiz “(a/b)?”
pilihan: .space 8
.text
inisial:
la $a0, str0                        # menampilkan tulisan
li $v0, 4                            # ‘~~~ program mengurutkan…’
syscall

pilihinput:                            # >>>> memilih jenis input <<<<
la $a0, str7                    # menampilkan tulisan
li $v0,4                        # ‘anda ingin memasukkan integer…’
syscall

li $v0,8                        # meminta masukan
la $a0,pilihan                    # menyimpannya di ‘pilihan’
li $a1, 8
syscall

lb $t2,($a0)                    # meload pilihan ke $t2

beq $t2,105, pilihmetode        # jika masukan sudah benar, pilih metode
beq $t2,112, pilihmetode        # masukan yang benar ‘i’, ‘p’, atau ‘k’
beq $t2,107, pilihmetode

b pilihinput                    # jika masukan salah, minta masukan lagi

pilihmetode:                        # >>> memilih metode sorting yang digunakan <<<
la $a0, str8                    # menamppilkan tulisan
li $v0,4                        # ‘pilih metode…’
syscall

masukanpilihan:
la $a0, str9                # menampilkan tulisan ‘(a/b)?’
li $v0,4
syscall

li $v0,8                    # meminta masukan
la $a0,pilihan                # menyimpannya di ‘pilihan’
li $a1, 8
syscall

lb $t0,($a0)                    # meload masukan jenis metode ke $t0

beq $t0,97, masukkanN            # jika pilihan benar (a/b)
beq $t0,98, masukkanN            # branch ke masukkanN

b masukanpilihan                # jika salah minta masukan lagi

masukkanN:                                # >>> meminta masukan N jumlah input <<<
la $a0, str1                        # menampilkan tulisan
li $v0, 4                            # ‘N: ‘
syscall

li $v0,5                            # meminta masukan, menyimpan di $v0
syscall
move $s1,$v0                        # memindah masukan ke $s1

blez $s1, keluar                    # jika N kurang dari 1, keluar

jr $ra                                # kembali ke register $ra (setelah jal inisial)
#>>>>>>>> end of inisial <<<<<<<<<<<<#

#>>>>>>>> input <<<<<<<<<<<<<<<<<<<#
.data
str3: .asciiz “<> masukan ke-”
str4: .asciiz “: ”

.text
input:                                    # >>> meminta input bilangan/karakter yang ingin diurutkan <<<
la $a0, str3                        # menampilkan tulisan ‘masukan ke-‘
li $v0, 4
syscall

move $a0, $s0                        # menampilkan counter masukan
li $v0, 1
syscall

la $a0, str4                        # menampilkan ‘: ‘
li $v0, 4
syscall

beq $t2,105, input.ins.int            # branch sesuai pilihan jenis input
beq $t2,112, input.ins.float        # i (105), p(112), atau k(107)
beq $t2,107, input.ins.char

input.ins.int:
li $v0,5                        # meminta masukan integer, menyimpan di $v0
syscall
jr $ra                            # kembali ke langkah setelah input

input.ins.float:
li $v0,7                        # meminta masukan pecahan (double), menyimpak di $f0
syscall
jr $ra                            # kembali ke langkah setelah input

input.ins.char:
li $v0,8                        # meminta masukan karakter
la $a0, arrchar($t3)            # menyimpan di arrchar($t3)
li $a1,1024
syscall
jr $ra                            # kembali ke langkah setelah input
#>>>>>> end of input <<<<<<<<<<#
#>>>>>>>>insort<<<<<<<<<<<<#
.text
insort:
beq $t2,105, sort_int                # branch sesuai jenis input
beq $t2,112, sort_float                # i (105), p(112), atau k(107)
beq $t2,107, sort_char

sort_int:
move $t4,$v0                    # menyimpan masukan integer ke $t4
move $t5,$t3                    # menyimpan indeks masukan ke $t5
beqz $t3, isi_int                # untuk masukan pertama ($t3==0), langsung isi array
addi $t5, -4                    # $t5 berkurang 4, menunjuk isi array sebelumnya
lw $t6, arrint($t5)                # meload isi array sebelumnya ke $t6

bgt $t6, $t4, ceklagi            # jika masukan baru lebih kecil dari array sebelumnya, ke ceklagi
addi $t5, 4                        # jika masukan baru lebih besar,
j isi_int                        # isi array di sebelah nilai yang dicek ($t5+4)
ceklagi:
move $t1, $t5                # $t1=$t5+4
addi $t1,4
sw $t6, arrint($t1)            # menggeser nilai yang selesai diperiksa($t6) satu tempat ke kanan

beqz $t5, isi_int            # jika $t5 telah mencapai 0, tidak perlu mengecek array lagi
addi $t5, -4                # $t5 berkurang 4
lw $t6, arrint($t5)            # meload ke $t6
bgt $t6, $t4, ceklagi        # jika masukan baru lebih kecil dari $t6, ceklagi
addi $t5,4                        # jika masukan baru lebih besar, $t5+4
isi_int:
sw $t4, arrint($t5)            # isi array di sebelah nilai yang dicek ($t5+4)
addi $t3,4                    # siapkan indeks untuk masukan baru selanjutnya
jr $ra                                # kembali ke langkah setelah insort

sort_float:
mov.d $f2,$f0                    # menyimpan masukan pecahan ke $f2
move $t5,$t3                    # menyimpan indeks masukan ke $t5
beqz $t3, isi_float                # untuk masukan pertama ($t3==0), langsung isi array
addi $t5, -8                    # $t5 berkurang 8, menunjuk isi array sebelumnya
l.d $f4, arrfloat($t5)            # meload isi array sebelumnya ke $f4
c.lt.d $f2, $f4                    # jika masukan baru lebih kecil dari array sebelumnya, ke ceklagi2
bc1t ceklagi2
addi $t5, 8                        # jika masukan baru lebih besar,
j isi_float                        # isi array di sebelah nilai yang dicek ($t5+8)
ceklagi2:
move $t1, $t5                # $t1=$t5+4
addi $t1,8
s.d $f4, arrfloat($t1)        # menggeser nilai yang selesai diperiksa($t6) satu tempat ke kanan

beqz $t5, isi_float            # jika $t5 telah mencapai 0, tidak perlu mengecek array lagi
addi $t5, -8                # $t5 berkurang 8
l.d $f4, arrfloat($t5)        # meload ke $t6
c.lt.d $f2, $f4                # jika masukan baru lebih kecil dari $t6, ceklagi2
bc1t ceklagi2
addi $t5,8                        # jika masukan baru lebih besar, $t5+8
isi_float:
s.d $f2, arrfloat($t5)        # isi array di sebelah nilai yang dicek ($t5+4)
addi $t3,8                    # siapkan indeks untuk masukan baru selanjutnya
jr $ra                                # kembali ke langkah setelah insort

sort_char:
lb $t4,($a0)                    # menyimpan masukan karakter ke $t4
move $t5,$t3                    # menyimpan indeks masukan ke $t5
beqz $t3, isi_char                # untuk masukan pertama ($t3==0), langsung isi array
addi $t5, -1                    # $t5 berkurang 1, menunjuk isi array sebelumnya
lb $t6, arrchar($t5)            # meload isi array sebelumnya ke $t6
bgt $t6, $t4, ceklagi3            # jika masukan baru lebih kecil dari array sebelumnya, ke ceklagi3
addi $t5, 1                        # jika masukan baru lebih besar,
j isi_char                        # isi array di sebelah nilai yang dicek ($t5+1)
ceklagi3:
move $t1, $t5                # $t1=$t5+1
addi $t1,1
sb $t6, arrchar($t1)        # menggeser nilai yang selesai diperiksa($t6) satu tempat ke kanan

beqz $t5, isi_char            # jika $t5 telah mencapai 0, tidak perlu mengecek array lagi
addi $t5, -1                # $t5 berkurang 1
lb $t6, arrchar($t5)        # meload ke $t6
bgt $t6, $t4, ceklagi3        # jika masukan baru lebih kecil dari $t6, ke ceklagi3
addi $t5,1                        # jika masukan baru lebih besar, $t5+1
isi_char:
sb $t4, arrchar($t5)        # isi array di sebelah nilai yang dicek ($t5+4)
addi $t3,1                    # siapkan indeks untuk masukan baru selanjutnya
jr $ra                                # kembali ke langkah setelah insort
#>>>>>>>>>  end of insort  <<<<<<<<<<<#
#>>>>>>>>> input_minsort <<<<<<<<<<<<#
.data
str13: .asciiz “<> masukan ke-”
str14: .asciiz “: ”
.text
input_minsort:
la $a0, str13                         # menampilkan tulisan ‘<> masukan ke-‘
li $v0, 4
syscall

move $a0, $s0
li $v0, 1                            # menampilkan N
syscall

la $a0, str14
li $v0, 4                            # menampilkan ‘:’
syscall

beq $t2,105, input.min.int            # branch sesuai jenis input
beq $t2,112, input.min.float
beq $t2,107, input.min.char

input.min.int:                        # >>> input integer <<<
li $v0,5                        # meminta masukan
syscall

sw $v0, arrint($t3)                # memasukkannya ke array
addi $t3,4                        # indeks array bertambah
jr $ra                            # jump ke instruksi setelah input_minsort
input.min.float:                    # >>> input pecahan <<<
li $v0,7                        # meminta masukan
syscall

s.d $f0, arrfloat($t3)            # memasukkannya ke array
addi $t3,8                        # indeks array bertambah
jr $ra                            # jump ke instruksi setelah input_minsort
input.min.char:                        # >>> input karakter <<<
li $v0,8                        # meminta masukan dan memasukkannya ke array
la $a0, arrchar($t3)
li $a1,1024
syscall

addi $t3,1                        # indeks array bertambah
jr $ra                            # jump ke instruksi setelah input_minsort
#>>>>>> end of input_minsort <<<<<<<<#
#>>>>>>   minsort  <<<<<<<<<<<<<#
.text
minsort:
li $s7,1                        # $s7 = 1
li $s4,0                        # $s4 = 0

move $s6, $s1                    # $s6 = N-1
addi $s6,-1

beq $t2,105, sort.min.int            # branch sesuai jenis input
beq $t2,112, sort.min.float
beq $t2,107, sort.min.char

sort.min.int:                        # >>> minsort untuk integer <<<
cari_iMin:                        # >>> mencari indeks dari array yang nilainya

#minimum untuk arrint[$s4..N]<<<
move $s2, $s4                # iMin <- $s4

move $s8,$s7                # $s8 = $s7+1
addi $s8,1

move $s3, $s4                # $s3 = $s4+4
addi $s3, 4

putar:
lw $t4, arrint($s2)        # $t4 = arrint[iMin]
lw $t5, arrint($s3)        # $t5 = arrint[$s3]

blt $t4,$t5, tidaktukar    # if ($t5 < $t4) {iMin <- $s3}
move $s2, $s3

tidaktukar:
addi $s3,4            # $s3 = $s3+4
addi $s8,1            # $s8 traversal [$s7+1 .. N]
ble $s8, $s1, putar

#iMin sudah ketemu:
lw $t4, arrint($s2)            # tukar arrint[iMin] dangan arrint[$s4]
lw $t5, arrint($s4)            # (memindah arrint[iMin] ke paling kiri)

sw $t4, arrint($s4)
sw $t5, arrint($s2)

addi $s4, 4                # $s4 = $s4 +4
addi $s7, 1                # $s7 traversal [1 .. N]
ble $s7, $s6, cari_iMin
jr $ra                    # jump ke instruksi setelah minsort

sort.min.float:                        # >>> minsort untuk pecahan <<<
cari_iMin.float:                # >>> mencari indeks dari array yang nilainya

# minimum untuk arrfloat[$s4..N] <<<
move $s2, $s4                # iMin <- $s4

move $s8,$s7                # $s8 = $s7+1
addi $s8,1

move $s3, $s4                # $s3 = $s4+8
addi $s3, 8

putar.float:
l.d $f4, arrfloat($s2)            # $f4 = arrfloat[iMin]
l.d $f6, arrfloat($s3)            # $f6 = arrfloat[$s3]

c.lt.d $f4,$f6                    # if ($t5 < $t4) {iMin <- $s3}
bc1t tidaktukar.float

move $s2, $s3

tidaktukar.float:
addi $s3,8                    # $s3 = $s3+8
addi $s8,1                    # $s8 traversal [$s7+1 .. N]
ble $s8, $s1, putar.float

#iMin sudah ketemu:
l.d $f4, arrfloat($s2)                # tukar arrfloat[iMin] dangan arrfloat[$s4]
l.d $f6, arrfloat($s4)                # (memindah arrfloat[iMin] ke paling kiri)

s.d $f4, arrfloat($s4)
s.d $f6, arrfloat($s2)

addi $s4, 8                        # $s4 = $s4 +8
addi $s7, 1                        # $s7 traversal [1 .. N]
ble $s7, $s6, cari_iMin.float

jr $ra                            # jump ke instruksi setelah minsort

sort.min.char:                                # >>> minsort untuk karakter <<<
cari_iMin.char:                            # >>> mencari indeks dari array yang nilainya minimum untuk arrfloat[$s4..N] <<<
move $s2, $s4                        # iMin <- $s4

move $s8,$s7                        # $s8 = $s7+1
addi $s8,1

move $s3, $s4                        # $s3 = $s4+1
addi $s3, 1

putar.char:
lb $t4, arrchar($s2)            # $t4 = arrchar[iMin]
lb $t5, arrchar($s3)            # $t5 = arrfloat[$s3]

blt $t4,$t5, tidaktukar.char    # if ($t5 < $t4) {iMin <- $s3}
move $s2, $s3

tidaktukar.char:
addi $s3,1                    # $s3 = $s3+1
addi $s8,1                    # $s8 traversal [$s7+1 .. N]
ble $s8, $s1, putar.char

lb $t4, arrchar($s2)                # tukar arrfloat[iMin] dangan arrfloat[$s4]
lb $t5, arrchar($s4)                # (memindah arrfloat[iMin] ke paling kiri)

sb $t4, arrchar($s4)
sb $t5, arrchar($s2)

addi $s4, 1                        # $s4 = $s4 +1
addi $s7, 1                        # $s7 traversal [1 .. N]
ble $s7, $s6, cari_iMin.char

jr $ra                            # jump ke instruksi setelah minsort
#>>>> end of minsort<<<<<<<<<<<<<#
#>>>>>>tampilkan<<<<<<<<<<<<<<#
.data
str5: .asciiz “urutan ”
str6: .asciiz ” masukan anda adalah: \n”
newline: .asciiz “\n”
tempchar: .space 8
.text
tampilkan:
li $t7,0                          # indeks untuk menampilkan isi array
li $s3,1                        # counter, bertambah 1 hingga $s3 = N

li $v0,4                        # menampilkan tulisan ‘urutan’
la $a0, str5
syscall
move $a0, $s1                    # menampilkan N
li $v0, 1
syscall
li $v0,4                        # menampilkan tulisan ‘masukan anda…’
la $a0, str6
syscall

beq $t2,105, print_int            # branch sesuai jenis masukan
beq $t2,112, print_float
beq $t2,107, print_char

print_int:                        # >>> menampilkan integer <<<
lw $a0, arrint($t7)
li $v0,1                    # menampilkan isi arrint($t7)
syscall
li $v0,4                    # enter
la $a0, newline
syscall

addi $t7,4                    # indeks bertambah 4
addi $s3, 1                    # counter bartambah 1
ble $s3,$s1, print_int        # print_int hingga $s3 = N
jr $ra                            # kembali ke langkah setelah ‘tampilkan’

print_float:                    # >>> menampilkan pecahan <<<
l.d $f12, arrfloat($t7)
li $v0,3                    # menampilkan isi arrint($t7)
syscall
li $v0,4                    # enter
la $a0, newline
syscall

addi $t7,8                    # indeks bertambah 8
addi $s3, 1                    # counter bartambah 1
ble $s3,$s1, print_float    # print_int hingga $s3 = N
jr $ra                            # kembali ke langkah setelah ‘tampilkan’

print_char:                        # >>> menampilkan karakter <<<
lb $t8, arrchar($t7)        # load arrchar($t7) ke $t8
sb $t8, tempchar($0)        # menyimpannya di tempchar($0), sehingga bisa ditampilkan per karakter

la $a0, tempchar($0)        # menampilkan tempchar($0)
li $v0,4
syscall

li $v0,4                    # enter
la $a0, newline
syscall

addi $t7,1                    # indeks bertambah 1
addi $s3, 1                    # counter bartambah 1
ble $s3,$s1, print_char        # print_int hingga $s3 = N
jr $ra                            # kembali ke langkah setelah ‘tampilkan’
#>>>>>>>>end of tampilkan<<<<<<<<<<<<<<<<#

#>>>>>>>>keluar<<<<<<<<<<<<<#
.text
keluar:
li $v0,10                        # keluar program
syscall
#>>>> end of everything, hehe… <<<<<<<<<#

  1. yume
    May 15, 2011 at 9:36 am

    pusing juga bacanya, anyway saya tetep butuh panduan ngoding dalam bahasa assembly. untuk fungsi yang misalnya f(x)=4x^3+3X^2+5 itu caranya gimana ya? soalnya taunya cuma yang pertambahan dan perkalian 2 buah bilangan.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: