Kajian Algoritma Modul Pencetakan Pembimbing Akademik Jurusan Ilmu Komputer

Vol. 3, No. 2, 2015

Jurnal Komputasi

©2014 Ilmu Komputer Unila Publishing Network all right reserved

Kajian Algoritma Modul Pencetakan Pembimbing Akademik Jurusan Ilmu Komputer 1

Dwi Sakethi, 2Didik Kurniawan dan 3Choiranti Efrina 1

Jurusan Ilmu Komputer FMIPA Unila Jurusan Ilmu Komputer FMIPA Unila 3 Jurusan Ilmu Komputer FMIPA Unila 2

Abstract The list of academic advisor utility is an utility that was developed to help the administration process of computer science major. Previously, it's only used bubble sort sorting algorithm. We try to compare the bubble sort algorithm with selection sort and quick sort to determine the quickest algorithm which will be implemented in other major by searching the worst case (slowest execution time per unit) and best case (fastest execution time per unit). The result is quick < selection < bubble. Selection sort algorithm is proven to be the quickest when n < 26. But the cademic advisor data that are used in the utility is more than 26. So in this research, the quicksort algorithm is the fastest algorithm. Keywords: Bubble Sort, Selection Sort, Quick Sort, Worst Case, Best Case.

1

Pendahuluan

Menurut Weiss(2007), Algoritma merupakan sekumpulan instruksi yang harus dilakukan untuk menyelesaikan masalah. Setelah algoritma tersebut terbukti benar, maka langkah yang tidak kalah penting lainnya adalah untuk menentukan seberapa banyak sumberdaya, apakah waktu atau ruang yang algoritma tersebut butuhkan dan menurut Azizah(2013), Algoritma yang efisien adalah algoritma yang meminimumkan kebutuhan waktu dan ruang, pengukuran efisien atau tidaknya yaitu dengan menganalisis beberapa algoritma untuk mengidentifikasi satu algoritma yang paling efisien. Besaran yang digunakan untuk menjelaskan model pengukuran waktu dan ruang ini adalah kompleksitas algoritma yang terbagi menjadi dua yaitu kompleksitas waktu dan kompleksitas ruang. Kecenderungan saat ini, ruang (memori utama) yang disediakan semakin besar yang artinya kapasitas data yang diproses juga semakin besar. Namun waktu yang diperlukan untuk menjalankan suatu algoritma harus semakin cepat. Oleh karena itu, algoritma sorting bubble sort yang digunakan pada utility sebelumnya akan dibandingkan dengan selection sort dan quicksort untuk menentukan algoritma yang paling cepat dengan menggunakan analisis kompleksitas waktu. Menurut Weis (2007), tidak bisa hanya menyusun algoritma tanpa menghitung running time karena ketika running time membutuhkan waktu berharihari, bahkan mungkin berbulan-bulan, maka algoritma tersebut tidak akan digunakan.

2

Metode

Penelitian yang dilakukan, melalui beberapa tahap yaitu: 1. Studi Literatur 2. Analisis Program 3. Merancang Program 4. Implementasi 5. Pengujian 6. Kesimpulan

http://jurnal.fmipa.unila.ac.id/index.php/komputasi

Hal. 8 dari 168

Vol. 3, No. 2, 2015

Jurnal Komputasi


Setelah melalui tahapan studi literatur, tahapan selanjutnya yaitu menganalisis program Daftar Pembimbing Akademik yang telah dibuat oleh Choiranti Efrina untuk memenuhi Kerja Praktiknya. Hasil analisis dituangkan ke dalam rancangan algoritma. Pada tahap ini juga dilakukan perancangan database dan interface program. Tahap selanjutnya adalah implementasi hasil analisis algoritma dalam kode program. Pembuatan program menggunakan bahasa pemrograman PHP dan database MySQL. Setelah mengimplementasikan hasil analisis ke dalam program yang baru maka tahap selanjutnya adalah menguji program yang baru menggunakan Running Time dan analisis kompleksitas waktu algoritma. Tahap akhir penelitian adalah menarik kesimpulan manakah algoritma sorting yang waktu menjalankan algoritmanya paling cepat.

