modul struktur data · 2020. 8. 6. · kata pengantar modul praktikum ini dibuat sebagai pedoman...

Disusun oleh :

Suhendra, ST., M.TI.

LP2M Politeknik Manufaktur Astra

JAKARTA

MODUL STRUKTUR DATA

MODUL STRUKTUR DATA

Penulis :

Suhendra ST.,M.TI.

ISBN: 978-623-93597-1-3

Editor :

Radix Rascalia ST., MT.

Penyunting :

Radix Rascalia ST., MT.

Desain Sampul dan Tata Letak :

Hence Ronald Runtuwene

Penerbit :

LP2M Politeknik Manufaktur Astra

Jl. Gaya Motor Raya No.8 Sunter II Jakarta 14330

Telepon: (021) 6519555 Fax: (021) 6519821

Email: [email protected]

Cetakan Pertama, April 2019

Hak Cipta dilindungi undang-undang.

Dilarang keras menerjemahkan, memfotokopi, atau memperbanyak

Sebagian atau seluruh isi buku ini tanpa izin tertulis dari penerbit.

mailto:[email protected]

KATA PENGANTAR

Modul praktikum ini dibuat sebagai pedoman mahasiswa dalam melakukan kegiatan

praktikum struktur data di Politeknik Manufaktur Astra. Modul praktikum ini terdiri dari 12

modul praktikum yang membahas tentang abstract data type, tipe data statik dan dinamik,

beberapa model struktur data linear dan non linear yang dikenal secara umum. Modul praktikum

ini diharapkan dapat membantu mahasiswa/i dalam melaksanakan praktikum dengan lebih baik,

terarah, dan terencana. Pada setiap topik telah ditetapkan tujuan pelaksanaan praktikum dan

semua kegiatan yang harus dilakukan oleh mahasiswa/i serta teori singkat untuk memperdalam

pemahaman mahasiswa/i mengenai materi yang dibahas.

Penyusun menyakini bahwa dalam pembuatan Modul Praktikum stuktur data ini masih

jauh dari sempurna. Oleh karena itu penyusun mengharapkan kritik dan saran yang membangun

guna penyempurnaan modul praktikum ini dimasa yang akan datang.

Akhir kata, penyusun mengucapkan banyak terima kasih kepada semua pihak yang telah

membantu baik secara langsung maupun tidak langsung.

Jakarta, 10 April 2019

Suhendra, ST.,M.TI.

ii

DAFTAR ISI

KATA PENGANTAR ................................................................................................................. i

DAFTAR ISI ............................................................................................................................... ii

MODUL STRUKTUR DATA – PRAKTIKUM 1 ..................................................................... 1

REKURSIF ................................................................................................................................. 1

1. Tujuan ........................................................................................................................... 1

2. Durasi Waktu ................................................................................................................ 1

3. Dasar Teori ................................................................................................................... 1

4. Peralatan : ..................................................................................................................... 4

5. Percobaan ...................................................................................................................... 4

6. Latihan dan Evaluasi .................................................................................................... 8

7. Referensi ....................................................................................................................... 9

MODUL STRUKTUR DATA – PRAKTIKUM 2 ................................................................... 10

ABSTRACT DATA TYPE (ADT) ........................................................................................... 10

1. Tujuan ......................................................................................................................... 10

2. Durasi Waktu .............................................................................................................. 10

3. Dasar Teori ................................................................................................................. 10

4. Peralatan : ................................................................................................................... 11

5. Percobaan .................................................................................................................... 11

6. Latihan dan Evaluasi .................................................................................................. 17

7. Referensi ..................................................................................................................... 17


iii

LINKED LIST .......................................................................................................................... 18

1. Tujuan ......................................................................................................................... 18

2. Durasi Waktu .............................................................................................................. 18

3. Dasar Teori ................................................................................................................. 18

4. Peralatan : ................................................................................................................... 23

5. Percobaan .................................................................................................................... 23


7. Referensi ..................................................................................................................... 30


STACK ..................................................................................................................................... 31

1. Tujuan ......................................................................................................................... 31

2. Durasi Waktu .............................................................................................................. 31

3. Dasar Teori ................................................................................................................. 31

4. Peralatan : ................................................................................................................... 33

5. Percobaan .................................................................................................................... 33


7. Referensi ..................................................................................................................... 41


QUEUE ..................................................................................................................................... 42

1. Tujuan ......................................................................................................................... 42

2. Durasi Waktu .............................................................................................................. 42

3. Dasar Teori ................................................................................................................. 42

4. Peralatan : ................................................................................................................... 43

5. Percobaan .................................................................................................................... 44


iv

7. Referensi ..................................................................................................................... 56


HASH TABLE .......................................................................................................................... 57

1. Tujuan ......................................................................................................................... 57

2. Durasi Waktu .............................................................................................................. 57

3. Dasar Teori ................................................................................................................. 57

4. Peralatan : ................................................................................................................... 60

5. Percobaan .................................................................................................................... 60


7. Referensi ..................................................................................................................... 76


TREE......................................................................................................................................... 77

1. Tujuan ......................................................................................................................... 77

2. Durasi Waktu .............................................................................................................. 77

3. Dasar Teori ................................................................................................................. 77

4. Peralatan : ................................................................................................................... 79

5. Percobaan .................................................................................................................... 80


7. Referensi ..................................................................................................................... 83


BINARY TREE TRAVERSAL ................................................................................................ 84

1. Tujuan ......................................................................................................................... 84

2. Durasi Waktu .............................................................................................................. 84

3. Dasar Teori ................................................................................................................. 84

4. Peralatan : ................................................................................................................... 86

v

5. Percobaan .................................................................................................................... 86


7. Referensi ..................................................................................................................... 90


GRAPH ..................................................................................................................................... 91

1. Tujuan ......................................................................................................................... 91

2. Durasi Waktu .............................................................................................................. 91

3. Dasar Teori ................................................................................................................. 91

4. Peralatan : ................................................................................................................... 96

5. Percobaan .................................................................................................................... 97

6. Latihan dan Evaluasi ................................................................................................ 101

7. Referensi ................................................................................................................... 102

MODUL STRUKTUR DATA – PRAKTIKUM 10 ............................................................... 103

GRAPH TRAVERSAL .......................................................................................................... 103

1. Tujuan ....................................................................................................................... 103

2. Durasi Waktu ............................................................................................................ 103

3. Dasar Teori ............................................................................................................... 103

4. Peralatan : ................................................................................................................. 105

5. Percobaan .................................................................................................................. 105


7. Referensi ................................................................................................................... 109


SORTING ............................................................................................................................... 110

1. Tujuan ....................................................................................................................... 110

2. Durasi Waktu ............................................................................................................ 110

vi

3. Dasar Teori ............................................................................................................... 110

4. Peralatan : ................................................................................................................. 112

5. Percobaan .................................................................................................................. 112


7. Referensi ................................................................................................................... 115


SEARCHING .......................................................................................................................... 116

1. Tujuan ....................................................................................................................... 116

2. Durasi Waktu ............................................................................................................ 116

3. Dasar Teori ............................................................................................................... 116

4. Peralatan : ................................................................................................................. 117

5. Percobaan .................................................................................................................. 117


7. Referensi ................................................................................................................... 118

1

MODUL STRUKTUR DATA – PRAKTIKUM 1

REKURSIF

1. Tujuan

Tujuan Instruksional Umum :

Mampu membuat program perulangan menggunakan teknik rekursif dengan bahasa

C.

Tujuan Instruksional Khusus :

1. Dapat menunjukkan persyaratan dari suatu teknik rekursif.

2. Dapat menentukan base case, recursif case dan algoritma rekursif dari suatu

masalah perulangan.

3. Dapat membuat program perulangan menggunakan teknik rekursif dengan

bahasa C.

2. Durasi Waktu

2 x 4,5 jam

3. Dasar Teori

Rekursi :

• Konsep pengulangan diluar pendekatan iteratif.

• Suatu proses yang memanggil dirinya sendiri, proses dapat berupa fungsi

atau prosedur.

• Setiap pemanggilan fungsi membutuhkan resource memori.

• Base Case adalah solusi dimana proses rekursi akan berhenti.

• Recursif Case adalah kasus dimana solusi di hasilkan dengan cara memanggil

“versi kecil” dari dirinya sendiri.

2

• Recursif Alghoritm, solusi yang diekspresikan melalui Base Case & Recursif

Case.

Contoh:

Fungsi matematik faktorial-n,

n! = n * (n-1) * (n-2)* …* 2 * 1

n! = n * (n-1)!

Dimana:

n > 0

0! = 1

4! = 4 * 3 * 2 * 1 = 24

Fungsi tersebut menunujukkan sifat rekursi berupa pemanggilan terhadap fungsi

faktorial-n berulang kali.

int factorial (int n) {

return n * factorial(n - 1);

}

• Proses Rekursi setidaknya memiliki parameter yang menentukan proses

rekursi lanjut atau berakhir (parameter sentinel).


if (n > 0) {

return n * factorial(n - 1);

} else {

return 1;

}

3

• Proses Rekursi mengarahkan parameter sentinel agar melalui parameter

tersebut rekursi dapat berakhir.


if (n > 0) {

return n * factorial(n - 1); // <-- recursif case

} else {

return 1; // <-- base case

}

Dalam contoh tersebut, parameter diarahkan dengan pengurangan nilai n dengan 1

sehingga proses rekursi dapat berakhir saat n=0.

• Proses Rekursi memiliki level dengan sifat Last In First Out (LIFO)

Output:

4

4. Peralatan :

1. C++ Compiler

2. Dev C++ IDE

5. Percobaan

PERCOBAAN 1: Menentukan Base Case dan Recursif Case

1. Jalankan program berikut, apa hasilnya ?

#include <stdio.h>

#include <stdlib.h>

/* run this program using the console pauser or add your own

getch, system("pause") or input loop */

void rekursi();

int main(int argc, char *argv[]) {

rekursi();

return 0;

}

void rekursi(){

printf("Rekursi\n");

rekursi();

}


5

#include <stdio.h>

#include <stdlib.h>



void rekursi(int val);


rekursi(10);

return 0;

}

void rekursi(int level){

printf("Rekursi: %d\n",val);

rekursi(--level);

}


#include <stdio.h>

#include <stdlib.h>



void rekursi(int level);


rekursi(10);

return 0;

}

void rekursi(int level){

if (level>0) {

printf("Rekursi: %d\n",level);

rekursi(--level);

}

}


