BAB 2
LANDASAN TEORI
2.1.
Algoritma
Algoritma adalah prosedur komputasi yang didefinisikan dengan baik yang mengambil beberapa nilai yaitu seperangkat nilai sebagai input dan output yang menghasilkan nilai (Sedgewick & Wayne, 2011). Secara umum algoritma merupakan kumpulan perintah untuk menyelesaikan suatu masalah. Perintah-perintah ini dapat diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut dapat berupa apa saja dengan catatan untuk setiap masalah, ada kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma.
Menurut Donald E. Knuth, algoritma yang baik memiliki kriteria sebagai berikut (Sitorus, 2015): 1. Input Suatu algoritma harus memiliki 0 (nol) atau lebih masukan (input). Artinya, suatu algoritma itu dimungkinkan tidak memiliki masukan secara langsung dari pengguna tetapi dapat juga memiliki beberapa masukan. Algoritma yang tidak memiliki masukan secara langsung dari pengguna, maka semua data dapat diinisialisaikan atau dibangkitkan dalam algoritma. 2. Output Suatu algoritma harus memiliki satu atau lebih algoritma. Suatu algoritma yang tidak memiliki keluaran (output) adalah suatu algoritma yang sia sia, yang tidak perlu dilakukan. Algoritma dibuat untuk tujuan menghasilkan sesuatu yang diinginkan, yaitu berupa hasil keluaran.
Universitas Sumatera Utara
3. Finiteness Setiap pekerjaan yang dikerjakan pasti berhenti. Demikian juga algoritma harus dapat dijamin akan berhenti setelah melakukan sejumlah langkah proses. 4. Definiteness Algoritma tersebut tidak menimbulkan makna ganda (ambiguous). Setiap baris aksi/pernyataan dalam suatu algoritma harus pasti, artinya tidak menimbulkan penafsiran lain bagi setiap pembaca algoritma, sehingga memberikan output yang sesuai dengan yang diharapkan oleh pengguna. 5. Effectiveness Setiap langkah algoritma harus sederhana sehingga dikerjakan dalam waktu yang wajar.
2.2. Pengurutan Algoritma pengurutan adalah proses menyusun kembali rentetan objek-objek untuk meletakkan objekdari suatukumpulan data ke dalam urutan yang logis (Cormen, 2009).Pada dasarnya, pengurutan(sorting) membandingkanantar data atau elemen berdasarkan kriteria dankondisi tertentu (Indrayana & Ihsan, 2005).Pengurutan dapat dilakukan dari nilai terkecil ke nilai terbesar (ascending) atau sebaliknya (descending). Ada dua kategori pengurutan (Suarga, 2012): 1. Pengurutan internal Pengurutan internal adalah pengurutan yang dilaksanankan hanya dengan menggunakan memori komputer, pada umumnya digunakan bila jumlah elemen tidak terlalu banyak. 2. Pengurutan eksternal Pengurutan eksternal adalah pengurutan yang dilaksanakan dengan bantuan memori virtual atau harddisk karena jumlah elemen yang akan diurutkan terlalu banyak.
Universitas Sumatera Utara
2.3. Klasifikasi Algoritma Pengurutan Klasifikasi algoritma-algoritma pengurutan dibedakan berdasarkan (Erzandi,2009): 1. Kompleksitas perbandingan antar elemen terkait dengan kasus terbaik, rata-rata dan terburuk 2. Kompleksitas pertukaran elemen, terkait dengan cara yang digunakan elemen setelah dibandingkan 3. Penggunaan memori 4. Rekursif atau tidak rekursif 5. Proses pengurutannya(metode penggunaannya) Klasifikasi algoritma pengurutan berdasarkan proses pengurutannya sebagai berikut (Putranto, 2007): 1. Exchange Sort Dalam prosesnya, algoritma-algoritma pengurutan yang diklasifikasikan sebagai exchange sort melakukan pembandingan antar data, dan melakukan pertukaran apabila urutan yang didapat belum sesuai. Contohnya: bubble sort, cocktail sort, comb sort, gnome sort, quick sort. 2. Selection Sort Prinsip utama algoritma dalam klasifikasi ini adalah mencari elemen yang tepat untuk diletakkan di posisi yang telah diketahui, dan meletakkannya di posisi tersebut setelah data tersebut ditemukan. Contohnya: selection sort, heap sort, smooth sort, strand sort. 3. Insertion Sort Algoritma pengurutan yang diklasifikasikan ke dalam kategori ini mencari tempat yang tepat untuk suatu elemen data yang telah diketahui ke dalam subkumpulan data yang telah terurut, kemudian melakukan penyisipan (insertion) data di tempat yang tepat tersebut. Contohnya: insertion sort, shell sort, tree sort, library sort, patience sorting. 4. Merge Sort Dalam algoritma ini kumpulan data dibagi menjadi subkumpulan-subkumpulan yang kemudian sub kumpulan tersebut diurutkan secara terpisah, dan kemudian digabungkan kembali dengan metode merging. Dalam kenyataannya algoritma ini melakukan metode pengurutan merge sort juga untuk mengurutkan subkumpulan
Universitas Sumatera Utara
data tersebut, atau dengan kata lain, pengurutan dilakukan secara rekursif. Contohnya: Merge sort. 5. Non-Comparison Sort Sesuai namanya dalam proses pengurutan data yang dilakukan algoritma ini tidak terdapatpembandingan antardata, data diurutkan sesuai dengan pigeon hole principle. Dalam kenyataanyaseringkali algoritma non-comparison sort yang digunakan tidak murni tanpa pembandingan, yangdilakukan dengan menggunakan algoritma-algoritma pengurutan cepat lainnya untuk mengurutkan subkumpulansubkumpulan datanya. Contohnya: Radix sort, Bucket sort, Counting sort, Pigeonhole sort, Tally sort. Berdasarkan klasifikasi algoritma pengurutanyang sudah dijelaskan maka yang akan dianalisis pada penelitian ini adalah algoritmacocktail shaker sort dan 4 ways mergesort.
2.4. AlgoritmaCocktail Shaker Sort Algoritma cocktail shaker sort adalah variasi kecil dari bubble sort(Knuth, 1973). Pada cocktail shaker sort setiap iterasi dari algoritma terdiri dari dua arah sedangkan pada bubble sortsetiap iterasi dalam satu arah sehingga bubble sorthanya dapat memindahkan mundur satu langkah setiap iterasi.Oleh karena itu, algoritma cocktail shaker sort disebut jugabidirectional bubble sort(Black &Bockholt, 2009). Langkah-langkah algoritma cocktailshaker sortsecara ascendingyaitu: 1. Iterasi dari algoritma ini terdiri dari dua arah. 2. Tahap pertama loopdimulai dari data sebelah kiri. 3. Kemudian dibandingkan antara data pertama dengan data kedua yang berada disebelah kanan data pertama. Jika pada nilai di sebelah kiri lebih besar dari nilai di sebelah kanan maka kedua data tersebut ditukar. Sebaliknya jika nilai data sebelah kiri lebih kecil dari data sebelah kanan maka tidak perlu dilakukan pertukaran. 4. Pada akhir iterasi pertama, nilai terbesar akan berada di akhir. Kemudian nilai tersebut disimpan dan tidak masuk lagi ke dalam data yang ingin diurutkan. 5. Tahap kedua loop melalui kumpulan data dalam arah yang berlawanan yaitu sebelah kanan. 6. Kemudian dibandingkandua data yang diambil dari sebelah kananmenuju kiri.
Universitas Sumatera Utara
7. Lakukan pertukaran data jika data sebelah kanan lebih kecil dari data sebelah kiri. Sebaliknya jika data sebelah kanan lebih besar dari data sebelah kiri maka pertukaran data tidak dilakukan. 8. Lakukan kembali proses tersebut sampai bergerak kembali menuju awal data sehingga diperoleh data pertama yang terkecil. Kemudian nilai tersebut disimpan dan tidak masuk lagi ke dalam data yang ingin diurutkan. 9. Ulangi kembali proses tersebut berulang-ulang sehingga diperoleh data dalam keadaan terurut dengan benar. Contoh proses pengurutan data menggunakan cocktail shaker sort dapat dilihat pada Gambar 2.1. Data yang ingin diurutkan: 31
98
72
14
8
22
Iterasi pertama mulai dari membandingkan 2 data awal yang berwarna merah 31
98
72
14
8
22
31
98
72
14
8
22
Data yang berwarna biru adalah data yang sudah ditukar(swap) 31
72
98
14
8
22
31
72
98
14
8
22
31
72
14
98
8
22
31
72
14
8
98
22
31
72
14
8
98
22
31
72
14
8
22
98
Data yang berwarna hijau adalah data yang sudah benar letak posisinya sehingga disimpan dan tidak ikut lagi dalam proses pengurutan data. Data di sebelah kanan merupakan data terbesar. 31
72
14
8
22
98
Universitas Sumatera Utara
Iterasi kedua dari arah yang berlawanan. 31
72
14
8
22
98
Lakukan terus proses perbandingan sehingga diperoleh nilai data terkecil di sebelah kiri. 31
72
14
8
22
98
31
72
8
14
22
98
31
72
8
14
22
98
31
8
72
14
22
98
31
8
72
14
22
98
Maka diperoleh data terkecil di sebeleh kiri yang berwarna hijau. Data tersebut akan disimpan dan tidak ikut lagi dalam proses pengurutan data. Ulangi kembali proses tersebut berulang-ulang sehingga diperoleh data dalam keadaan terurut dengan benar. 8
31
72
14
22
98
8
31
72
14
22
98
8
31
72
14
22
98
8
31
14
72
22
98
8
31
14
72
22
98
8
31
14
22
72
98
8
31
14
22
72
98
8
14
31
22
72
98
8
14
31
22
72
98
14
22
31
72
98
Data yang sudah terurut: 8
Universitas Sumatera Utara
Gambar 2.1. Proses pengurutan data menggunakan cocktail shaker sort 2.5. Algoritma4 WayMerge Sort Algoritmamerge sort merupakan algoritma yang dicetuskan oleh John von Neuman pada tahun 1945 (Knuth, 1998). Merge sortmenggunakan prinsip divide and conquer. Divide and conquer adalah metode pemecahanmasalah yang bekerja dengan membagi masalah (problem) menjadi beberapa sub-masalah (subproblem) yang lebih kecil, kemudian menyelesaikan masing-masing sub-masalah secara independen dan akhirnya menggabung solusi masing-masing sub-masalah sehingga menjadi solusi masalah semula (Munir, 2005). Pada umumnya, merge sortmembagi data menjadi 2 bagian. Namun pada algoritma 4 way merge sort membagi datamenjadi 4 bagian sehingga diperoleh subdata yang terpisah. Kemudian subdata tersebut diurutkan secara terpisahlalu menggabungkannya hingga diperoleh data dalam keadaan terurut. Proses pengurutan menggunakan 4 way merge sortdapat dilihat pada Gambar 2.2.
Gambar 2.2. Proses pengurutan menggunakan algoritma 4 way merge sort 2.6. Pseudocode Skema lain untuk menyusun algoritma adalah pseudocode. Pseudocode merupakan bentuk informal untuk mendeskripsikan algoritma yang mengikuti struktur bahasa pemrograman.Pseudocode adalah kode yang mirip dengan kode pemrograman sebenarnya(Utami & Raharjo, 2004).
Universitas Sumatera Utara
Tujuan dari penggunaan pseudocode: 1. Lebih mudah dibaca oleh manusia 2. Lebih mudah dipahami 3. Lebih mudah dalam menuangkan ide/hasil pemikiran
2.6.1. Pseudocode cocktail shaker sort Pseudocode algortima cocktail shaker sort sebagai berikut: procedure cocktailShakerSort(A:list of sortable items); do swapped := false for each i in 0 to length( A ) - 2 do: if A[ i ] > A[ i + 1 ] then // menguji apakah kedua elemen dalam urutan yang benar swap( A[ i ], A[ i + 1 ] ) // jika urutannya salah maka tukar posisi swapped := true end if end for if not swapped then // keluar dari proses looping jika tidak terjadi swap break do-while loop end if swapped := false for each i in length( A ) - 2 to 0 do: if A[ i ] > A[ i + 1 ] then swap( A[ i ], A[ i + 1 ] ) swapped := true end if end for while swapped // jika tidak ada lagi proses swap maka data sudah dalam keadaan terurut end procedure
Universitas Sumatera Utara
2.6.2. Pseudocode 4 way merge sort Pseudocode algortima4 way merge sort sebagai berikut: MergeSort (Array(First,FirstOne,Last,LastOne)) Begin if Array contains only one element then Return Array Else Middle=((Last+LastOne+First+FirstOne)/4) rounded down to nearest integer LeftHalfArray=MergeSort(Array(First..Middle)) RightHalfArray=MergeSort(Array(Middle+1..Last)) ResultArray=Merge(LeftHalfArray,RightHalfArray) Return ResultArray Endif End MergeSort 2.7. Flowchart Untuk menggambarkan sebuah algoritma yang terstruktur dan mudah dipahamioleh orang lain (khususnya programmer yang bertugas mengimplementasikan program), maka dibutuhkan alatbantu yang bebrbentuk diagram alir (flowchart). Flowchart menggambarkan urutan logika dari suatu prosedur pemecahan masalah, sehingga flowchart merupakan langkah-langkah penyelesaian masalah yang dituliskan dalam simbol-simbol tertentu.Tujuan flowchart adalah untuk menggambarkan suatu tahapan penyelesaian masalah secara sederhana, terurai, rapi dan jelas menggunakan simbolsimbol yang standar. Simbol-simbol flowchartyang digunakan untuk menggambarkan algoritma dalam bentuk diagram alir dan kegunaan dari simbol-simbol yang bersangkutan dapat dilihat pada Tabel 2.1. Tabel 2.1. Simbol-Simbol Flowchart Simbol
Nama
Fungsi
Terminal
Menyatakan permulaan atau akhir program..
Input/Output
Menyatakan proses input/output tanpa tergantung jenis peralatannya
Universitas Sumatera Utara
Process
Menyatakan (proses)
suatu
yang
tindakan
dilakukan
oleh
komputer. Decision
Menunjukkan
suatu
kondisi
tertentu yang akan menghasilkan dua kemungkinan jawaban yaitu: ya atau tidak.
Tabel 2.1. Simbol-Simbol Flowchart(Lanjutan) Simbol
Nama
Fungsi
Connector
Menyatakan sambungan dari proses ke proses lainnya dalam halaman yang sama.
Offline Connector
Menyatakan sambungan dari proses ke proses lainnya dalam halaman yang berbeda
Prefined Data
Menyatakan penyimpanan
penyediaan suatu
tempat
pengolahan
untuk memberi inisialisasi/harga awal PredefinedProcess
Menyatakan
permulaan
sub
program/proses menjalankan sub program
2.8. Running Time Running time adalah waktu yang digunakan oleh sebuah algoritma untuk menyelesaikan masalah pada sebuah komputer paralel dihitung mulai dari saat algoritma mulai hingga
Universitas Sumatera Utara
saat algoritma berhenti.Jika prosesor-prosesornya tidak mulai dan selesai pada saat yang bersamaan, maka running time dihitung mulai saat komputasi pada prosesor pertama dimulai hingga pada saat komputasi pada prosesor terakhir selesai.
2.9. Kompleksitas Waktu Kompleksitas Waktu atau T(n) adalah jumlah operasi yang dilakukan untuk melaksanakan algoritma sebagaifungsidari ukuran masukan n (Tjaru, 2009). Oleh karena itu, dalam mengukur kompleksitas waktu dihitunglah banyaknya operasi yangdilakukan oleh algoritma. Idealnya, harusmenghitung semua operasi yang ada dalam suatu algoritma. Namun untuk alasan praktis, cukup menghitungjumlah operasi abstrak yang mendasari suatu algoritma.
Hal–hal yang mempengaruhi kompleksitas waktu (Aulia, 2006): 1. Jumlah masukan data untuk suatu algoritma(n). 2. Waktu yang dibutuhkan untuk menjalankan algoritma tersebut. 3. Ruang memori yang dibutuhkan untuk menjalankan algoritma yang berkaitan dengan strutur data dari program. Kompleksitas waktu dibedakan atas tiga jenis, yakni : 1. Tmax(n) : kompleksitas waktu untuk kasus terburuk (worst case), kebutuhan waktumaksimum. 2. Tmin(n) : kompleksitas waktu untuk kasus terbaik (best case),kebutuhan waktuminimum. 3. Tavg(n): kompleksitas waktu untuk kasus rata-rata (average case), kebutuhanwaktu secara rata-rata.
2.10. Metode Pemodelan UML UML (Unified Modeling Language) merupakan metode pemodelan secara visual sebagai sarana untuk merancang atau membuat software berorientasi objek. Karena UML sebuah bahasa visual untuk pemodelan bahasa berorientasi objek, maka semua elemen dan diagram berbasiskan pada paradigma object oriented sehingga UML merupakan sebuah bahasa standar untuk pengembangan sebuah software yang dapat menyampaikan bagaimana membuat danmembentuk model-model, tetapi tidak
Universitas Sumatera Utara
menyampaikan apa dan kapanmodel yang seharusnya dibuat yang merupakan salah satu proses implementasi pengembangan software. UML terdiri atas pengelompokan diagram-diagram sistem menurut aspek atau sudut pandang tertentu.Diagram yang menggambarkan permasalahan maupun solusi dari permasalahan suatu model. UML mempunyai beberapa jenis diagram yaitu:Use Case Diagram, Class Diagram, Package Diagram, Object Diagram, Sequence Diagram,
Collaboration
Diagram,
StatiChart
Diagram,
Activity
Diagram,
Deployment Diagram, Component Diagram, Composite Structure Diagram, Interaction Overview Diagram, Timing Diagram.Tetapi yang sering digunakan adalah Use Case Diagram, Activity Diagram, Sequence Diagram dan Class Diagram.
2.10.1. Use case diagram Use case diagramadalah model fungsional sebuah system yang menggunakan actor dan use case. Use case adalah layanan (service) atau fungsi-fungsi yang disediakan oleh sistem untuk penggunanya yang menjadi persoalan itu apa yang dilakukanbukan bagaimana melakukannya. Use case diagrammenggambarkan fungsionalitas yang diharapkan dari sebuah sistem. Yang tekankan adalah “apa” yang dibuat sistem, dan bukan “bagaimana” sebuah use case menerangkan sebuah interaksi antar actor dengan system. Use case merupakan sebuah pekerjaan tertentu, misalnya:login ke sistem, meng-create sebuah daftar belanja, dan lain-lain. Seorang sebuah actor adalah sebuah entitas manusia atau mesin yang berinteraksi dengan sistem untuk melakukan pekerjaan-pekerjaan tertentu. Diagram use case dekat kaitannya dengan kejadian-kejadian. Kejadian (scenario) merupakan contoh apa yang terjadi ketika seseorang berinteraksi dengan sistem.Use case diagram mempunyai beberapa bagian penting seperti: Actor, Use Case, Underectional Association, Generalization. Use case diagram mempunyai pengkasifikasian yang ditunukkan pada Tabel 2.2. Tabel 2.2. Pengklasifikasian dalam Use Case Diagram Pengklasifikasi
Kegunaan
Notasi
Universitas Sumatera Utara
Actor
Menggambarkan semua objek di luar sistem
(bukan
hanya
sistem/perangkat berinteraksi
pengguna
lunak)
dengan
sistem
yang yang
dikembangkan. Use Case
Menggambarkan fungsionalitas yang dimiliki system
Relasi menggambarkan hubungan antara actor dan use case.Pembagian relasi-relasi ini dapat dilihat pada Tabel 2.3.
Tabel 2.3. Tabel Relasi-Relasi dalam Use Case Diagram Relasi
Kegunaan
Notasi
Asosiasi
Lintasan komunikasi antara actor
(Association)
dengan use case
Extend
Penambahan perilaku ke suatu use case dasar
Generalisasi
Menggambarkan hubungan antara
Use Case
use case yang bersifat umum dengan use case-use case yang bersifat lebih spesifik
Include
Penambahan perilaku ke suatu use case dasar yang secara eksplisit mendeskripsikan
penambahan
tersebut
2.10.2. Activity diagram
Universitas Sumatera Utara
Activity diagram menggambarkan berbagai alir aktivitas dalam sistem yang sedang dirancang, bagaimana masing-masing alir berawal, decision yang mungkin terjadi, dan bagaimana aktivitas berakhir.Activity diagram sesungguhnya merupakan bentuk khusus dari state machine yang bertujuan memodelkan komputasi-komputasi dan aliran-aliran kerja yang terjadi dalam sistem/perangkat lunak yang sedang dikembangkan. Activity diagrammencakup didalamnya simbol-simbol yang relative mudah digunakan. Simbol-simbol yang sama juga dapat digunakan pada statechart diagram.
Jenis-jenis state diperlihatkan pada Tabel 2.4. Tabel 2.4. Jenis-Jenis State Relasi
Fungsi
Notasi
State
State tanpa struktur apapun di
sederhana
dalamnya
State
State yang dibagi menjadi 2 atau
komposit
lebih substate konkuren.
Initial state
State
mendindikasikan
State With Substance
awal
rangkaian state dalam diagram state Final state
State
mengindikasikan
akhir
rangkaian state dalam diagram state 2.10.3. Sequence diagram Sequence diagram termasuk kedalam kategori diagram behavior, yaitu diagram yang berfungsi untuk menampilkan prilaku software. Sequence diagram menggambarkan bagaimana objek saling berinteraksi melalui message dalam eksekusi operation, untuk satu buah use case.Diagram ini mengilustrasikan bagaimana message dikirim dan
Universitas Sumatera Utara
diterima diantara objek, dan di urutan yang mana.Sequence diagram membantu untuk menggambarkan data yang masuk dan keluar sistem.
Universitas Sumatera Utara
Notasi/simbol sequence diagram dapat dilihat pada Tabel 2.5 Tabel 2.5. Notasi/simbol Sequence Diagram Actor
Seseorang atau sesuatu yang berinteraksi dengan sistem. Berpartisipasi secara berurutan dengan mengirimkan dan/atau menerima pesan. Ditempatkan dibagian atas diagram.
System
Kotak yang menunjukan sebuah sistem sebagai „black box‟ atau secara keseluruhan.
Lifeline
Garis putus vertikal dibawah aktor dan sistem, menunjukkan berjalannya sistem
Activation bar
Garis membentuk kotak panjang dibawah lifelines. Menunjukkan waktu ketika objek aktif di dalam interaksi.
Input message
Garis panah horizontal dari aktor ke sistem yang menunjukkan input. Penulisan diawali dengan huruf kapital. Jika mengandung parameter, ditulis dengan cara yang sama, dan setiap parameter diawali dengan koma.
Output message
Garis panah putus-putus horizontal dari sistem ke aktor yang menunkukkan message yang dikirim dari sistem ke aktor.
Receiver actor
Aktor lain diluar sistem yang menerima message dari sistem juga dapat diikutsertakan.
Frame
Sebuah kotak yang dapat menutup satu atau lebih message untuk membagi sequence. Frame dapat menunjukkan loop atau pilihan lain.
Universitas Sumatera Utara
