asd modul 6 (sorting&searching).pdf

7/23/2019 ASD Modul 6 (Sorting&Searching).pdf

1/11

Dokumen Laboratorium Teknik Informatika UMM @ 2015Modul Praktikum Algoritma dan Struktur DataBy. Team Informatika UMM

PRAKTIKUM ALGORITMA DAN STRUKTUR DATA

MODUL KE-6

ALGORITMAPENCARIAN DAN PENGURUTAN

LABORATORIUM PEMROGRAMAN

PROGRAM STUDI TEKNIK INFORMATIKA

FAKULTAS TEKNIK

UNIVERSITAS MUHAMMADIYAH MALANG

2015


2/11


I. TUJUAN

Mahasiswa mampu :

1. Memahami algoritma pencarian (linear search dan binary search)2. Menerapkan algoritma pencarian kedalam pemrograman

3.

Memahami algoritma pengurutan (insertion sort, selection sort, bubble sort, merge sort)4. Menerapkan algoritma pengurutan kedalam pemrograman

II. ALAT YANG DIGUNAKAN

Peralatan yang digunakan :

1. Perangkat PC yang terinstall Java

2. Editor Java

III.

DASAR TEORISearching adalah proses pencarian data yang ada pada suatu deret data dengan cara

menelusuri data-data tersebut. Tahapan paling penting pada searching: memeriksa jika

data yang dicari sama dengan data yang ada pada deret data.

1. Sequential Search

Disebut juga linear search atau Metode pencarian beruntun.

Adalah suatu teknik pencarian data yang akan menelusuri tiap elemen satu per-satu

dari awal sampai akhir.

Data awal = tidak harus dalam kondisi terurut.

Best case: jika data yang dicari terletak di depan sehingga waktu yang dibutuhkan

minimal. Worst case: jika data yang dicari terletak di akhir sehingga waktu yang dibutuhkan

maksimal.

2. Binary Search

Teknik pencarian = data dibagi menjadi dua bagian untuk setiap kali proses

pencarian.

Data awal harus dalam kondisi terurut. Sehingga harus dilakukan proses sorting

terlebih dahulu untuk data awal.

Mencari posisi tengah :

Jika data tengah sama, berarti ketemu.

Jika lebih besar, maka posisi awal adalah posisi tengah + 1

Jika lebih kecil, maka posisi akhir adalah posisi tengah1

Best case: jika data yang dicari terletak di posisi tengah.

Worst case: jika data yang dicari tidak ditemukan.

Posisi tengah = (posisi awal + posisi akhir) / 2


3/11



4/11



5/11


IV. PROSEDUR PELAKSANAANProsedur pelaksanaan praktikum adalah sebagai berikut :

1. Mahasiswa mencoba latihan yang ada pada modul praktikum

2.

Mahasiswa menganalisa hasil dari program pada latihan yang telah dijalankan

3.

Mahasiswa mengerjakan tugas yang diberikan

4. Mahasiswa mendemonstrasikan program yang telah dikerjakan pada dosen/assisten

5. Mahasiswa membuat laporan dari tugas yang telah dikerjakan

6. Upload laporan melalui e-labit.umm.ac.id

V. LATIHAN

ALGORITMA PENCARIAN

1. Linear atau Sequential Search

import java.util.Arrays;

import java.util.Scanner;import static java.lang.Math.*;

