bab iii - array statis

ARRAY STATIS (lanjutan)

DIKTAT STRUKTUR DATA

Oleh:Tim Struktur Data IF

OPERASI ARRAY STATIS (lanjutan)

3. Pencarian (searching) array Proses menemukan suatu data yang terdapat dalam suatu array. Proses ini menghasilkan nilai benar atau salah.

Metode Pencarian1. Sequential / Linear Search

2. Binary Search

Metode Pencarian (lanjutan)Sequential / Linear

Search:

1. Tanpa Boolean

a. Tanpa Sentinel

b. Dengan Sentinel

2. Dengan Boolean

SEQUENTIAL SEARCH

Tanpa boolean tanpa

sentinel:

1. Tidak menggunakan variabel

boolean

2. Tidak mempunyai tambahan

elemen di akhir array.

Sequential Search tanpa Sentinel

berikut ini terdapat array yang akan diproses:

Number

Data yang akan dicari: 9 Number[1] = 9? Number[2] = 9? Number[3] = 9?

hasil: 9 ditemukan pada indeks ke- [3]

5 1 9 4 2[1] [2] [3] [4] [5]

i i + 1

i i + 1

i (STOP SEARCH)

Sequential Search tanpa Sentinel

Procedure SeqSearchTanpaSentinel (Input nama_array:tipe_array){I.S. : elemen array [1..maks_array] sudah terdefinisi}{F.S. : menampilkan hasil pencarian (ditemukan/tidak)}Kamus:

i : integerdata_cari : tipedata

Algoritma:input(data_cari)i 1while(nama_array [i] ≠ data_cari) and (i < maks_array) do

i i + 1endwhileif (nama_array[i] = data_cari)then

output(data_cari,’ ditemukan pada indeks ke-’,i)else

output(data_cari,’ tidak ditemukan’)endif

EndProcedure

SEQUENTIAL SEARCH (lanjutan)

Tanpa boolean dengan sentinel:

1. Tidak menggunakan variabel

boolean

2. Mempunyai tambahan elemen

di akhir array untuk menyimpan

data cari apabila data cari tidak

ditemukan

Sequential Search dengan Sentinel

Data yang dicari: 9

Number

Hasil: Data ditemukan pada indeks ke- 3

Data yang dicari: 10

Number

Result: Data tidak ditemukan

5 1 9 4 2 9[1] [2] [3] [4] [5] [6]

sentinel

5 1 9 4 2 10[1] [2] [3] [4] [5] [6]

sentinel

Sequential Search Use SentinelProcedure SeqSearchSentinel (Input nama_array:tipe_array){I.S. : elemen array [1..maks_array] sudah terdefinisi}{F.S. : menampilkan hasil pencarian (ditemukan/tidak)}Kamus:i : integerdata_cari : tipedataAlgoritma:input(data_cari)i 1nama_array(maks_array + 1) data_cariwhile (nama_array [i] ≠ data_cari) doi i + 1endwhileif (i < maks_array+1)thenoutput(data_cari,’ ditemukan pada indeks ke-’,i)elseoutput(data_cari,’ tidak ditemukan’)endifEndProcedure

SEQUENTIAL SEARCH (lanjutan)

Dengan boolean:

1. Menggunakan variabel

boolean

2. Menghasilkan nilai TRUE

atau FALSE di akhir

pencarian

Sequential Search dengan Boolean

berikut ini adalah array yang akan diproses:

Number

Data yang akan dicari: 9 Number[1] = 9? Number[2] = 9? Number[3] = 9?

hasil: 9 ditemukan pada indeks ke- 3

5 1 9 4 2[1] [2] [3] [4] [5]

KETEMU FALSE

KETEMU FALSE

KETEMU TRUE (STOP SEARCH)

Sequential Search Use SentinelProcedure SeqSearchBoolean (Input nama_array:tipe_array){I.S. : elemen array [1..maks_array] sudah terdefinisi}{F.S. : menampilkan data yg dicari ditemukan atau tidak ditemukan}Kamus:

i : integerketemu : booleandata_cari : tipedata

Algoritma:input(data_cari)i 1ketemu falsewhile (not ketemu) and (i ≤ maks_array) do

