bab 2 landasan teori 2.1. algoritma algoritma adalah prosedur

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.


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


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 subkumpulan-

subkumpulan 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.


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


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

Data yang sudah terurut:

8 14 22 31 72 98


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).


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


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 simbol-

simbol 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


Process Menyatakan suatu tindakan

(proses) yang 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 penyediaan tempat

penyimpanan suatu 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


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


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


Actor Menggambarkan semua objek di luar

sistem (bukan hanya pengguna

sistem/perangkat lunak) yang

berinteraksi dengan sistem 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

(Association)

Lintasan komunikasi antara actor

dengan use case

Extend Penambahan perilaku ke suatu use

case dasar

Generalisasi

Use Case

Menggambarkan hubungan antara

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


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

sederhana

State tanpa struktur apapun di

dalamnya

State

komposit

State yang dibagi menjadi 2 atau

lebih substate konkuren.

Initial state State mendindikasikan 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

State With

Substance


diterima diantara objek, dan di urutan yang mana.Sequence diagram membantu untuk

menggambarkan data yang masuk dan keluar sistem.


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.


bab 2 landasan teori 2.1. algoritma algoritma adalah prosedur

Documents