#include <stdio.h>

#include <stdlib.h>

6



void rekursi(int val);


rekursi(3);

return 0;

}

void rekursi(int val){

if (val>0) {

printf("Step in recursion -> val : %d\n", val);

rekursi(--val);

printf("Step after recursion -> val : %d\n", val);

}

}

Nama Program Hasil

Program 1

Program 2

Program 3

Program 4

7

Kesimpulan :

PERCOBAAN 2: Menggunakan algoritma rekursif untuk memecahkan

problem deret Fibonacci.

Deret Fibonacci merupakan barisan bilangan sederhana dimulai dari 0 dan 1 dan suku

berikutnya merupakan jumlah dua bilangan sebelumnya. Deret Fibonacci ini

ditemukan oleh Leonardi Pisano atau lebih dikenal dengan sebutan Leonardo

Fibonacci.

Jalankan program berikut, tentukanlah base case, recursif case !

#include <stdio.h>

#include <stdlib.h>



int main()

{

int nilai, i ;

printf ("Jumlah deret bilangan fibonacci ? ");

scanf ("%d", &nilai);

for (i=1; i<= nilai; i++)

{

printf ("%d__", fibo(i));

}

printf ("\n");

return 0;

}

int fibo (int a)

{

if (a==0){ return 0;}

if (a==1) return 1;

else

return fibo(a-2) + fibo(a-1);

8

}

Isilah tabel berikut :

Base Case ?

Recursif Case ?

6. Latihan dan Evaluasi

1. Buatlah program untuk melakukan operasi perkalian bilangan real dengan

metode iterasi & rekursi !

n = 6 x 4

n = 6 + 6 + 6 + 6

2. Carilah angka terbesar dari elemen-elemen yang terdapat pada sebuah array

integer dengan metode rekursi !

3. Buatlah program untuk menampilkan permutasi karakter ‘a’..’c’ dengan

metode rekursi !

Contoh output:

abc

acb

bca

bac

cab

cba

9

7. Referensi

1. Dale, Nell B., et al. 2001. Object Oriented Data Structured Using Java.

Sudbury: Jones and Bartlett Publishers, Inc.

2. Hubbard, John R. 2007. Data Structure With Java. New York: McGraw-Hill

Companies, Inc.

3. Lafore, R. 1999. Sams Teach Yourself Data Structures and Algorithms in 24

Hours. Indianapolis: Sams Publishing.

10


ABSTRACT DATA TYPE (ADT)

1. Tujuan


Mampu membuat dan menggunakan Class Abstract Data Type (ADT) menggunakan

Java


1. Mampu menggunakan Class ADT yang telah ada dari Java Library

2. Mampu membuat Class ADT sendiri (user defined) yang sederhana dengan

perspektif data logika, aplikasi dan implementasi.

3. Mampu menggunakan user defined Class ADT

2. Durasi Waktu

2 x 4,5 jam

3. Dasar Teori

Abstract Data Type (ADT)

Abstract Data Type (ADT) merupakan tipe data dimana properti (domain dan

operasi) terpisah dari implementasinya.

Contoh :

11

Tipe Data Primitif int, kita tahu bahwa tipe data ini memiliki operasi tambah, kurang,

kali dan bagi, namun kita tidak tahu bagaimana proses didalam operasi tersebut

bekerja (implementasi nya).

ADT dalam java diimplementasikan melalui Class.

Struktur Data

Struktur Data merupakan kumpulan item-item data terorganisir yang dianggap

sebagai suatu unit. Item-item data pada struktur data dapat terdiri dari kombinasi tipe

data primitif, komposit terstruktur atau tak terstruktur.

Contoh: List, Queue, Stack, Tree, Graph.

Level Data

Terdiri dari 3 perspektif yaitu:

1. Level abstract (logical), abstract view dari domain data dan operasinya. ADT

dibuat disini.

2. Level aplikasi, memodelkan data yang nyata (real-life) untuk konteks masalah

tertentu. Programmer menggunakan ADT disini untuk menyelesaikan

masalah.

3. Level implementasi, cara memanipulasi data dan pengkodean operasi.

4. Peralatan :

3. Java Development Kit (JDK) Versi 1.8

4. Netbeans 8.0.2 Java IDE

5. Percobaan

PERCOBAAN 1 : Mencetak Tanggal Sekarang dengan menggunakan Class

ADT Date yang terdapat pada Java Library

1. Buatlah Proyek Baru – Java Application - dengan nama CobaDate

12

2. Untuk menggunakan class ADT Date dapat dilakukan dengan cara Import

class ADT Date dari Java Library jav.util. Letakkan sesudah baris: package

cobadate;

import java.util.Date;

3. Modifikasi Method main sehingga tampak seperti berikut:

13

public static void main(String[] args) {

// instansiasi kelas Date

// Application Data Level

Date curDate = new Date();

// cetak tanggal sekarang

// gunakan method getDate(), getMonth() & getYear() dari

ADT date

System.out.println("Tanggal Sekarang : " +

curDate.getDate() + "/" + curDate.getMonth() + "/" +

curDate.getYear());

}

Perhatikan bahwa kita tidak mengetahui bagaimana proses internal yang terjadi

pada operations/method curDate.getDate(), curDate.getMonth() ,

curDate.getYear(). Dari perspektif level data, hal ini termasuk pada Data

Implementation Level.

4. Jalankan program. Contoh output program tampak seperti gambar berikut:

PERCOBAAN 2 : Membuat Class ADTBox

1. Kita akan membuat class ADTBox. Perhatikan Diagram berikut :

14

2. Buatlah Proyek Baru – Java Application - dengan nama CobaBox

3. Buatlah class baru dengan nama ADTBox

15

4. Source dari class ADTBox tampak seperti berikut :

public class ADTBox {

private int top;

private int left;

private int right;

private int bottom;

private byte color;

private boolean rounded;

public void setColor(byte color) {

this.color = color;

}

public void setRounded(boolean rounded) {

this.rounded = rounded;

}

public void setTopLeft(int top, int left) {

this.top = top;

this.left = left;

}

public void setBottomRight(int bottom, int right) {

this.right = right;

this.bottom = bottom;

}

public void show() {

System.out.println("Box");

System.out.println("Top = " + this.top);

System.out.println("Left = " + this.left);

System.out.println("Bottom = " + this.bottom);

System.out.println("Right = " + this.right);

System.out.println("Color = " + this.color);

System.out.println("Rounded = " + this.rounded);

}

}

PERCOBAAN 3 : Menggunakan Class ADT Box

1. Melanjutkan percobaan 2, modifikasi source dari method main dari project

CobaBox sehingga tampak seperti berikut :

public class CobaBox {

/**

* @param args the command line arguments

16

*/


ADTBox box = new ADTBox();

box.setTopLeft(10, 10);

box.setBottomRight(20, 20);

box.setColor((byte) 0);

box.setRounded(true);

box.show();

}

}

2. Jalankan program. Output program akan tampak seperti berikut:

3. Jalankanlah test plan pada tabel berikut, jika menemui kesalahan perbaikilah

kemudian jalankan kembali test plan.

Test Case Expected Result Checked

Input topleft (10,10)

Input bottomRight(20,20)

Input color(0)

Input rounded(true)

Top = 10

Left = 10

Bottom = 20

Right = 20

Color = 0

Rounded = true


Input bottomRight(-20,20)

Error message “Bottom <

Top”

17


Input bottomRight(20,-24)

Error message “Bottom <

Top”


Buatlah ADT PhoneBook, spesifikasikan domain/attribute dan operation yang perlu

ada. Implementasikan dalam Java.

7. Referensi




Companies, Inc.

18


LINKED LIST

1. Tujuan


Mampu membuat Linked List menggunakan bahasa Java.


1. Dapat membuat Singly Linked List berikut operasi-operasinya.

2. Dapat membuat Doubly Linked List berikut operasi-operasinya.

3. Dapat membuat Circular Linked List berikut operasi-operasinya.

2. Durasi Waktu

2 x 4,5 jam

3. Dasar Teori

Struktur Data dilihat dari alokasi memori yang digunakan dibagi menjadi 2 yaitu

dinamik dan statik. Struktur dinamik memungkinkan jumlah elemen data dapat

berubah-ubah (tambah atau kurang) pada saat runtime. Sementara pada struktur statik

elemen data tetap/fixed.

Linked List merupakan jenis struktur data linear yang dinamis. Berikut

karakteristiknya:

- Terdiri atas node yang secara bersama-sama membentuk susunan linear.

19

- Tiap node terhubung dengan node sebelumnya menggunakan referensi dari

node sebelumnya.

- Referensi ke node sebelumnya disebut dengan link.

- Node terdiri atas elemen data dan referensi.

Ada 3 Tipe Linked List yaitu Singly Linked List, Doubly Linked List, Circular

Linked List.

Gambaran Linked List adalah seperti tampak pada gambar berikut:

Operasi Insertion:

21

Deletion:

22

Doubly Linked List:

Circular Linked List:

23

4. Peralatan :



5. Percobaan

PERCOBAAN 1 – MEMBUAT SINGLY LINKED LIST

1. Buatlah Proyek Baru – Java Application - dengan nama CobaLinkedList

2. Buatlah Class Baru pada proyek dengan nama Node

public class Node {

private String data;

private Node nextReference;

public Node(String data) {

this.data = data;

this.nextReference = null;

}

public String getData() {

return data;

}

public void setData(String data) {

24

this.data = data;

}

public Node getNextReference() {

return nextReference;

}

public void setNextReference(Node nextReference) {

this.nextReference = nextReference;

}

}

3. Buatlah Class Baru pada proyek dengan nama SLinkedList, pada kelas ini

terdapat method yang akan menyisipkan Node baru di awal node (Head) dan

diakhir node (Tail).

public class SLinkedList {

private Node head;

private Node tail;

private int size;

public SLinkedList() {

this.head = null;

this.tail = null;

this.size = 0;

}

public boolean isEmpty() {

if ((this.head==null) && (this.tail==null)) {

return true;

}

else {

return false;

}

25

}

public void addFirst(Node node) {

if (!isEmpty()) {

node.setNextReference(head);

head = node;

}

else {

node.setNextReference(null);

tail = node;

head = node;

}

++this.size;

}

public int getSize() {

return size;

}

public void addLast(Node node) {

if (!isEmpty()) {


this.tail.setNextReference(node);

tail = node;

}

else {


tail = node;

head = node;

}

++this.size;

}

26

4. Pada method main di class CobaLinkedList, ketikkan kode berikut:


SLinkedList myLinkedList = new SLinkedList();

Node data1 = new Node("Data1");



myLinkedList.addLast(data1);


myLinkedList.addFirst(data3);

}