3

Pembahasan

Terdapat dua masalah yang dikaji, yaitu kasus terburuk (worst case) dan kasus terbaik (best case). Kasus terburuk (worst case) terjadi ketika jumlah statement yang dieksekusi program paling banyak. Sebaliknya, kasus terbaik (best case) terjadi ketika jumlah statement yang dieksekusi program paling sedikit. Telah diketahui sebelumnya bahwa total running time sangat dipengaruhi oleh total statement yang dieksekusi. Dengan demikian, running time kasus terburuk dan running time kasus terbaik, berturut-turut, melambangkan waktu paling lama dan waktu paling singkat yang dibutuhkan oleh algoritma 3.1 Garis Besar Algoritma Sistem 1. User memilih jenis algoritma pengurutan dari menu yang tersedia. Setelahnya, user memilih nama fakultas, nama jurusan, dan tahun ajaran dari menu dropdown. 2. Sistem mengambil data NPM mahasiswa aktif pada tahun ajaran yang diinput-kan dari tabel krs_mahasiswa. Maksud ”mahasiswa aktif” di sini adalah mahasiswa yang mengisi KRS. 3. Sistem melengkapi data mahasiswa aktif ini dengan nama dan dosen PA-nya masingmasing, yang diperoleh dari tabel mahasiswa. Tabel mahasiswa hanya berisikan detail mahasiswa yang terdaftar di Universitas Lampung. Field dalam tabel ini di antaranya adalah nama lengkap, tempat tanggal lahir, dan alamat. Namun, tidak semua mahasiswa yang terdaftar ini mengisi KRS. Oleh karena itu, data mahasiswa aktif diambil dari tabel krs_mahasiswa, bukan mahasiswa. 4. Data diurut ascending berdasarkan NIP dosen. Proses ini berimbas pada mengelompoknya mahasiswa-mahasiswa yang ber-PA sama dalam satu blok. 5. Data mahasiswa bimbingan tiap PA diurutkan berdasarkan NPM-nya. 6. Menampilkan data dosen PA beserta mahasiswa bimbingan akademiknya dalam bentuk tabel.


Hal. 9 dari 168

Vol. 3, No. 2, 2015

Jurnal Komputasi


3.2 Analisis running time Kasus Terburuk (Worst Case) 3.2.1

Algoritma Bubble Sort

Kode bubble sorting NIP pembimbing akademik for ($i = 1; $i < $jum; ++$i) { . . . . . . . . . . . . . . . . . . . . . . . (1) for ($j = 0; $j < $jum-1; ++$j) { if($nip[$j]>$nip[$j+1]){ $temp=$nip[$j];$nip[$j]=$nip[$j+1];$nip[$j+1]=$temp; $temp=$nama dos[$j]; . . . . .. . . . . . . . . . . . . . . . . . . . . . (5) $nama dos[$j]=$nama dos[$j+1]; $nama dos[$j+1]=$temp; $temp=$npm[$j];$npm[$j]=$npm[$j+1];$npm[$j+1]=$temp; $temp=$nama mhs[$j]; $nama mhs[$j]=$nama mhs[$j+1]; . ..

. . . . . . . . . . . . . . . . . . (10)

$nama mhs[$j+1]=$temp; } } } . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .(14)

running time per unit sintaks Baris 1

Baris 2

Baris 3 Baris 4 Baris 5-11

$i= 1

1

$i < $jum

1

++$i

1

$j = 0

1

$j < $jum-1 ++$j

2 1

$nip[$j]>$nip[$j+1]

2

$temp=$nip[$j]

1

$nip[$j]=$nip[$j+1] $nip[$j+1]=$temp

2 2

$temp=$nama dos[$j]

1

$nama_dos[$j]= $nama_dos[$j+1] $nama_dos[$j+1]=$temp $temp=$npm[$j] $npm[$j]= $npm[$j+1] $npm[$j+1]=$temp $temp=$nama mhs[$j] $nama_mhs[$j]= $nama_mhs[$j+1] $nama_mhs[$j+1]=$temp