if(nama_var_array(i) = data_cari)then ketemu trueelse i i + 1endif

endwhileif (ketemu)then

output(data_cari,’ ditemukan pada indeks ke-’,i)else

output(data_cari,’ tidak ditemukan’)endif

EndProcedure

BINARY SEARCH

1. Data harus terurut, baik secara ascending atau

descending

2. Mekanismenya adalah dengan cara membagi larik

menjadi dua bagian yaitu bagian kiri (indeks

terkecil/Ia) sampai ke indeks tengah dan bagian

kanan mulai dari indeks tengah sampai indeks terbesar

(Ib)

3. Indeks tengah (k) : (Ia+Ib) div 2 (posisi tengah larik)

BINARY SEARCH (lanjutan)4. Jika data yang dicari lebih kecil dari

data di posisi tengah, maka pencarian

dilanjutkan ke bagian kiri

5. Jika data yang dicari lebih besar dari

data di posisi tengah, maka pencarian

dilanjutkan ke bagian kanan

KASUS BINARY SEARCHData yang dicari = 7Banyak data = 5Angka

Angka

3 7 12 15 29[1] [2] [3] [4] [5]

Ia k IbBag. Kiri Bag. Kanan

3 7[1] [2]

Ia Ibk

Bag. Kiri Bag. Kanan

KASUS BINARY SEARCH

Angka 7[2]

IbIak

Jadi:Angka 7 ditemukan pada indeks ke- 2

Binary SearchProcedure BinarySearch (Input nama_array : tipe_array){I.S. : elemen array yang terurut secara ascending sudah terdefinisi}{F.S. : menampilkan data yg dicari ditemukan atau tidak ditemukan}Kamus:

Ia, Ib, k : integerketemu : booleandata_cari : tipedata

Algoritma:input(data_cari)Ia 1Ib maks_arrayketemu falsewhile (not ketemu) and (Ia ≤ Ib) do

k (Ia + Ib) div 2if (nama_var_array[k] = data_cari) then ketemu true else if (nama_var_array[k] < data_cari) then Ia k + 1 else Ib k – 1 endifendif

endwhileEndprocedure


4. Pengurutan (sorting) array a. Bubble Sortb. Selection Sortc. Insertion Sortd. Radix Sort e. Merge Sortf. Quick Sort

BUBBLE SORT Proses menyusun data acak dengan cara

menggelembungkan data yang ringan. Jika akan disusun secara ascending,

maka penggelembungan dilakukan dari kanan ke kiri (bawah ke atas).

Tapi jika akan disusun secara descending, maka penggelembungan dilakukan dari kiri ke kanan (atas ke bawah)

Proses Bubble Sort (Ascending)Berikut adalah data yang akan diurutkan secara ascending: 6 3 9 1 5

Step 1 : 6 3 9 1 5

6 3 9 1 5

6 3 1 9 5

6 1 3 9 5

1 6 3 9 5

j

j

j

j

Proses Bubble Sort (Ascending)

Step 2 : 1 6 3 9 5

1 6 3 5 9

1 6 3 5 9

1 3 6 5 9

j

j

j

Proses Bubble Sort (Ascending)

Step 3 : 1 3 6 5 9

1 3 6 5 9

1 3 5 6 9

Step 4 : 1 3 5 6 9

1 3 5 6 9

Array setelah diurutkan secara ascending:1 3 5 6 9

j

j

j

BUBBLE SORT ASC

ArrayAwal:

6 3 9 1 5

step. 1 1 6 3 9 5

step. 2 1 3 6 5 9

step. 3 1 3 5 6 9

step. 4 1 3 5 6 9

Bubble Sort AscendingProcedure BubbleSortAsc(I/O nama_var_array : nama_tipe_array, Input N : integer){I.S. : array[1..N] sudah terdefinisi}{F.S. : menghasilkan array[1..N] yang tersusun secara ascending}Kamus: i, j : integer

temp : tipedataAlgoritma:

for i 1 to N-1 do for j n downto i+1 do

if(nama_var_array[j] < nama_var_array[j-1]) then temp nama_var_array[j] nama_var_array[j] nama_var_array[j-1] nama_var_array[j-1] temp endif

endforendfor

EndProcedure

SELECTION SORT