5. Jalankan program.

PERCOBAAN 2 – MEMBACA ISI SINGLY LINKED LIST

1. Pada Class SLinkedList, untuk membaca linked list digunakan pointer.

Tambahkan method berikut:

1. public void display() { 2. Node pointer; 3. 4. pointer = head; 5. 6. System.out.println("Size :" + this.size); 7. while (pointer != null) { 8. System.out.println(pointer.getData()); 9. pointer = pointer.getNextReference(); 10. }

11. }

12. }

2. Jalankan program, akan muncul output seperti berikut:

27

PERCOBAAN 3 – MENCARI DATA

1. Untuk mencari data digunakan pointer yang akan bergerak dimulai dari head

lalu ke node-node berikutnya sampai data ditemukan. Tambahkan method

berikut Pada Class Slinked List :

1. public Node search(String data) { 2. Node pointer; 3. 4. if (isEmpty()) return null; 5. 6. pointer = head; 7. 8. while (pointer != null) { 9. if (pointer.getData().contentEquals(data)) return

pointer;

10.

11. pointer = pointer.getNextReference();

12. }

13.

14. return null;

15. }

2. Untuk mencobanya, modifikasi method main pada Class CobaLinkedList.

1. public static void main(String[] args) { 2. SLinkedList myLinkedList = new SLinkedList(); 3. 4. Node data1 = new Node("Data1"); 5. Node data2 = new Node("Data2"); 6. Node data3 = new Node("Data3"); 7. Node hasilCari; 8. 9. myLinkedList.addLast(data1); 10. myLinkedList.addLast(data2);

28

11. myLinkedList.addFirst(data3);

12.

13. hasilCari = myLinkedList.search("Data1");

14.

15. if (hasilCari==null) {

16. System.out.println("Data tidak ditemukan

!");

17. }

18. else {

19. System.out.println("Data ketemu !");

20. }

21. }

3. Jalankan program untuk melihat hasilnya.

4. Bereksperimenlah dengan method pencarian ini.

PERCOBAAN 4 – MENGHAPUS DATA (HEAD)

1. Untuk menghapus data pada head, dilakukan dengan membuat memindahkan

posisi head ke node berikutnya. Node Head yang lama kemudian dihapus atau

dijadikan null. Tambahkan method berikut Pada Class Slinked List :

public void deleteHead() {

Node pointer;

pointer = head;

head = pointer.getNextReference();

pointer = null;

}

2. Untuk mencobanya, modifikasi method main pada Class CobaLinkedList.


SLinkedList myLinkedList = new SLinkedList();




29

Node hasilCari;



myLinkedList.addFirst(data3);

System.out.println("Data sebelum dihapus");

myLinkedList.display();

myLinkedList.deleteHead();

System.out.println("Data sesudah dihapus");

myLinkedList.display();

}

3. Jalankan program untuk melihat hasilnya.

4. Bereksperimenlah dengan method ini.


1. Modifikasi Class SLinkedList pada percobaan, tambahkan method berikut:

- add, berfungsi untuk menambahkan node baik di awal, tengah maupun

akhir.

- delete, fungsi dapat menghapus data baik di awal, tengah maupun

akhir.

2. Buatlah sebuah class baru yang mengimplementasikan konsep doubly linked

list !

3. Buatlah sebuah class baru yang mengimplementasikan konsep circular linked

list !

4. Modifikasilah program PhoneBook agar dapat menggunakan SLinkedList !

30

7. Referensi




Companies, Inc.



31


STACK

1. Tujuan


Mampu membuat Stack menggunakan bahasa Java.


1. Dapat membuat Stack berikut operasi-operasinya menggunakan array dalam

bahasa Java.

2. Dapat membuat Stack berikut operasi-operasinya menggunakan linked list

dalam bahasa Java.

3. Dapat menggunakan Stack dalam dalam sebuah kasus sederhana.

2. Durasi Waktu

2 x 4,5 jam

3. Dasar Teori

Stack merupakan koleksi elemen-elemen data yang memiliki karakteristik berikut :

- Termasuk struktur data Linear

- Elemen paling atasnya diketahui

- Penambahan elemen dilakukan di atas (top)

- Penghapusan elemen dilakukan di atas (top)

- Berlaku aturan Last In First Out (LIFO)

Analogi : Tumpukan/Stack Kotak, Tumpukan Piring, Tumpukan Buku

32

Contoh Pemanfaatan Stack :

- Parsing/Analyzing Arithmetic Expression

- Procedure Calling

- Recursivity

- Programming algorithms for certain complex data structures

- Microprocessor → stack based architecture

- Some Pocket Calculator → stack based

Operasi Pada Stack :

- Push, menambahkan elemen di top stack

- Pop, mengambil elemen dari top stack

- Peek, membaca element di top stack

Implementasi Stack :

- Array Based

- Linked List

Stack dan operasinya tampak seperti gambar berikut:

33

4. Peralatan :



5. Percobaan

PERCOBAAN 1 – STACK DENGAN ARRAY

1. Buatlah Proyek Baru – Java Application - dengan nama CobaStackArray

public class CobaStackArray {

/**


*/


// TODO code application logic here

}

2. Penyajiaan Stack. Buatlah Class Baru pada proyek dengan nama AStack.java

public class AStack {

private static final int MAX_SIZE = 100;

private int size;

private String[] elements;

public AStack() {

size = -1;

elements = new String[MAX_SIZE];

}

public void push(String element) {

34

}

public String pop() {

}

public String peek() {

}

}

3. Push Operation. Dilakukan dengan cara menyimpan nilai pada parameter ke

array index size dan menambah nilai size dengan 1.


size++;

elements[size] = element;

}

Bagaimana jika size > MAX_SIZE ? perbaikilah source tersebut agar

memenuhi kondisi tersebut.

4. Pop Operation. Dilakukan dengan menghapus array elemen yang diindex size

dan mengurangi size dengan 1.


return elements[size--];

}

Bagaimana jika Array stack kosong? perbaikilah source tersebut.

5. Peek Operation. Dilakukan dengan mengambil elemen yang diindex size.


return elements[size];

}

Bagaimana jika Array stack kosong? perbaikilah source tersebut.

35

6. Mencoba Program. Modifikasi method main pada Class CobaStackArray

sehingga terlihat seperti source berikut:


AStack stack = new AStack();

stack.push(“A”);

stack.push(“B”);

stack.push(“C”);

stack.push(“D”);

System.out.println(stack.pop());




}

Hasil Run Program akan tampak seperti berikut:

7. Bereksperimenlah dengan beberapa kondisi.

PERCOBAAN 2 – STACK DENGAN LINKED LIST

1. Buatlah Proyek Baru – Java Application - dengan nama

CobaStackLinkedList

public class CobaStackLinkedList {

/**


*/


36


}

2. Dari Percobaan di PRAKTIKUM sebelumnya (Proyek CobaLinkedList)

copy-kan class Node dan SLinkedList.

3. Paste ke Proyek CobaStackLinkedList

Pilih Refactor Copy.

Catatan:

Refactor akan menyesuaikan perubahan-perubahan seperti nama package ke

proyek tujuan.

37

4. Menambahkan method getNode pada class SLinkedList, method ini bertujuan

untuk mendapatkan node pada index yang ditunjuk parameter. Nantinya akan

bermanfaat untuk mendapakan Node dari element teratas (TOP) Stack.

public Node getNode(int index) {

Node pointer;

int i;

if (isEmpty()) return null;

pointer = head;

i = 0;

while (pointer != null) {

if (i == index) return pointer;

i++;

pointer = pointer.getNextReference();

}

return null;

}

5. Penyajian Stack. Buatlah sebuah class baru dengan nama LStack.

public class LStack {


private int size;

private SLinkedList elements;

public LStack() {

size = -1;

elements = new SLinkedList();

}

38


}


}


}

}

6. Push Operation. Dilakukan dengan cara menambah sebuah node baru diawal

List dan menaikkan size dengan 1.


Node e = new Node(element);

elements.addFirst(e);

size++;

}

Bagaimana jika size > MAX_SIZE ? perbaikilah source tersebut agar memenuhi

kondisi tersebut.

7. Pop Operation. Dilakukan dengan cara mengambil Elemen teratas,

menghapus node diposisi Head dan mengurangi size dengan 1.


String s = peek(); // ambil elemen TOP

elements.deleteHead();

size--;

return s;

}

Bagaimana jika List kosong? perbaikilah source tersebut.

39

8. Peek Operation. Dilakukan dengan mengambil elemen pada node head (index

0).


Node e = elements.getNode(0); // ambil node teratas (TOP

of Stack)

return e.getData();

}

Bagaimana jika stack kosong? perbaikilah source tersebut.

9. Mencoba Program. Modifikasi method main pada Class CobaStackLinkedList



LStack stack = new LStack();

stack.push("A");

stack.push("B");

stack.push("C");

stack.push("D");





}


40


1. Buatlah program untuk menguji apakah string number yang diinputkan

oleh user merupakan palindrom atau bukan. Berikut contoh outputnya:

Petunjuk:

• Gunakan class Scanner untuk mendapat inputan user melalui

keyboard.

Contoh:

Scanner in = new Scanner(System.in);

str = in.nextLine();

• Gunakan fungsi String charAt, untuk membaca character pada

posisi/index tertentu dari String.

Contoh:

// membaca karakter dari String str pada index 0

char ch = str.charAt(0);

• Gunakan fungsi String valueOf, untuk mengubah tipe char menjadi

String.

Contoh:

char ch = str.charAt(0);

String s = String.valueOf(ch);

41

2. Buatlah class baru Stack, beri nama DLStack yang mengimplementasikan

konsep Double Linked List pada struktur Stack !

Petunjuk:

• Operasi push, menambahkan elemen ke tail list.

• Pop, mengambil kemudian menghapus elemen yang ditunjuk tail.

3. Buatlah program yang akan mengkonversi notasi infix yang diinput user

ke notasi postfix ! Berikut contoh outputnya:

7. Referensi




Companies, Inc.



42


QUEUE

1. Tujuan


Mampu membuat Queue menggunakan bahasa Java.


1. Dapat membuat Queue berikut operasi-operasinya menggunakan array dalam