2


2 1 2 2 1 2 2

Hal. 10 dari 168

Vol. 3, No. 2, 2015

Jurnal Komputasi


Perhitungan

Kode bubble sorting NPM mahasiswa for ($k = $batas atas+1; $k < $i; ++$k){ . . . . . . . . for ($j = $batas atas; $j < $i-1; ++$j) { if($npm[$j] > $npm[$j+1]){ $temp = $npm[$j]; $npm[$j] = $npm[$j+1]; $npm[$j+1] $temp = $nama_mhs[$j]; $nama_mhs[$j] = $nama_mhs[$j+1]; . . . . . . . . . $nama_mhs[$j+1] = $temp; } } } . . . . . . . . . . . . . . . . . . . . . . . . . . .

running time per unit sintaks Baris 15 $k = $batas atas+1 $k < $i ++$k

1 1 1

Baris 16

$j = $batas atas $j < $i-1 ++$j

1 2 1

Baris 17

$npm[$j]>$npm[$j+1]

2

Baris 18

$temp=$npm[$j] $npm[$j]=$npm[$j+1] $npm[$j+1]=$temp

1 2 2

Baris 19-21

$temp=$nama mhs[$j] $nama mhs[$j]= $nama mhs[$j+1] $nama mhs[$j+1]=$temp

1 2


. . . . . . . . . . (15)

= $temp; . . . . . . . . . . (20)

. . . . . . . . . . (24)

2

Hal. 11 dari 168

Vol. 3, No. 2, 2015

Jurnal Komputasi


Perhitungan

Perhitungan Akhir

3.2.2

Algoritma Selection Sort

Kode selection sorting NIP pembimbing akademik for ($i = 0; $i < $jum-1; ++$i) { . . . . . . . . . . . . . . . . . . . . . . (1) $min nip = $nip[$i]; $min nama dos = $nama dos[$i]; $min npm = $npm[$i]; $min nama mhs = $nama mhs[$i]; . . . .

. . . . . . . . . . . . . . . . . . (5)

$minKey = $i; for ($j = $i+1; $j < $jum; ++$j) { if($nip[$j] < $min nip){ $minKey = $j; . . . . . . . . . . . . . . . . . . . . . . . . . . . ..(10) $min nip = $nip[$j]; $min nama dos = $nama dos[$j]; $min npm = $npm[$j]; $min nama mhs = $nama mhs[$j]; } . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (15) }


Hal. 12 dari 168

Vol. 3, No. 2, 2015

Jurnal Komputasi


$nip[$minKey] = $nip[$i]; $nama dos[$minKey] = $nama dos[$i]; $npm[$minKey] = $npm[$i]; . . . . . . . . . . . . . . . . . . . . . . . . . (20) $nama mhs[$minKey] = $nama mhs[$i]; $nip[$i] = $min nip; $nama dos[$i] = $min nama dos; $npm[$i] = $min npm; $nama mhs[$i] = $min nama mhs; } . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . (26)

running time per unit sintaks Baris 1

Baris 2-6

Baris 8

$i = 0

1

$i < $jum-1

2

++$i

1

$min nip = $nip[$i]

1

$min nama dos = $nama dos[$i] $min npm = $npm[$i] $min nama mhs = $nama mhs[$i] $minKey = $i

1

$j = $i+1 $j < $jum ++$j

Baris 9

Baris 18-25

1 1 1 1

if($nip[$j] < $min nip)

Baris 10-14

1 1

1

$minKey = $j

1

$min nip = $nip[$j] $min nama dos = $nama dos[$j] $min npm = $npm[$j] $min nama mhs = $nama mhs[$j]

1 1

$nip[$minKey] = $nip[$i]

1

$nama dos[$minKey]= $nama dos[$i] $npm[$minKey] = $npm[$i] $nama mhs[$minKey]= $nama mhs[$i] $nip[$i] = $min nip $nama dos[$i] = $min nama dos $npm[$i] = $min npm $nama mhs[$i] = $min nama mhs

1