public class SequentialSearch{

public static void main(String args[])

{

Scanner sc = new Scanner(System.in);int j, k, number, size;

boolean found = false;

System.out.print("Enter the array size: ");size = sc.nextInt();

int[] intArray = new int[size];

for (j=0; j


6/11


2. Binary Search

class OrdArray

{private long[] a; // ref to array a

private int nElems; // number of data items

//-----------------------------------------------------------public OrdArray(int max) // constructor

{

a = new long[max]; // create arraynElems = 0;

}

//-----------------------------------------------------------public int size()

{ return nElems; }

//-----------------------------------------------------------public int find(long searchKey)

{

int lowerBound = 0;int upperBound = nElems-1;

int curIn;

while(true){

curIn = (lowerBound + upperBound ) / 2;

if(a[curIn]==searchKey)return curIn; // found it

else if(lowerBound > upperBound)

return nElems; // cant find itelse // divide range

{

if(a[curIn] < searchKey)

lowerBound = curIn + 1; // its in upper half

else

upperBound = curIn - 1; // its in lower half} // end else divide range

} // end while

} // end find()//-----------------------------------------------------------

public void insert(long value) // put element into array

{int j;

for(j=0; j value) // (linear search)break;

for(int k=nElems; k>j; k--) // move bigger ones up

a[k] = a[k-1];

a[j] = value; // insert itnElems++; // increment size

} // end insert()//-----------------------------------------------------------

public boolean delete(long value){

int j = find(value);if(j==nElems) // cant find it

return false;else // found it

{

for(int k=j; k


7/11


} // end delete()

//-----------------------------------------------------------

public void display() // displays array contents{for(int j=0; j X[j]){

min = j;}

}

if(min!=i){t = X[min];

X[min] = X[i];X[i] = t;


8/11


}

}

}public static void main(String[] args)

{

cetak();System.out.println();

selectionSort();

cetak();System.out.println();

}

}

2.Contoh method untuk algoritma pengurutan Insertion Sort

void insertionSort()

{int i=1,t,j;

int n= X.length;

for(i=1;i= 0; j--) {

if (t < X[j]){X[j+1] = X[j];

X[j]=t;

}else {

X[j+1] = t;break;

}

}

}}

3.

Contoh method untuk algoritma pengurutan Bubble Sort

void bubbleSort()

{

boolean status = true;int i,j,tmp;

int n = X.length;

for (i=0; i < n-1 && status; i++){status = false;

for (j=n-1; j > i; j--) {

if (X[j] < X[j-1]) {tmp = X[j];X[j] = X[j-1];

X[j-1] = tmp;

status = true;}

}

}}


9/11


4.

Contoh method untuk algoritma pengurutan Merge Sort

void mergeSort(int l,int r)

{

if(l==r) return;else{

int mid = (l+r)/2;mergeSort(l, mid);

mergeSort(mid+1,r);

Merging(l,mid+1,r);}

}

static void Merging(int kiri,int tengah, int kanan)

{

int j=0;

int batasBawah = kiri;

int mid = tengah-1;

int n=kanan-batasBawah+1;

int tampung[] = new int[X.length];

while(kiri


10/11


VI. TUGAS PRAKTIKUM

Melanjutkan tugas praktikum sebelumnya yaitu aplikasi kontak telpon yang mana sebelumnya

kita sudah membuat buku telpon dengan fitur berikut :

a. Tambah kontak unlimited.

b. Edit Kontak.

c. Hapus Kontak.

d. Lihat Kontak. (plus searching).

e. Scroll kontak (geser a b c d).

Sekarang kita bisa tambahkan satu fitur lagi yaitu fitur sorting. Fitur ini bisa digunakan untuk

mengurutkan nama-nama kontak yang ada pada kontak telpon kita. Dengan aturan berikut :

1.

Mengurutkan data kontak telpon berdasrkan nama kontak dan bisa diurutkan 2 arah,yaitu ascending dan descending. Dengan syarat tanpa menggunakan library pada java

dengan kata lain coding manual. (point max 85).

2. Dengan menyelesaikan aturan nomor 1 (diatas) ditambah dengan mengerjakan dengan

2 pola, yaitu quick sort, dan merge sort. Jadi pada menu aplikasi kita bisa memilih metode

sorting yaitu quick sort, dan merge sort. (point max 110).

Nilai akhir demo akan dikurangi dgn kekurangan pada fitur (tiap fitur -5 point) dengan syarat

sudah bisa mengerjakan yang pencarian 1 atau 2. Misal :

Nilai yang di dapat : 85.a.

Tambah kontak unlimited. (sudah)

b. Edit Kontak. (belum)

c. Hapus Kontak. (belum)

d. Lihat Kontak. (belum)

e. Scroll kontak (geser a b c d). (belum)

f. Searching (sudah)

g. Sorting (sudah)

Nilai akhir adalah 85-5-5-5-5=65.


11/11


Keterangan :

1. Tugas praktikum dikerjakan sendiri, jika ketahuan mengcopas, mencontoh, mereplika,

menjiplak dll akan dikenakan sanksi nilai x .

2. Tidak ada demo susulan, sesuai dengan jadwal yang telah ditentukan, kecuali ada alasan

yang logis dan dapat di maklumi.

3. Kriteria penilaian praktikum:

a. 25% Absensi.

b. 50% demo tugas.

c. 25% laporan praktikum.

d. Tambahan nilai (sesuai kebijakan aslab masing-masing), misal keaktifan dll.

4. Kriteria penilaian laporan:

a. Menggunakan template yang sudah disediakan.

b. Melampirkan hasil praktikum (latihan dan tugas modul) dan screenshot hasil programdan

penjelasannya.

c. Dikerjakan sendiri, jika ketahuan mengcopas, mencontoh, mereplika, menjiplak dll akan

dikenakan sanksi pengosongan nilai laporan.

Penting!Tetap semangat, jangan menyerah dan pasti bisa jika mau berusaha, jangan lupa juga untuk

terus berdoa agar dapat mencapai hasil yang maksimal, jangan pernah takut untuk bertanya jika

masih ada kebingungan yang melanda, diselingi terus berolah raga, makan yang banyak dan

sehat sesuai 4 sehat 5 sempurna serta minum multivitamin agar tetap bugar :D,

asd modul 6 (sorting&searching).pdf

Documents