bahasa Java.

2. Dapat membuat Queue berikut operasi-operasinya menggunakan linked list

dalam bahasa Java.

3. Dapat menggunakan Queue dalam dalam sebuah kasus sederhana.

2. Durasi Waktu

2 x 4,5 jam

3. Dasar Teori

Queue merupakan koleksi elemen-elemen data yang memiliki karakteristik berikut :

- Termasuk struktur data Linear

- Penambahan elemen dilakukan didepan (front)

- Penghapusan elemen dilakukan dibelakang (rear)

- Berlaku aturan First In First Out (FIFO)

Analogi : Antrian Pembelian Tiket

43

Gambaran queue dapat terlihat seperti gambar berikut :

Contoh Pemanfaatan Queue :

- Printer queue

- Keyboard keystroke queue

- Time sharing computer system (process / computer application queue)

Parsing/Analyzing Arithmetic Expression

Operasi Pada Queue :

- Enqueue, menambahkan elemen di dibelakang queue

- Dequeue, mengambil elemen dari depan queue

- Front, membaca element di depan queue

Implementasi Queue :

- Array Based

- Linked List

4. Peralatan :



44

5. Percobaan

PERCOBAAN 1 – QUEUE DENGAN ARRAY

1. Buatlah Proyek Baru – Java Application - dengan nama CobaQueueArray

public class CobaQueueArray {

/**


*/



}

}

2. Penyajiaan Queue. Buatlah Class Baru pada proyek dengan nama

AQueue.java

public class AQueue {


private String[] elements;

private int size;

private int front;

private int rear;

public AQueue() {

elements = new String[MAX_SIZE];

size = 0;

front = -1;

rear = front;

}

public void enqueue(String newElement) {

}

45

public String dequeue() {

}


}


}

public boolean isFull() {

}

}

3. isEmpty Operation. Fungsi ini akan melakukan pengecekan apakah Queue

kosong atau tidak. Pengecekan dilakukan dengan cara melihat isi variable

size. Lengkapilah source codenya.


}

4. isFull Operation. Fungsi ini melakukan pengecekan apakah Queue full atau

tidak. Dilakukan dengan cara membandingkan variable MAX_SIZE.

Lengkapilah source codenya.

public boolean isFull() {

}

46

5. enqueue Operation. Fungsi ini akan melakukan penambahan sebuah element

data pada queue selagi masih cukup. Element baru ditempatkan pada posisi

rear, kemudian menambahkan rear dengan 1.


if (isFull()) {

System.out.println("Cannot enqueue " + newElement +

", Queue are full");

return;

}

elements[rear++] = newElement;

size++;

}

6. dequeue Operation. Fungsi ini akan menghapus element pada queue yang

ditunjuk front. Proses penghapusan dilakukan dengan cara menggeser elemen

element[1]..element[rear] ke elemen[0]..elemen[rear-1], ingat bahwa

element[0] adalah front. Kemudian decrement rear dan size;


if (isEmpty()) {

System.out.println("Cannot dequeue, Queue are

empty");

return null;

}

String deletedElement = elements[front];

// move the elements

for (int i=front; i<rear; i++) elements[i]=elements[i+1];

// erase last / rear elements, then decrement rear

elements[rear--] = null;

47

size--;

return deletedElement;

}

7. peek Operation. Fungsi ini akan mengambil data pada elemen queue

terdepan/front. Element terdepan adalah element[0].


if (isEmpty()) {

System.out.println("Cannot peek, Queue are empty");

return null;

}

return elements[front];

}

8. Mencoba Program. Modifikasi method main pada Class CobaQueueArray



AQueue queue = new AQueue();

queue.enqueue("A");

queue.enqueue("B");

queue.enqueue("C");

queue.enqueue("D");

queue.enqueue("E");

queue.dequeue();

queue.peek();

queue.dequeue();

queue.peek();

queue.dequeue();

queue.peek();

48

queue.dequeue();

queue.peek();

queue.enqueue("G");

queue.peek();

queue.dequeue();

queue.peek();

queue.dequeue();

queue.peek();

}

9. Hasil Run Program akan tampak seperti berikut:

10. Bereksperimenlah dengan beberapa kondisi.

49

PERCOBAAN 2 – QUEUE DENGAN LINKED LIST

1. Buatlah Proyek Baru – Java Application - dengan nama

CobaQueueLinkedList

public class CobaQueueLinkedList {

/**


*/



}

2. Dari Percobaan di PRAKTIKUM sebelumnya (Proyek CobaLinkedList)

copy-kan class Node dan SLinkedList.

3. Paste ke Proyek CobaStackLinkedList

50

Pilih Refactor Copy.

Catatan:

Refactor akan menyesuaikan perubahan-perubahan seperti nama package ke

proyek tujuan.

4. Penyajian Queue. Buatlah sebuah class baru dengan nama LQueue.

public class LQueue {

private SLinkedList elements;

private int size;

public LQueue() {

elements = new SLinkedList();

size = 0;

}


return size == 0;

}

public void enqueue(String element) {

}


}

51


}

}

5. enqueue Operation. Fungsi ini akan melakukan penambahan sebuah element

data pada queue. Element baru ditempatkan pada posisi rear atau pada node

tail dari list.


System.out.println("enqueue " + newElement);

Node newNode = new Node(newElement);

elements.addLast(newNode);

size++;

}

6. dequeue Operation. Fungsi ini akan menghapus element pada queue yang

ditunjuk front dengan cara menghapus node head.


if (size==0) {

System.out.println("Cannot dequeue, Queue are

Empty");

return null;

}

String frontElement = elements.getNode(0).getData(); //

get front node;

System.out.println("dequeue " + frontElement);

elements.deleteHead(); // delete front node

size--;

52

return frontElement;

}

7. peek Operation. Fungsi ini akan mengambil data pada elemen queue

terdepan/front. Element terdepan adalah node head pada list atau Node(0).


String frontElement = elements.getNode(0).getData(); //

get front node;

return frontElement;

}

8. Mencoba Program. Modifikasi method main pada Class

CobaQueueLinkedList sehingga terlihat seperti source berikut:


LQueue queue = new LQueue();

queue.enqueue("A");

queue.enqueue("B");

queue.enqueue("C");

queue.enqueue("D");

queue.enqueue("E");

queue.dequeue();

queue.peek();

queue.dequeue();

queue.peek();

queue.dequeue();

queue.peek();

queue.dequeue();

queue.peek();

53

queue.enqueue("G");

queue.peek();

queue.dequeue();

queue.peek();

queue.dequeue();

queue.peek();

}



1. Modifikasilah program pada Percobaan 1 – Queue menggunakan Array, agar

memenuhi kaidah Circular Queue.

Petunjuk:

54

Gunakan tools debugging (Breakpoint, Watch, Step Into, Step Over, dll) pada

IDE yang anda digunakan untuk mempermudah pelacakan kesalahan program.

2. Demonstrasikan melalui program kasus Round Robin Scheduler, Lama

Pelayanan dapat dibuat random dengan waktu tunggu.

Petunjuk:

• Untuk membangkitkan bilangan acak dapat menggunakan class

Random

Contoh:

Untuk mencetak bilangan acak dengan range 0..9

Random random = new Random();

for (int i=1; i<=10; i++) {

System.out.println(random.nextInt(10));

}

• Untuk waktu tunggu (delay) dapat menggunakan fungsi sleep dari

class Thread.

Contoh:

Untuk men-delay proses selama 3000ms.

System.out.println("Sleep for 3000ms");

try {

Thread.sleep(3000);

} catch (InterruptedException ex) {

Logger.getLogger(ContohThreadSleep.class.getName()).log(

Level.SEVERE, null, ex);

}

System.out.println("Wake again");

55

3. Demonstrasikan melalui program sebuah kasus antrian pada Customer Service

(CS) Bank XYZ, dimana terdapat 3 meja CS & 1 antrian utama. 1 CS hanya

dapat melayani 1 Customer dalam 1 waktu. Sebagai contoh, Antrian 1

(Customer 1) akan dilayani oleh CS1, kemudian Antrian 2 dilayani oleh CS2,

antrian 3 oleh CS3, antrian 4 oleh CS1 kembali jika Customer pada CS1 telah

selesai dilayani jika tidak maka diberikan ke CS2 dan seterusnya. Lama

pelayanan oleh CS random.

Berikut ilustrasinya.

CS1 CS2 CS3

ANTRIAN

Antrian

Masuk Antrian

Keluar

Waktu CS melayani Customer Random

56

7. Referensi




Companies, Inc.



57


HASH TABLE

1. Tujuan


Mampu menggunakan Hash dengan bahasa Java.


1. Dapat menjelaskan konsep Hashing, Fungsi Hash, Hash Table dan Collision.

2. Dapat menggunakan teknik penanggulangan Collision baik linear probing,

quadratic probing, dan separate chaining menggunakan bahasa Java.

3. Dapat menggunakan Hash dalam dalam sebuah kasus sederhana.

2. Durasi Waktu

2 x 4,5 jam

3. Dasar Teori

Hashing merupakan teknik yang digunakan untuk menyusun dan mengakses elemen

data dalam List dengan waktu yang relatif konstan melalui manipulasi key untuk

mengidentifikasi lokasi dalam List.

Hash function merupakan fungsi yang digunakan untuk memanipulasi key dari

elemen data dalam List untuk mengidentifikasi lokasi aslinya di list. Fungsi ini akan

memetakan list data yang ukurannya berubah-ubah ke ukuran tetap. Nilai kembalian

dari fungsi hash disebut dengan Hash Values.

58

Hash table merupakan istilah untuk menjelaskan struktur data yang digunakan untuk

menyimpan dan mengambil elemen data menggunakan hashing.

Penanggulangan Collision

Open Addressing → sebagai ganti index yang telah ditentukan oleh fungsi hash, cari

cell yang kosong dalam array dengan cara yang sistematis kemudian masukkan item

baru disana.

Yang termasuk pada Open Adressing method adalah Linear Probing, Clustering dan

Quadratic Probing.

Linear Probing → menanggulangi collision dengan cara secara sequensial mencari

posisi yang kosong pada hash table dimulai dari lokasi yang didapatkan oleh fungsi

hash.

59

Quadratic Probing → menanggulangi collision dengan rehashing formula

(HashValue + I^2 ) % array-size, dimana I adalah jumlah rehash function yang telah

dipakai.

Separate Chaining → untuk elemen yang memiliki lokasi hash yang sama maka buat