1 1

1 1 1 1 1 1

Hal. 13 dari 168

Vol. 3, No. 2, 2015

Jurnal Komputasi


Perhitungan

3.2.3

Algoritma Quick Sort

Kode selection sorting NPM mahasiswa for ($k = $batas_atas; $k < $i-1; ++$k){ . . . . . . . . . . . . . . . . . . (27) $min_npm = $npm[$k]; $min_nama_mhs = $nama mhs[$k]; $minKey = $k; for ($l = $k+1; $l < $i; ++$l) { if($npm[$l] < $min_npm){ $minKey=$l; $min_npm=$npm[$l]; . . . . . . . . . . . . . . . . . . . . . . . . . (35) $min_nama_mhs=$nama_mhs[$l]; } } $npm[$minKey]=$npm[$k]; . . . . . . . . . . . . . . . . . . . . . . (40) $nama_mhs[$minKey]=$nama_mhs[$k]; $npm[$k]=$min_npm; $nama_mhs[$k]=$min_nama_mhs; } . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (44)

running time per unit sintaks Baris 27 $k = $batas atas

Baris 28-30

Baris 32

1

$k < $i-1 ++$k

2 1

$min npm = $npm[$k]

1

$min nama mhs = $nama mhs[$l] $minKey = $k

1

$l = $k+1

1

$l < $i ++$l

1 1


1

Hal. 14 dari 168

Vol. 3, No. 2, 2015

Jurnal Komputasi


Baris 33

if($npm[$l] < $min npm)

1

Baris 34-36

$minKey=$l

1

$min npm = $npm[$l] $min nama mhs = $nama mhs[$l]

1 1

$npm[$minKey] = $npm[$k] $nama mhs[$minKey] = $nama mhs[$k] $npm[$k] = $min npm $nama mhs[$k] = $min nama mhs

1

Baris 40-43

1 1 1

Perhitungan

Perhitungan Akhir


Hal. 15 dari 168

Vol. 3, No. 2, 2015

Jurnal Komputasi


3.2.3 Algoritma Quick Sort Kode quick sorting NIP pembimbing akademik function partition(&$arg1,&$arg2,&$arg1_name,&$arg2_name,$left, $right, &$sortx, &$file,&$sortA,&$sortB)) { . . . . . . . . . . . . . . . . (1) $pivot index = $left; swap($arg1[$pivot index],$arg1[$right],$sortx,$sortA); swap($arg1_name[$pivot index],$arg1_name[$right],$sortx,$sortA); . . . . . .(5) swap($arg2[$pivot index],$arg2[$right],$sortx,$sortB); swap($arg2_name[$pivot index],$arg2_name[$right],$sortx,$sortB); $pivot = $arg1[$right]; . . . . . . . . . . . . . . . . . . . . . . . . . . (9) $i = $left-1; for($j = $left ; $j < $right ; $j++) { if($arg1[$j] <= $pivot) { $i++; swap($arg1[$i],$arg1[$j],$sortx, $sortA); . . . . . . . . . . . . . .(15) swap($arg1_name[$i],$arg1_name[$j],$sortx,$sortA); swap($arg2[$i],$arg2[$j],$sortx, $sortB); swap($arg2_name[$i],$arg2_name[$j],$sortx,$sortB); } } . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (20) swap($arg1[$i+1],$arg1[$right],$sortx,$sortA); swap($arg1_name[$i+1],$arg1_name[$right],$sortx,$sortA); swap($arg2[$i+1],$arg2[$right]$sortx, $sortB); swap($arg2_name[$i+1],$arg2_name[$right],$sortx,$sortB); . . . . . . . . . (25) i+=1; return $i; } . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .(29) function quickSort(&$arg1,&$arg2,&$arg1_name,&$arg2_name,$left, $right,&$sortx, &$sortA, &$sortB) { if($left < $right) { $pivot index = partition($arg1,$arg2,$arg1_name,$arg2_name,$left, $right,$sortx, $sortA, $sortB); quickSort($arg1,$arg2,$arg1_name,$arg2_name,$left,$pivot index-1, $sortx, $sortA, $sortB); quickSort($arg1,$arg2,$arg1_name,$arg2_name,$pivot index+1, $right,$sortx, $sortA, $sortB); . . . . . . . . . . . . . .. . . . . . (35) } } function swap(&$a,&$b,&$sortx,&$sort) { $tmp = $a; . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (40) $a = $b; $b = $tmp; } $A=1; $B=1; quickSort($nip,$npm,$nama dos,$nama mhs,0,$jum-1,$sortx,$A,$B) . . . . . . (46)