Proses menyusun data acak dengan cara menyeleksi atau menentukan data terbesar atau data terkecil dari elemen array yang ditinjau.- Maximum Sort- Minimum Sort

Proses Maximum Sort (Ascending)

This is an array that will be sorted in Ascending way : 6 3 9 1 5

Step 1 : 6 3 9 1 5

6 3 9 1 5

6 3 9 1 5

6 3 9 1 5

6 3 9 1 5

6 3 5 1 9

j

j

j

jmax

max

max

max

max j


Step 2 : 6 3 5 1 9

6 3 5 1 9

6 3 5 1 9

6 3 5 1 9

1 3 5 6 9

j

j

jmax

max

max

max j


Step 3 : 1 3 5 6 9

1 3 5 6 9

1 3 5 6 9

1 3 5 6 9

Step 4 : 1 3 5 6 9

1 3 5 6 9

Array after sorted in descending way: 1 3 5 6 9

j

j

max

max

max

max

j

j

max

MAXIMUM SORT ASC

ArrayAwal:

6 3 9 1 5

step 1

6 3 5 1 9step

2 1 3 5 6 9step

3 1 3 5 6 9step

4 1 3 5 6 9

SELECTION SORT (lanjutan)

ArrayAwal:

6 3 9 1 5

SILAKAN DICOBA UNTUK MAXIMUM SORT DSC,

MINIMUM SORT ASC dan MINIMUM SORT DSC !!!

OPERASI ARRAY STATIS

5. Penghancuran (destroy) array

Proses mengembalikan data array ke

nilai awal

LATIHAN

Diketahui array Nama :Kiki, Arif, Sari, Ahmad, Doni, Maman, Aras, Dedi, Yuni, Murni, Zenal.Dicari Nama “Wiwin”, dengan menggunakan metode Binary Search pada data terurut secara Descending, maka: 1. Berapa kali iterasi sampai pencarian berhenti?2. Berapa harga indeks atas (Ia) dan indeks bawah

(Ib) ketika pencarian berhenti?3. Posisi tengah pada iterasi ke-3 adalah ……


4. Pengurutan (Sorting)a. Bubble Sortb. Selection Sortc. Insertion Sortd. Radix Sort e. Merge Sortf. Quick Sort

TUGAS

TUGAS

Kelompok Tugas:1. Sequential Search Tanpa Sentinel (Insertion Sort Asc)2. Sequential Search Tanpa Sentinel (Radix Sort Asc)3. Sequential Search Dengan Sentinel (Merge Sort Asc)4. Sequential Search Dengan Sentinel (Quick Sort Asc)5. Sequential Search Dengan Boolean (Insertion Sort

Dsc)6. Sequential Search Dengan Boolean (Radix Sort Dsc)7. Binary Search (Merge Sort Dsc)8. Binary Search (Quick Sort Dsc)

Catatan:Kasus yang diambil setiap kelompok harus berbeda

TUGAS

Buatlah Makalah per kelompok (Algoritma dan Program) dengan ketentuan sebagai berikut:1. Kasus (Asumsi + Batasan)2. Teori dari Metode Sorting yang

digunakan3. Algoritma dari kasus yang harus

diselesaikan4. Listing program5. Layar tampilan6. Kontribusi masing-masing anggota

kelompok

TUGAS

Ketentuan:1. Buat menjadi 8 kelompok2. Tipe data yang digunakan minimal array of

record dengan minimal jumlah field = 33. Gunakan modul atau subrutin berparameter

(minimal 5 prosedur dan 2 fungsi)4. Gunakan operasi-operasi yang telah dijelaskan

mulai dari operasi penciptaan sampai operasi penghancuran

5. Penyelesaian kasus menggunakan menu pilihan

6. Cover berisi judul, Nama dan NIM, serta kelas

Contoh Cover

Tugas Struktur Data ke-2

Sequential Search Tanpa SentinelDengan Insertion Sort secara Ascending

Oleh:Nama – NIM

Kelas : IF-……

{logo UNIKOM}

Program Studi Teknik InformatikaFakultas Teknik dan Ilmu Komputer

UNIKOM2013

MATERI SELANJUTNYA

SINGLE LINKED LIST

See u next week...

bab iii - array statis

Documents