array yang terdiri dari linked list.

60

4. Peralatan :



5. Percobaan

PERCOBAAN 1 – HASH TABLE SEDERHANA

1. Buatlah Proyek Baru – Java Application - dengan nama CobaSimpleHash

public class CobaSimpleHash {

/**


*/



}

}

2. Penyajian Elemen Data. Buatlah Class Baru pada proyek dengan nama

Employee.java, class ini akan berisi Elemen data karyawan.

61

public class Employee {

private int id;

private String name;

private String dept;

public Employee(int id, String name, String dept) {

this.id = id;

this.name = name;

this.dept = dept;

}

public int getId() {

return id;

}

public void setId(int id) {

this.id = id;

}

public String getName() {

return name;

}

public void setName(String name) {

this.name = name;

}

public String getDept() {

return dept;

}

public void setDept(String dept) {

this.dept = dept;

}

62

}

3. Penyajiaan Hash Table. Buatlah Class Baru pada proyek dengan nama

HashTable.java. Class ini memiliki 2 buah constructor. Constructor pertama

akan menginisialiasi ukuran HashTable dari parameter hashTableSize,

sementara constructor kedua akan meninisialisasi ukuran HashTable dari

atribut defaultHashTableSize.

public class HashTable {

private static final int defaultHashTableSize = 10;

private Employee employee[];

private int hashTableSize;

private int size;

public HashTable(int hashTableSize) {

this.hashTableSize = hashTableSize;

employee = new Employee[hashTableSize];

}

public HashTable() {

this.hashTableSize = defaultHashTableSize;

employee = new Employee[defaultHashTableSize];

}

}

4. hash Function. Fungsi ini merupakan fungsi hash, yaitu sebuah fungsi yang

akan menghitung lokasi pada Hash Table berdasarkan Key yang ditunjuk oleh

parameter. Untuk percobaan ini hash function mengikuti aturan berikut:

hashValue = Key % HashTableSize.

// hash function

63

private int hash(int key) {

return (key % hashTableSize);

}

5. insert Operation. Fungsi ini akan menambahkan elemen data baru pada lokasi

yang ditunjuk oleh fungsi hash.

public void insert(Employee newEmployee, int key) {

int hashVal = hash(key); // get hash value / hash

Location

System.out.format("inserting Employee %d ...",

newEmployee.getId());

if (employee[hashVal] == null) {

employee[hashVal] = newEmployee;

size++;

System.out.println("OK");

} else {

System.out.format("Collision with %d.New Employee not

inserted !\n", employee[hashVal].getId());

}

}

6. remove Operation. Fungsi ini akan menghapus elemen data pada lokasi yang

ditunjuk oleh parameter Key.

public void remove(int key) {


Location

System.out.format("removing Employee %d...",

employee[hashVal].getId());

employee[hashVal] = null;

size--;


}

64

7. getEmployee Operation. Fungsi ini akan mengambil elemen data Karyawan

dari Hash Table yang ditunjuk Key.

public Employee getEmployee(int key) {


Location

if (employee[hashVal]==null) {

System.out.format("Empty. No Employee with Key

%d.\n",key);

}

return employee[hashVal];

}

8. getLoadFactor Operation. Fungsi ini akan mengambil Load Factor dari Hash

Table. Load Factor merupakan nilai perbandingan jumlan data dengan ukuran

Hash Table.

public float getLoadFactor() {

return (float) size / hashTableSize;

}

Note: Tahukah anda mengapa nilai kembalian fungsi ditambahkan keyword

(float) ?

9. Mencoba Program – Menambah beberapa Elemen Data. Modifikasi method

main pada Class CobaSimpleHash sehingga terlihat seperti source berikut:


Employee emp1000 = new Employee(1000, "Yakub Liman",

"BPUSDM");

Employee emp1001 = new Employee(1001, "Tonny Pongoh",

"BAAK");

Employee emp2001 = new Employee(2001, "Thomas H",

"General Affair (GA)");

Employee emp2006 = new Employee(2006, "Bela Aryani",


65

Employee emp5006 = new Employee(5006, "Yosep S", "MIS");

Employee emp7003 = new Employee(7003, "Alex", "BAAK");

Employee emp8004 = new Employee(8004, "Atet K", "UPT");

Employee emp9006 = new Employee(9006, "Ellen",

"FINANCE");

Employee emp9009 = new Employee(9009, "Hari DN", "KHA");

// insert Employee into HashTable data structure

HashTable employeeData = new HashTable(10);

employeeData.insert(emp1000, emp1000.getId());









System.out.format("Load Factor: %.2f\n",

employeeData.getLoadFactor());

}


66

10. Mencoba Program – Menghapus data. Modifikasi method main pada Class

CobaSimpleHash sehingga terlihat seperti source berikut:



"BPUSDM");


"BAAK");








Employee emp9006 = new Employee(9006, "Ellen",

"FINANCE");

Employee emp9009 = new Employee(9009, "Hari DN", "KHA");














employeeData.remove(2001);

67

employeeData.remove(2001);



}

Jalankanlah program tersebut. Apa yang terjadi ? Sempurnakanlah source-

codenya agar output tampak seperti gambar berikut:

11. Bereksperimenlah dengan fungsi getEmployee dan beberapa kondisi lain.

68

PERCOBAAN 2 – PENANGANAN COLLISION DENGAN LINEAR PROBING

1. Kopi-lah proyek pada percobaan 1 – CobaSimpleHash dengan nama proyek

CobaHashWithLinearProbing.

2. Modifikasi operation insert pada class HashTable seperti tampak pada source

berikut :

public void insert(Employee newEmployee, int key) {

int hashVal = hash(key); // get first hash value / hash

Location

System.out.format("inserting Employee %d ...",

newEmployee.getId());

// search empty hash location - linear probing

while (employee[hashVal] != null) {

69

hashVal++; // increment until empty element from has

table found

}

employee[hashVal] = newEmployee;

size++;


}


main pada Class CobaHashWithLinearProbing sehingga terlihat seperti source

berikut:



"BPUSDM");


"BAAK");















}

70


Kesimpulan apa yang anda dapat ?


main pada Class CobaHashWithLinearProbing sehingga terlihat seperti source

berikut:



"BPUSDM");


"BAAK");













71







}

Apa yang terjadi ?

Perbaikilah source class HashTable sehingga hasil run program akan tampak

seperti gambar berikut:

5. Modifikasi operation remove pada class HashTable seperti tampak pada

source berikut :

public void remove(int key) {

int hashVal = hash(key); // get first hash value / hash

Location

System.out.format("removing Employee with key %d ...",

key);

// search hash location - linear probing

while (employee[hashVal].getId() != key) {

72

hashVal++;

}

employee[hashVal] = null;

size--;


}

6. Mencoba Program – Menghapus Elemen Data. Modifikasi method main pada

Class CobaHashWithLinearProbing sehingga terlihat seperti source berikut:



"BPUSDM");


"BAAK");



















73

// remove Employee with key 3007 from Hash Table;

employeeData.remove(emp3007.getId());



}

7. Jalankan program, output akan tampak seperti gambar berikut:

8. Mencoba Program – Menghapus Elemen Data. Modifikasi method main pada

Class CobaHashWithLinearProbing sehingga terlihat seperti source berikut:



"BPUSDM");


"BAAK");








74












// remove Employee with key 8009 from Hash Table;

employeeData.remove(emp8009.getId());



}

Apa yang terjadi ?

Perbaikilah source class HashTable sehingga hasil run program akan tampak

seperti gambar berikut:

9. Bereksperimenlah dengan fungsi getEmployee dan beberapa kondisi lain.

75

PERCOBAAN 3 – PENANGANAN COLLISION DENGAN QUADRATIC

PROBING

1. Kopi-lah proyek pada percobaan 2 – CobaHashWithLinearProbing dengan

nama proyek CobaHashWithQuadraticProbing.

2. Modifikasi operation insert & remove pada class HashTable sehingga apabila

diuji akan tampak seperti pada tabel berikut :

Test Case Operation Expected Result

insert Employee, key: 1000







insert Stored in Hash Location: 0

Stored in Hash Location: 1






remove Employee, key: 8009 remove Employee remove at Hash

Location :2,

Hash Location:2 → null

Ingatlah bahwa, jika hash location tidak empty maka:

hash Value = hash Value + I2

dengan

I merupakan jumlah rehash yang dilakukan, dimulai dengan 0.

Contoh Output program:

76


1. Implementasikan metode Separate Chaining untuk penanganan Collision

pada proses Hashing !

2. Buatlah perbandingan waktu yang digunakan untuk insertion data integer

random sebanyak 1000 dengan ukuran Hash Table 100 menggunakan metode

penanganan Collision dengan Linear Probing, Quadratic Probing dan Separate

Chaining !

7. Referensi




Companies, Inc.



77


TREE

1. Tujuan


Mampu membuat program menggunakan Tree dengan bahasa Java.


1. Dapat menjelaskan terminologi yang ada pada Tree.

2. Dapat memberikan contoh jenis-jenis Tree.

3. Dapat membuat class Tree menggunakan bahasa Java.

4. Dapat menggunakan class Tree.

2. Durasi Waktu

2 x 4,5 jam

3. Dasar Teori

Tree/pohon merupakan struktur data non linear yang digunakan untuk

merepresentasikan hubungan data yang bersifat hierarkis antara elemen-elemennya.

Pada tree salah satu elemennya disebut dengan root (akar) dan sisa elemen lain

disebut simpul (node/vertex) yang terpecah menjadi sejumlah himpunan yang tidak

saling berhubungan satu sama lain, yang disebut subtree/cabang”. Perhatikan gambar

Tree T berikut :

78

A

B C D

G HFE

JI

Level 1

Level 2

Level 3

Level 4

Tree T

Istilah-istilah pada Tree:

- Simpul adalah elemen tree yang berisi informasi / data dan penunjuk

pencabangan.

- Tingkat/level suatu simpul ditentukan dari akar (root), sebagai level 1. Apabila

simpul dinyatakan sebagai tingkat N, maka simpul-simpul yang merupakan

anaknya berada pada tingkat N+1.

- Derajat/degree menyatakan banyaknya anak/turunan di simpul tersebut.

Contoh : Simpul A memiliki derajat 3 (B,C dan D), simpul yang memiliki derajat

0 (nol) disebut leaf (daun) seperti : E, F, G, I, J

- Tinggi (height) atau kedalaman (depth) suatu tree adalah tingkat maksimum dari