Hal. 16 dari 168

Vol. 3, No. 2, 2015

Jurnal Komputasi


running time per unit sintaks swap() Baris 40-42 $tmp=$a

1

$a=$b $b=$tmp

1 1

partition() Baris 2,4-7

$pivot index = $left

1

swap($arg1[$pivot index], $arg1[$right]) swap($arg1 name[$pivot index], $arg1 name[$right]) swap($arg2[$pivot index], $arg2[$right]) swap($arg2 name[$pivot index], $arg2 name[$right])

3

Baris 9

$pivot = $arg1[$right]

1

Baris 11

$i = $left-1

1

Baris 12

Baris 13-15

Baris 16-18

Baris 22-25

Baris 27-28

3 3 3

$j = $left

1

$j < $right $j++

1 1

if($arg1[$j] <= $pivot)

1

$i++ swap($arg1[$i],$arg1[$j])

1 3

swap($arg1 name[$i], $arg1 name[$j])

3

swap($arg2[$i], $arg2[$j]) swap($arg2 name[$i], $arg2 name[$j])

3 3

swap($arg1[$i+1], $arg1[$right])

3

swap($arg1 name[$i+1], $arg1 name[$right] swap($arg2[$i+1], $arg2[$right]) swap($arg2 name[$i+1], $arg2 name[$right])

3

$i+=1

1

return $i

quickSort() Baris 31-35 if($left

3 3

< $right)

quickSort(1) quickSort(n-1)


1

1 T(1) T (n − 1)

Hal. 17 dari 168

Vol. 3, No. 2, 2015

Jurnal Komputasi


Perhitungan

Kode quick sorting NPM mahasiswa function partition(&$arg1,&$arg2,&$arg1_name,&$arg2_name,$left, $right, &$sortx, &$file,&$sortA,&$sortB)) { . . . . . . . .. . . . . . . . (47) $pivot index = $left; swap($arg1[$pivot index],$arg1[$right],$sortx,$sortA); swap($arg1_name[$pivot index],$arg1_name[$right],$sortx,$sortA); swap($arg2[$pivot index],$arg2[$right],$sortx,$sortB); swap($arg2_name[$pivot index],$arg2_name[$right],$sortx,$sortB); $pivot = $arg1[$right]; . . . . . . . . . .

. . . . . . . . . . . . . . . (55)

$i = $left-1; for($j = $left ; $j < $right ; $j++) { if($arg1[$j] <= $pivot) { $i++; . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . (60) swap($arg1[$i],$arg1[$j],$sortx, $sortA); swap($arg1_name[$i],$arg1_name[$j],$sortx,$sortA); swap($arg2[$i],$arg2[$j],$sortx, $sortB); swap($arg2_name[$i],$arg2_name[$j],$sortx,$sortB); } . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . (65) } swap($arg1[$i+1],$arg1[$right],$sortx,$sortA); swap($arg1_name[$i+1],$arg1_name[$right],$sortx,$sortA); swap($arg2[$i+1],$arg2[$right]$sortx, $sortB); . . . . . . . . . . . . . . . (70) swap($arg2_name[$i+1],$arg2_name[$right],$sortx,$sortB); $i+=1; return $i; } . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (75) function quickSort(&$arg1,&$arg2,&$arg1_name,&$arg2_name,$left, $right,&$sortx, &$sortA, &$sortB) { if($left < $right) { $pivot index = partition($arg1,$arg2,$arg1_name,$arg2_name,$left, $right,$sortx, $sortA, $sortB);


Hal. 18 dari 168

Vol. 3, No. 2, 2015

Jurnal Komputasi


quickSort($arg1,$arg2,$arg1_name,$arg2_name,$left,$pivot index-1, $sortx, $sortA, $sortB); . . . . . . . . . . . . . . . . . . . . . . (80) quickSort($arg1,$arg2,$arg1_name,$arg2_name,$pivot index+1, $right,$sortx, $sortA, $sortB); } } function swap(&$a,&$b,&$sortx,&$sort) { . . . . . . . . . . . . . . . . . . (85) $tmp = $a; $a = $b; $b = $tmp; } $A=1; $B=0; . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . (90) quickSort($npm, $nip, $nama_mhs, $nama_dos, $batas_atas, $i-1, $sorty,$A,$B)