level dalam tree tersebut dikurangi 1.

Contoh dalam tree di atas, mempunyai depth 3.

- Ancestor suatu simpul adalah semua simpul yang terletak dalam satu jalur

dengan simpul tersebut, dari akar sampai simpul yang ditinjaunya.

Contoh Ancestor J adalah A, D dan H

- Predecessor adalah simpul yang berada di atas simpul yang ditinjau.

79

Contoh : Predecessor I adalah H.

- Successor adalah simpul yang berada di bawah simpul yang ditinjau.

Contoh : Successor D adalah H.

- Descendant adalah seluruh simpul yang terletak sesudah simpul tertentu dan

terletak pada jalur yang sama.

Contoh : Descendant A adalah B,C dan D. Descendant C adalah F dan G.

- Sibling adalah simpul-simpul yang memiliki parent yang sama dengan simpul

yang ditinjau.

Contoh : Sibling F adalah G

- Parent adalah simpul yang berada satu level di atas simpul yang ditinjau.

Contoh : Parent I adalah H

- Lintasan (path) adalah urutan akses untuk mendapatkan Node yang ditunjuk yang

dimulai dari Akar. Path J adalah A-D-H-J.

Pohon Biner

Ciri : Maksimum child adalah 2 (Left Child dan Right Child).

Complete Binary Tree :

Bila semua node kecuali Leaf memiliki 0 atau 2 child.

Skewed Binary Tree (Miring) :

Bila semua node, kecuali Leaf memiliki hanya 1 child

Full Binary Tree :

Bila semua node kecuali Leaf memiliki 2 Child dan semua subtree harus memiliki

path yang sama

4. Peralatan :


80


5. Percobaan

PERCOBAAN 1: Membuat Class Tree

1. Buatlah Proyek Baru – Java Application - dengan nama CobaBinaryTree

2. Buatlah class baru dengan nama node.java, source code tampak seperti

berikut:

public class Node {

private String data;

private Node LeftChild;

private Node RightChild;

private Node parent;

public String getData() {

return data;

}

public void setData(String data) {

this.data = data;

}

public Node getLeftChild() {

return LeftChild;

}

public void setLeftChild(Node LeftChild) {

this.LeftChild = LeftChild;

}

public Node getRightChild() {

return RightChild;

}

public void setRightChild(Node RightChild) {

this.RightChild = RightChild;

}

public Node (String data){

this.data = data;

LeftChild = null;

RightChild = null;

}

81

public boolean isGreater(Node compare){

return this.data.compareTo(compare.getData()) > 0;

}

}

3. Buatlah class baru dengan nama BinaryTree.java, dengan source tampak

seperti berikut:

public class Tree {

private Node root;

public Tree(){

root = null;

}

public Tree(Node root){

this.root = root;

}

public Tree(String data){

this.root = new Node(data);

}

public void insert(String data){

insert(new Node(data));

}

public void insert(Node child){

insert(root, child);

}

public void insert(Node parent, Node child){

if(root == null) {

root = child;

System.out.println("Add " + child.getData() + " as

Root");

}

else{

if(child.isGreater(parent)){

if(parent.getRightChild() == null) {

parent.setRightChild(child);

System.out.println("Add " + child.getData() +

" RightChild " + parent.getData());

}

else insert(parent.getRightChild(), child);

}

else {

82

if(parent.getLeftChild() == null) {

parent.setLeftChild(child);

System.out.println("Add " + child.getData() +

" LeftChild " + parent.getData());

}

else insert(parent.getLeftChild(), child);

}

}

}

}

4. Mencoba Program. Modifikasi method main pada Class CobaBinaryTree



Tree pohon = new Tree();

// String data = "HAKCBDJL";

Scanner input = new Scanner(System.in);

System.out.print("String : ");

String data = input.nextLine();

for(int i=0; i<data.length(); i++)

pohon.insert(String.valueOf(data.charAt(i)));

}

Debuglah program tersebut, perhatikanlah isi dari object Pohon.

Input string: HAKCBDJL

Iterasi Isi Object Pohon

Iterasi 1

Iterasi 2

Iterasi 3

Iterasi 4

Iterasi 5

Iterasi 6

83

Iterasi 7

Iterasi 8

Gambarkan bentuk pohonnya !


Modifikasilah class BinaryTree, tambahkan operasi untuk Finding Node.

7. Referensi




Companies, Inc.



84


BINARY TREE TRAVERSAL

1. Tujuan


Mampu mengimplementasikan Binary Tree untuk kasus sederhana.


1. Dapat menjelaskan konsep Binary Tree Traversal inorder, preorder dan post

order.

2. Dapat menyusun program traversal Binary Tree inOrder.

3. Dapat menyusun program traversal Binary Tree postOrder.

4. Dapat menyusun program traversal Binary Tree preOrder.

5. Dapat membuat program sederhana yang memanfaatkan Binary Tree

Traversal.

2. Durasi Waktu

2 x 4,5 jam

3. Dasar Teori

Penelusuran Binary Tree (Traversing Binary Tree)

Ada tiga cara yang standar yaitu :

- Preorder (Node – Left – Right [NLR])

1. Proses root

85

2. Telusuri subtree kiri (Left) secara preorder

3. Telusuri subtree kanan (Right) secara preorder

- Inorder (Left – Node – Right [LNR])

1. Telusuri subtree kiri (Left) secara inorder

2. Proses root

3. Telusuri subtree kanan (Right) secara inorder

- Postorder (Left – Right – Node [LNR])

1. Telusuri subtree kiri (Left) secara postorder

2. Telusuri subtree kanan (Right) secara postorder

3. Proses root

Perhatikan Tree T Berikut:

A

B c

ED

GF

Level 1

Level 2

Level 3

Level 4

Tree T

Jika dilakukan traversal:

- Preorder, maka didapat ABDCEFG

- Inorder, maka didapat BDAFGEC

- Post Order, maka didapat DBFGECA

86

4. Peralatan :



5. Percobaan

PERCOBAAN 1 : Membuat Program Traversal Preorder

1. Modifikasilah class BinaryTree.java pada praktikum sebelumnya dengan

menambahkan method/operasi preorder() didalamnya. Source source tampak

seperti berikut:

public void preOrder(){

preOrder(root);

}

private void preOrder(Node tree){

System.out.print(tree.getData());

if(tree.getLeftChild() != null)

preOrder(tree.getLeftChild());

if(tree.getRightChild() != null)

preOrder(tree.getRightChild());

}











System.out.print("\nPreOrder : ");

pohon.preOrder();

}

87

3. Jalankan program. Contoh output tampak seperti gambar berikut :

Debuglah program tersebut, perhatikanlah isi dari object Pohon.

Input string: HAKCBDJL

Iterasi Isi Object Pohon

Iterasi 1

Iterasi 2

Iterasi 3

Iterasi 4

Iterasi 5

Iterasi 6

Iterasi 7

Iterasi 8

Gambarkan bentuk pohonnya !

88

PERCOBAAN 2 : Membuat Program Traversal Inorder


source tampak seperti berikut:

public void inOrder(){

inOrder(root);

}

private void inOrder(Node tree){


inOrder(tree.getLeftChild());



inOrder(tree.getRightChild());

}











System.out.print("\nInOrder : "); pohon.inOrder();

}


89

PERCOBAAN 3 : Membuat Program Traversal Postorder


source tampak seperti berikut:

public void postOrder(){

postOrder(root);

}

private void postOrder(Node tree){


postOrder(tree.getLeftChild());


postOrder(tree.getRightChild());


}











System.out.print("\nPostOrder : "); pohon.postOrder();

}

90



1. Buatlah program kalkulator sederhana yang mengimplementasikan konsep

postorder traversal.

7. Referensi




Companies, Inc.



91


GRAPH

1. Tujuan


Mampu mengimplementasikan Graph untuk kasus sederhana.


1. Dapat menjelaskan konsep Graph

2. Dapat menyajikan Graph dengan menggunakan matrix incident

3. Dapat menyajikan Graph dengan menggunakan matrix adjacent

2. Durasi Waktu

2 x 4,5 jam

3. Dasar Teori

Graph adalah kumpulan dari simpul dan busur yang secara matematis dinyatakan

sebagai :

G = (V, E)

Dimana

G = Graph

V = Simpul atau Vertex, atau Node, atau Titik

E = Busur atau Edge, atau arc

Contoh Graph :

92

A

B c

D

v1

v3

e1

e3e4

Graph G

Vertex V yaitu v1,v2,v3,v4

Edge E yaitu e1, e2, e3, e4

Dilihat dari busurnya, Graph terbagi menjadi 2 yaitu directed graph dan undirected

graph. Pada directed graph busurnya memiliki arah dan sebaliknya pada undirected

graph busurnya tidak memiliki arah.

Gambar Graph G sebelumnya merupakan contoh undirected graph.

Contoh Directed Graph :

A

B c

D

v1

e2e1

e3e4

Pada directed graph, urutan simpul memiliki arti.

93

Graph Berbobot (weighted graph)

- Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah

simpul, maka busur tersebut dinyatakan memiliki bobot.

- Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik,

jumlah rata-rata kendaraan perhari yang melalui sebuah jalan, waktu yang

dibutuhkan untuk pengerjaan suatu aktifitas, dll.

Contoh:

A

B c

D

v1

v3

58

29

7

Terminologi Graph :

- Incident. Jika e merupakan busur dengan simpul-simpulnya adalah x dan y

yang ditulis e=(x,y), maka x dan y disebut “terletak” pada e, dan e disebut

incident dengan x dan y.

- Degree sebuah simpul adalah jumlah busur yang incident dengan simpul

tersebut.

- Indegree sebuah simpul pada graph berarah adalah jumlah busur yang

kepalanya incident dengan simpul tersebut, atau jumlah busur yang “masuk”

atau menuju simpul tersebut.

94

- Outdegree sebuah simpul pada graph berarah adalah jumlah busur yang

ekornya incident dengan simpul tersebut, atau jumlah busur yang “keluar”

atau berasal dari simpul tersebut.

- Adjacent

Pada graph tidah berarah, 2 buah simpul disebut adjacent bila ada busur yang

menghubungkan kedua simpul tersebut.

Pada graph berarah, simpul x disebut adjacent dengan simpul y bila ada busur

dari x ke y.

- Successor dan Predecessor

Pada graph berarah, bila simpul v adjacent dengan simpul w, maka simpul v

adalah successor simpul w, dan simpul w adalah predecessor dari simpul v.

- Path

Sebuah path adalah serangkaian simpul-simpul yang berbeda, yang adjacent

secara berturut-turut dari simpul satu ke simpul berikutnya.

Representasi Graph dengan Matrix

Adjacency Matrix Undirected Graph

Contoh Graph:

A

B c

D

Matrix Adjacency:

Nyatakan 1 jika berhubungan 0 jika tidak

95

A B C D

A 0 1 1 0

B 1 0 0 1

C 1 0 0 1

D 0 1 1 0

Adjacency Matrix Directed Graph

Contoh Graph:

A

B c

D

Dari\Ke A B C D

A 0 1 1 0

B 0 0 0 1

C 0 0 0 1

D 0 0 0 0

→ Ke …

96

Untuk Graph berbobot jika ada hubungan maka angka 1 dapat diganti dengan

bobotnya.

Incidence Matrix Undirected Graph

Contoh Graph:

A

B c

D

e2e1

e3e4

Matrix Incidence:

Nyatakan 1 jika berhubungan 0 jika tidak

e1 e2 e3 e4

A 1 1 0 0

B 1 0 0 1

C 0 1 1 0

D 0 0 1 1

4. Peralatan :



97

5. Percobaan

PERCOBAAN 1 : Penyajian Graph

1. Buatlah Proyek Baru – Java Application - dengan nama CobaGraph

2. Buatlah class baru dengan nama Vertex.java, source code tampak seperti

berikut:

public class Vertex {

private String label;

private boolean wasVisited;

public Vertex(String label) {

this.label = label;

this.wasVisited = false;

}

public String getLabel() {

return label;

}

public void setLabel(String label) {

this.label = label;

}

public boolean isWasVisited() {

return wasVisited;

}

public void setWasVisited(boolean wasVisited) {

this.wasVisited = wasVisited;

}

}

3. Buatlah class baru dengan nama Edge.java, source code tampak seperti

berikut:

public class Edge {

private String label;

private Vertex fromVertex;

private Vertex toVertex;

private Double weight;

public Edge(String label, Vertex fromVertex, Vertex toVertex)

{

this.label = label;

this.fromVertex = fromVertex;

98

this.toVertex = toVertex;

this.weight = 0.0;

}

public Edge(String label, Vertex fromVertex, Vertex toVertex,

Double weight) {

this.label = label;



this.weight = weight;

}

public Double getWeight() {

return weight;

}

public String getLabel() {

return label;

}

public void setLabel(String label) {

this.label = label;

}

public void setWeight(Double weight) {

this.weight = weight;

}

public Vertex getFromVertex() {

return fromVertex;

}

public void setFromVertex(Vertex fromVertex) {


}

public Vertex getToVertex() {

return toVertex;

}

public void setToVertex(Vertex toVertex) {


}

}

4. Buatlah class baru dengan nama Graph.java, source code tampak seperti

berikut:

public class Graph {

99

private int numVertices;

private int numEdges;

private Vertex vertices[];

private Edge edges[];

private boolean isVertexExist(Vertex vertex) {

for (int i = 0; i < numVertices; i++) {

if

(vertices[i].getLabel().contentEquals(vertex.getLabel())) {

return true;

}

}

return false;

}

private int getVertexIndex(Vertex vertex) {

for (int i = 0; i < numVertices; i++) {

if

(vertices[i].getLabel().contentEquals(vertex.getLabel())) {

return i;

}

}

return -1;

}

public void addVertex(Vertex vertex) {

if (isVertexExist(vertex)) {

System.out.println("Vertex Already Exist");

return;

}

vertices[numVertices] = vertex;

++numVertices;

}

public Graph() {

this.vertices = new Vertex[10];

this.edges = new Edge[20];

}

public void addEdge(Vertex fromVertex, Vertex toVertex) {

if (!isVertexExist(fromVertex)) {

System.out.println("From Vertex does not exist");

return;

}

if (!isVertexExist(toVertex)) {

System.out.println("To Vertex does not exist");

}

edges[numEdges] = new Edge("e" +

String.valueOf(numEdges), fromVertex, toVertex);

++numEdges;

100

}

public void addEdge(Vertex fromVertex, Vertex toVertex,

Double weight) {

if (!isVertexExist(fromVertex)) {

System.out.println("From Vertex does not exist");

return;

}

if (!isVertexExist(toVertex)) {

System.out.println("To Vertex does not exist");

}

edges[numEdges] = new Edge("e" +

String.valueOf(numEdges), fromVertex, toVertex, weight);

++numEdges;

}

}

5. Mencoba Program. Modifikasi method main pada Class CobaGraph sehingga

terlihat seperti source berikut:


Graph myGraph = new Graph();

Vertex a = new Vertex("A");

Vertex b = new Vertex("B");

Vertex c = new Vertex("C");

Vertex d = new Vertex("D");

Vertex e = new Vertex("E");

myGraph.addVertex(a);

myGraph.addVertex(b);

myGraph.addVertex(c);

myGraph.addVertex(d);

myGraph.addEdge(a, b);

myGraph.addEdge(a, d);

myGraph.addEdge(c, a);

myGraph.addEdge(b, d);

myGraph.addEdge(d, c);

}

Jalankanlah program tersebut. Gambarkanlah bentuk Graphnya !

PERCOBAAN 2 : Adjacent Matrix

101


menambahkan method public void displayAdjacent().

2. Mencoba Program. Gunakan method tersebut pada main pada Class

CobaGraph. Contoh Output tampak seperti gambar berikut :

PERCOBAAN 3 : Incidence Matrix

1. Modifikasilah class Graph.java pada praktikum sebelumnya dengan

menambahkan method public void displayIncidence().

2. Mencoba Program. Gunakan method tersebut pada main pada Class

CobaGraph. Contoh Output tampak seperti gambar berikut :


1. Disconnected Graph adalah bentuk graph dimana salah satu vertexnya tidak

memiliki edge. Modifikasilah program diatas yang akan memunculkan pesan

102

“Disconnected Graph” jika dijumpai graph tersebut tergolong disconnected

Graph.

2. Complete Graph adalah jenis Graph dimana tiap vertexnya terhubung secara

langsung dengan vertex lainnya. Modifikasilah program diatas yang akan

memunculkan pesan “Complete Graph” jika dijumpai graph tersebut

tergolong disconnected Graph.

3. Cetaklah indegree dan outdegree dari sebuah vertex/simpul.

7. Referensi




Companies, Inc.

103


GRAPH TRAVERSAL

1. Tujuan


Mampu mengimplementasikan Graph Traversal untuk kasus sederhana.


1. Dapat menjelaskan konsep Graph Traversal Breadth-First Search (BFS) dan

Depth First Search (DFS).

2. Dapat menunjukkan path Graph jika menggunakan BFS atau DFS.

3. Dapat menggunakan alogoritma BFS atau DFS untuk kasus sederhana.

2. Durasi Waktu

2 x 4,5 jam

3. Dasar Teori

Algoritma BFS

Pada algoritma BFS, pencarian dimulai dari simpul akar dan mengunjungi semua

tetangga dari simpul tersebut. Kemudian, pencarian dilanjutkan dari setiap simpul

terdekat ke simpul tetangga yang belum dikunjungi, dan seterusnya, sampai

mendapatkan solusi.

• Traversal dimulai dari simpul v.

• Algoritma:

104

1. Kunjungi simpul v,

2. Kunjungi semua simpul yang bertetangga dengan simpul v terlebih

dahulu.

3. Kunjungi simpul yang belum dikunjungi dan bertetangga dengan simpul-

simpul yang tadi dikunjungi, demikian seterusnya.

Contoh :

Jika terdapat Graph seperti dibawah ini:

Maka, urutan penelusurannya adalah : A – B – C – D – E – F – G – H – I – J – K – L

Algoritma DFS (Depth First Search)

Pada algoritma DFS, pencarian dimulai dari simpul akar, dilanjutkan dengan

mengunjungi satu cabang sampai sedalam mungkin sebelum melakukan runut balik

dan melanjutkan pencarian dari cabang lain.

• Traversal dimulai dari simpul v.

• Algoritma:

1. Kunjungi simpul v,

2. Kunjungi simpul w yang bertetangga dengan simpul v.

3. Ulangi DFS mulai dari simpul w.

https://saungkode.files.wordpress.com/2014/04/pohonbiner.png

105

Contoh :

Jika terdapat Graph seperti dibawah ini:

Maka, urutan penelusurannya adalah : A – B – D – H – E – I – C – F – G – J – K – L

4. Peralatan :



5. Percobaan

PERCOBAAN 1 : Algoritma BFS

1. Modifikasilah class Graph pada percobaan sebelumnya dengan menambahkan

method bfs, source code tampak seperti berikut:

public void BFS(Vertex base) {

if (base.isWasVisited()) {

return;

}

base.setWasVisited(true);

System.out.print(base.getLabel());

for (int i = 0; i < numEdges; i++) {

if (edges[i].getFromVertex() == base) {

BFS(edges[i].getToVertex());

https://saungkode.files.wordpress.com/2014/04/pohonbiner.png

106

} else if (edges[i].getToVertex() == base) {

BFS(edges[i].getFromVertex());

}

}

}

2. Modifikasilah method main dalam program sehingga tampak seperti dibawah

ini.












myGraph.addVertex(e);


myGraph.addEdge(b, c);


myGraph.addEdge(c, e);

myGraph.displayAdjacent();

myGraph.displayIncidence();

System.out.println("");

myGraph.BFS(b);

}

3. Jalankan program, contoh output tampak seperti gambar dibawah:

107

PERCOBAAN 2 : Algoritma DFS

1. Modifikasilah class Graph pada percobaan sebelumnya dengan menambahkan

method public void DFS(Vertex base)

public void DFS(Vertex base) {

Queue<Vertex> q = new LinkedList();

q.add(base);

base.setWasVisited(true);

while (!q.isEmpty()) {

Vertex x = q.poll();

System.out.print(x.getLabel());

for (int i = 0; i < numEdges; i++) {

if (edges[i].getFromVertex() == x &&

!edges[i].getToVertex().isWasVisited()) {

q.add(edges[i].getToVertex());

edges[i].getToVertex().setWasVisited(true);

} else if (edges[i].getToVertex() == x &&

!edges[i].getFromVertex().isWasVisited()) {

q.add(edges[i].getFromVertex());

edges[i].getFromVertex().setWasVisited(true);

}

}

}

}