running time per unit sintaks swap() Baris 86-88 $tmp=$a

partition() Baris 48,50,51

1

$a=$b $b=$tmp

1 1

$pivot index = rand($left,$right)

1

swap($arg1[$pivot index], $arg1[$right]) swap($arg1 name[$pivot index], $arg1 name[$right]

3

Baris 55

$pivot = $arg1[$right]

1

Baris 57

$i = $left-1

1

Baris 58

$j = $left

1

$j < $right $j++

1 1

Baris 59-62

Baris 68-69

Baris 73-74 quickSort() Baris 78-81

3

if($arg1[$j] <= $pivot)

1

$i++ swap($arg1[$i],$arg1[$j]) swap($arg1 name[$i],$arg1 name[$j])

1 3 3

swap($arg1[$i+1], $arg1[$right])

3

swap($arg1 name[$i+1], $arg1 name[$right])

3

$i+=1

1

return $i

1

if($left < $right) quickSort(1) quickSort(n-1)


1 T(1) T (n − 1)

Hal. 19 dari 168

Vol. 3, No. 2, 2015

Jurnal Komputasi


Perhitungan

Perhitungan Akhir


Hal. 20 dari 168

Vol. 3, No. 2, 2015

Jurnal Komputasi


3.3 Menguji Akurasi Hasil Analisis Berikut running time hasil analisis tiap algoritma yang telah dirangkum :

Hasil lengkap perhitungan running time versi analisis dan versi program dikumpulkan dalam table 1. .1

1

4

Kesimpulan

Kesimpulan yang dapat diambil dari penelitian ini adalah; Perhitungan analisis algoritma sorting buble, selection dan quick sort menggunakan > 1499 data. Membuktikan bahwa ketika data tidak lebih besar dari 26 data, algoritma quick sortlah sorting yang paling cepat Nomenklatur dituliskan dalam urutan alfabetis. Formatnya adalah huruf Roman yang diikuti oleh simbol-simbol Yunani, yang kemudian diikuti dengan subskrip dan superskrip. T(n)

=

Running Time yang dihasilkan dari proses penyortingan sebanyak data yang dikeluarkan oleh query.


Hal. 21 dari 168

Vol. 3, No. 2, 2015

Jurnal Komputasi


T(m) =

5 [1] [2] [3]

[4]

Running Time yang dihasilkan dari proses penyortingan sebanyak jumlah mahasiswa per blok dosen pembimbing akademik.

Referensi McConnel, Jeffrey J.2001. Analysis of Algorithms: An Active Learning Approach. Canada: Jones and Bartlett Publishers Rao, D. D., & Ramesh, B. 2012. Experimental Based Selection Of Best Sorting Algorithm. International Journal Of Modern Engineering Research, 2(4) Singh, A., Monika, V., & Kaur, S. 2013. ASSORTMENT OF DIFFERENT SORTING ALGORITHMS. ASIAN JOURNAL OF COMPUTER SCIENCE & INFORMATION TECHNOLOGY, 1(5) Weis, Mark Allen. 2007. Data Structures and Algorithm Analysis in C. Yogyakarta: Penerbit ANDI.


Hal. 22 dari 168

Kajian Algoritma Modul Pencetakan Pembimbing Akademik Jurusan Ilmu Komputer

Recommend Documents