2. Modifikasilah method main dalam program sehingga tampak seperti dibawah

ini.

108












myGraph.addVertex(e);


myGraph.addEdge(b, c);


myGraph.addEdge(c, e);

myGraph.displayAdjacent();

myGraph.displayIncidence();

myGraph.DFS(b);

System.out.println("");

}

3. Jalankan program, contoh output tampak seperti gambar dibawah:

109


Modifikasi program diatas agar dapat menentukan jalur terpendek dari vertex A ke E

dari gambar graph dibawah ini:

7. Referensi




Companies, Inc.

110


SORTING

1. Tujuan


Mampu mengimplementasikan macam teknik sorting.


1. Dapat menggunakan teknik sorting Bubble sort

2. Dapat menggunakan teknik sorting Straight insertion sort

3. Dapat menggunakan teknik sorting Selection sort

4. Dapat menggunakan teknik sorting Quick sort

5. Dapat mengimplementasikan teknik sorting pada kasus sederhana

2. Durasi Waktu

2 x 4,5 jam

3. Dasar Teori

Sorting merupakan teknik pengurutan data yang sebelumnya disusun secara acak,

sehingga menjadi tersusun secara teratur menurut aturan tertentu. Biasanya untuk

menyimpan nilai yang memiliki tipe data sama.

Ada beberapa teknik sorting yaitu:

• Bubble sort

Metode bubble sort merupakan metode pengurutan yang mengambil proses

dengan menggunakan bubble atau exchange. Perbandingan data dilakukan

dari posisi pertama atau posisi terakhir bergeser satu persatu sampai semua

111

data dibandingkan. Jika terdapat N data dan data terkoleksi dari urutan 0

sampai dengan N-1 maka algoritma pengurutan dengan metode bubble sort

adalah sebagai berikut:

1. Bandingkan posisi data i = 0 dan j = 1.

2. Jika data diposisi i lebih besar daripada data diposisi j, maka data diposisi

i ditukar dengan data diposisi j (swap). Jika tidak penukaran posisi tidak

dilakukan.

3. Kemudian, lakukan perbandingan data diposisi i=1 dan data diposisi j=2.

Lakukan langkah 2, begitu juga untuk data berikutnya hingga i=N-2 dan

j=N-1.

4. Ulangi langkah 1, 2 dan 3 untuk data diposisi 0 sampai dengan data

diposisi N-2, karena data di posisi N-1 adalah data dengan nilai terbesar.

Untuk tahap selanjutnya data yang dibandingkan akan semakin berkurang

sebab data dengan nilai yang lebih besar akan terposisi dibagian sebelah

kanan data.

• Selection sort.

Metode pengurutan selection sort sering dipakai oleh orang saat bermain kartu

bridge dalam mengurutkan kartunya, yaitu dengan cara menyisip kartu yang

lebih kecil ke urutan sebelum posisi kartu yang dibandingkannya.

• Insertion sort

Metode selection sort merupakan perbaikan dari metode bubble sort dengan

mengurangi jumlah perbandingan. Selection sort merupakan metode

pengurutan dengan mencari nilai data terkecil dimulai dari data diposisi 0

hingga diposisi N-1. Jika terdapat N data dan data terkoleksi dari urutan 0

sampai dengan N-1 maka algoritma pengurutan dengan metode selection sort

adalah sebagai berikut:

1. Cari data terkecil dalam interval j = 0 sampai dengan j = N-1

112

2. Jika pada posisi pos ditemukan data yang terkecil, tukarkan data diposisi

pos dengan data di posisi i jika k.

3. Ulangi langkah 1 dan 2 dengan j = j+i sampai dengan j = N-1, dan

seterusnya sampai j = N - 1.

• Quick sort

Algoritma quick sort adalah sebagai berikut :

Jika diketahui n buah data integer (dalam array)

1. Jika n=1, selesai.

2. Else, pilih satu elemen sebagai pivot dan partisi data menjadi dua

bagian sedemikian hingga elemen-elemen yang lebih besar atau sama

dengan pivot berada di bagian sebelah kanan dan elemen-elemen yang

lebih kecil berada dibagian sebelah kiri.

3. Ulangi Quick Sort secara rekursif terhadap kedua sub bagian tersebut.

4. Peralatan :



5. Percobaan

PERCOBAAN 1 : Bubble Sort

1. Buatlah Proyek Baru – Java Application - dengan nama CobaBubbleSort

2. Buatlah class baru dengan nama Sort.java, tambahkan method bublesort().

Source code tampak seperti berikut:

public void bubleSort() {

for (int i = 0; i < data.length - 1; i++) {

for (int j = i; j < data.length; j++) {

if (data[i].compareTo(data[j]) >= 0) {

113

String temp = data[i];

data[i] = data[j];

data[j] = temp;

}

}

}

}

3. Ujikan untuk 10000 data integer random. Gunakan kelas Random untuk

membangkitkan bilangan acak.

PERCOBAAN 2 : Selection Sort

1. Modifikasi class sort, tambahkan method dan implementasi selectionsort().

2. Ujikan untuk 10000 data integer random.

PERCOBAAN 3 : Insertion Sort

1. Modifikasi class sort, tambahkan method dan implementasi insertionsort().


PERCOBAAN 4 : Quick Sort

1. Modifikasi class sort, tambahkan method dan implementasi selectionsort().


Isilah tabel berikut :

Teknik

Sorting

Waktu

eksekusi (ms)

Percobaan 1

Waktu

eksekusi

(ms)

Percobaan

2

Waktu

eksekusi

(ms)

Percobaan

3

Waktu

eksekusi

(ms)

Percobaan

4

Waktu

eksekusi

(ms)

Percobaan

5

Bubble Sort

114

Selection Sort

Insertion Sort

Quick Sort

Kesimpulan :


1. Buatlah program untuk melakukan pengurutan secara menaik / ascending dari

file berikut: unsorted.txt, metode pengurutan adalah straight insertion sort.

Petunjuk :

• Untuk melakukan pengurutan data bertipe string, dapat menggunakan

method String.compareTo

Contoh Unsorted String :

“abb”

“abc”

“acb”

Result Sorted String :

“abc”

“abb”

“acb”

• Untuk membaca file, dapat menggunakan class FileReader &

BufferedReader dari library java.io.

115

2. Buatlah perbandingan waktu proses (melalui program) pengurutan pada soal

no.1 jika menggunakan metode-metode berikut:

a. Bubble sort

b. Straight insertion sort

c. Quick sort

d. Shell sort

Petunjuk:

Untuk membandingkan waktu proses dapat menggunakan method

System.currentTimeMillis();

Contoh:

long start; long end; start = System.currentTimeMillis();

/*

…proses pengurutan

*/ end = System.currentTimeMillis();

System.out.println("\nWaktu proses : " + ((end - start) /

1000.0) + " detik");

7. Referensi

1. Fuadi Abidin, Taufik.”Teknik Pengurutan Sederhana”.15 November 2015.

http://www.informatika.unsyiah.ac.id/tfa/ds/bubblesort.pdf

2. Fuadi Abidin, Taufik.”Quick Sort”.15 November 2015.

http://www.informatika.unsyiah.ac.id/tfa/ds/quicksort.pdf

3. Fuadi Abidin, Taufik.”Selection Sort dan Insertion Sort”.15 November 2015.

http://www.informatika.unsyiah.ac.id/tfa/ds/selectionsort.pdf

116


SEARCHING

1. Tujuan


Mampu mengimplementasikan macam teknik searching.


1. Dapat menggunakan teknik sequential search

2. Dapat menggunakan teknik binary search

3. Dapat mengimplementasikan teknik searching pada kasus sederhana

2. Durasi Waktu

2 x 4,5 jam

3. Dasar Teori

Sequential Search

Teknik sequential search merupakan teknik paling sederhana, cara kerja teknik ini

adalah dengan cara data yang dicari dibandingkan satu per satu sampai data tersebut

ditemukan atau tidak ditemukan. Pada saat data yang dicari ditemukan, maka proses

pencarian langsung dihentikan. Tetapi jika belum ditemukan, maka pencarian

diteruskan sampai seluruh data dibandingkan. Dalam kasus paling buruk, untuk data

dengan N elemen harus dilakukan pencarian sebanyak N kali pula.

117

Binary Search

Teknik ini digunakan jika data telah diurutkan. Cara kerja teknik ini adalah dengan

menurutkan dahulu sejumlah data. Lalu bagi dua data-data tadi dengan jumlah data

yang sama pada masing-masingnya. Kemudian data dibandingkan dengan data

terakhir dari subdata yang pertama Jika data yang dicari lebih kecil, pencarian

dilanjutkan pada sub data pertama dengan terlebih dahulu membagi dua lagi data-data

tersebut dengan jumlah yang sama. Tetapi jika data yang dicari lebih besar dari data

terakhir subdata pertama, berarti data yang dicari kemungkinan terletak pada subdata

yang kedua. Proses diatas dilakukan berulang sampai data ditemukan atau tidak

ditemukan.

4. Peralatan :



5. Percobaan

PERCOBAAN 1 : Sequential Search

1. Buatlah Proyek Baru – Java Application - dengan nama CobaSearch

2. Buatlah class baru dengan nama Search.java, tambahkan method dan

implementasi dari sequentialSearch().

PERCOBAAN 2 : Binary Search

1. Modifikasi kelas Search.java, tambahkan method dan implementasi dari

binarySearch().

Isilah tabel pengujian berikut berikut untuk jenis data uji:

a. 10000 Random data integer

118

b. 10000 data urut integer ascending

c. 10000 data urut descending

Data yang dicari: satu data yang diambil random 1-10000

Teknik

Searching

Waktu

eksekusi (ms)

Percobaan 1

Waktu

eksekusi (ms)

Percobaan 2

Waktu

eksekusi (ms)

Percobaan 3

Waktu

eksekusi (ms)

Percobaan 4

Waktu

eksekusi (ms)

Percobaan 5

Sequential

Search

Binary

Search

Kesimpulan:


Dari program yang dibuat pada latihan PRAKTIKUM 11 Sorting no.1, tambahkanlah

fungsi untuk mencari String. Gunakan 2 metode yaitu sequential search dan binary

search. Kemudian dalam outputnya munculkan juga lama waktu pencarian.

7. Referensi




Companies, Inc.

modul struktur data · 2020. 8. 6. · kata pengantar modul praktikum ini dibuat sebagai pedoman...

Documents