2010. Sequential Search (Tanpa Variabel Logika) untuk kondisi data tidak terurut

11/11/2010

Tujuan TUJUAN MATERI Setelah mengikuti materi pertemuan ini, mahasiswa diharapkan dapat

Searching & Sorting

Menjelaskan dan menggunakan metode pencarian dalam menyelesaikan masalah pencarian data/informasi pada

1.

Pertemuan 9-10

Dosen Pembina Danang Junaedi

Kondisi data yang tidak terurut Kondisi data terurut

Menjelaskan dan menggunakan metode untuk mengurutkan data/informasi dalam menyelesaikan masalah pegurutan data/informasi

2.

Jurusan Teknik Informatika

Lingkup Materi Sequential dengan variabel logika Sequential tanpa variabel logika Sentinel

a. b. c.

2.

a. b.

3.

Pencarian pada Data yang Terurut Sequential tanpa variabel logika Binary search/dikotomik

a. b. c.

Bubble Sort Selection Sort Insertion Sort


Tujuan : mencari suatu nilai/elemen dalam kumpulan nilai (yang disimpan dalam array, list atau file) yang sudah diketahui Jenis

Searching pada Data Tidak Terurut

Searching pada Data Terurut

Sorting

IX/XII - 3

Universitas Widyatama

SEQUENTIAL SEARCH Pencarian pada Data yang Tidak Terurut Disini proses pencarian dilakukan secara beruntun dari data pertama sampai data terakhir. Pencarian pada Data yang Terurut Disini proses pencarian dapat dilakukan secara berurutan dari data pertama sampai data terakhir atau tidak berurutan.


Searching (1)

Pencarian pada Data yang Tidak Terurut

1.

IX/XII - 2

Sequential Search Sequential Search Binary Search/Pencarian Bagi Dua/ Dikotomik Search


IX/XII - 4


Sequential Search (Tanpa Variabel Logika) untuk kondisi data tidak terurut

5 10 11 2 8

13 7

20 35 18

• Misalnya, terdapat sebuah array seperti di atas • Keadaan awal : I 1 • Pencarian dilakukan sampai dengan posisi akhir pada array atau data ditemukan

Masalah : Diketahui sebuah array A[1..10] yang berisi data integer dengan kondisi tidak terurut. Buat algoritma untuk mencari nilai X dan beri pesan ditemukan atau tidak nilai tersebut


IX/XII - 5


• Keadaan Akhir : I akan diisi nomor indeks yang array-nya bernilai X, bila nilai yang dicari ketemu


IX/XII - 6


1

11/11/2010

Sequential Search (Tanpa Variabel Logika) untuk kondisi data tidak terurut : Algoritma untuk mencari bilangan X : ARRAY A[1..10] = array yang menampung data dalam tabel I = integer, counter pengulangan X = integer, variabel yang menampung data yang akan dicari Algoritma : INPUT X, I 1 WHILE (I < 10) AND ( A[I] <> X) DO II+1 END WHILE IF A[I] = X THEN OUTPUT ‘Ditemukan di elemen ke-‘,I ELSE OUTPUT ‘Tidak ditemukan’ END IF

Sequential Search (Tanpa Variabel Logika) untuk kondisi data terurut

Judul Kamus


IX/XII - 7


Sequential Search (Tanpa Variabel Logika) untuk kondisi data terurut 2 5

7

8 10 11 13 18 20 35

• Misalnya, terdapat sebuah array seperti di atas • Keadaan awal : I 1 • Pencarian dilakukan selama nilai dalam array < nilai yang dicari • Keadaan Akhir : I akan diisi nomor indeks yang array-nya bernilai X, bila nilai yang dicari ketemu


IX/XII - 9


Sequential Search Tanpa Variabel Logika

Data Tidak Terurut scanf(“%d”,&Cari); i = 1; while (i <= N && Cari != Barang[i]) { i++; } (i < N) ? printf("Barang ditemukan") : printf("Barang tidak ditemukan");

7

8 10 11 13 18 20 35

• Misalnya, terdapat sebuah array seperti di atas • Keadaan awal : I 1 • Pencarian dilakukan selama nilai dalam array < nilai yang dicari • Keadaan Akhir : I akan diisi nomor indeks yang array-nya bernilai X, bila nilai yang dicari ketemu


IX/XII - 8


Sequential Search (Tanpa Variabel Logika) untuk kondisi data terurut : Algoritma untuk mencari nilai X : ARRAY A[1..10] = array yang menampung data I = integer, counter pengulangan X = integer, variabel yang menampung data yang akan dicari Algoritma : INPUT X, I 1 WHILE (A[I] < X) and (I <= 10) DO II+1 END WHILE IF A[I] = X THEN OUTPUT ‘Ditemukan di elemen ke-‘,I ELSE OUTPUT ‘Tidak ketemu’ END IF Judul Kamus


IX/XII - 10


Sequential Search (Dengan Variabel Logika) untuk kondisi data tidak terurut

Searching (2)

2 5

Data Terurut scanf(“%d”,&Cari); i = 1; while (i <= N && Cari < Barang[i]) { i++; } (Barang[i] == Cari) ? printf("Barang ditemukan") : printf("Barang tidak ditemukan");

5

10

11

2

8

13

7

20

35

18

•

Misalnya, terdapat sebuah array seperti di atas

•

Keadaan awal : Found False, I 1

•

Pencarian dilakukan sampai dengan posisi akhir pada array atau data ditemukan

•

Keadaan Akhir : Found False, berarti nilai yang dicari tidak ketemu Found True, berarti nilai yang dicari ketemu I akan diisi nomor indeks yang array-nya bernilai X, bila nilai yang dicari ketemu


IX/XII - 11



IX/XII - 12


2

11/11/2010

Sequential Search (Dengan Variabel Logika) untuk kondisi data tidak terurut Judul Kamus

: Algoritma untuk mencari bilangan X : ARRAY A[1..10] = array yang menampung data dalam tabel I = integer, counter pengulangan X = integer, variabel yang menampung data yang akan dicari Found = boolean, variabel logika untuk mengetahui ketemu/tidak nilai yang akan dicari Algoritma : INPUT X, I 1, Found False WHILE (I <= 10) AND ( Not Found) DO IF A[I] = X THEN Found True ELSE II+1 ENDIF END WHILE IF Found THEN OUTPUT ‘Ditemukan di elemen ke-‘,I ELSE OUTPUT ‘Tidak ditemukan’ END IF Jurusan Teknik Informatika

IX/XII - 13


Sequential Search (Tanpa Variabel Logika) untuk kondisi data terurut 2 5

• Keadaan awal : Found False, I 1 • Pencarian dilakukan selama nilai dalam array < nilai yang dicari • Keadaan Akhir : Found False, berarti nilai yang dicari tidak ketemu Found True, berarti nilai yang dicari ketemu I akan diisi nomor indeks yang array-nya bernilai X, bila nilai yang dicari ketemu Jurusan Teknik Informatika

IX/XII - 15


Sequential Search (Sentinel) untuk kondisi data tidak terurut 5

10

11

2 8

13 7

20

35

18 Sentinel di akhir

Sentinel di awal

• Misalnya, terdapat sebuah array seperti di atas • Keadaan awal : I 1 • Pencarian dilakukan sampai dengan posisi sentinel. Jika menggunakan sentinel di awal pencarian dilakukan dari posisi paling belakang ke depan, sebaliknya jika menggunakan sentinel di akhir pencarian dilakukan dari depan ke belakang • Keadaan Akhir : I akan diisi nomor indeks yang array-nya bernilai X, namun apabila I bukan sentinel berarti nilai X ditemukan Jurusan Teknik Informatika

IX/XII - 17


IX/XII - 14


Searching (2)

Judul Kamus


8 10 11 13 18 20 35

• Misalnya, terdapat sebuah array seperti di atas

Sequential Search (Dengan Variabel Logika) untuk kondisi data terurut : Algoritma untuk mencari bilangan X : ARRAY A[1..10] = array yang menampung data dalam tabel I = integer, counter pengulangan X = integer, variabel yang menampung data yang akan dicari Found = boolean, variabel logika untuk mengetahui ketemu/tidak nilai yang akan dicari Algoritma : INPUT X, I 1, Found False WHILE (I <= 10) AND ( Not Found) AND (A[I] < X) DO IF A[I] = X THEN Found True ELSE II+1 ENDIF END WHILE IF Found THEN OUTPUT ‘Ditemukan di elemen ke-‘,I ELSE OUTPUT ‘Tidak ditemukan’ END IF

7

Sequential Search Dengan Variabel Logika

Data Tidak Terurut scanf(“%d”,&Cari); i = 1; ketemu = 0; while (i <= N && ketemu == 0){ (Cari == Barang[i]) ? ketemu = 1: i++; } (ketemu == 1) ? printf("Barang ditemukan") : printf("Barang tidak ditemukan"); Jurusan Teknik Informatika

Data Terurut scanf(“%d”,&Cari); i = 1; Ketemu = 0; while (i <= N && Cari < Barang[i] && ketemu ==0){ (Cari == Barang[i]) ? ketemu = 1: i++; } (ketemu == 1) ? printf("Barang ditemukan") : printf("Barang tidak ditemukan");

IX/XII - 16


Sequential Search (Sentinel) untuk kondisi data tidak terurut

{Sentinel adalah elemen fiktif yang dipasang setelah elemen terakhir atau di awal table} Judul : Algoritma untuk mencari bilangan X Kamus : ARRAY A[1..11] = array yang menampung data dalam tabel I = integer, counter pengulangan X = integer, variabel yang menampung data yang akan dicari Found = boolean, variabel logika Algoritma : INPUT X, I 1, A[11] X {Sentinel di akhir} WHILE A[I] <> X DO II+1 END WHILE IF I <> 11 THEN OUTPUT ‘Ditemukan di elemen ke-‘,I ELSE OUTPUT ‘Tidak ketemu’ END IF Jurusan Teknik Informatika

IX/XII - 18


3

11/11/2010

Sequential Search (Sentinel) untuk kondisi data terurut 2

5

7

8 10 11

13 18

20

35 Sentinel di akhir

Sentinel di awal

•

Misalnya, terdapat sebuah array seperti di atas

•

Keadaan awal : I 1

•

Pencarian dilakukan selama nilai dalam array < nilai pada posisi sentinel. Jika menggunakan sentinel di awal pencarian dilakukan dari posisi paling belakang ke depan, sebaliknya jika menggunakan sentinel di akhir pencarian dilakukan dari depan ke belakang

•

Keadaan Akhir : I akan diisi nomor indeks yang array-nya bernilai X, namun apabila I bukan sentinel berarti nilai X ditemukan


IX/XII - 19


Sequential Search Dengan Sentinel di awal


Data Terurut i = N; j=0; scanf(“%d”,&Barang[j]); while (i >= 1 && Barang[i] < Barang[j]) { ii-- -; } (i >= 1) ? printf("Barang ditemukan") :printf("Barang tidak ditemukan");

IX/XII - 21

{Sentinel adalah elemen fiktif yang dipasang setelah elemen terakhir atau di awal table} Judul : Algoritma untuk mencari bilangan X Kamus : ARRAY A[1..11] = array yang menampung data dalam tabel I = integer, counter pengulangan X = integer, variabel yang menampung data yang akan dicari Found = boolean, variabel logika Algoritma : INPUT X, I 1, A[11] X {Sentinel di akhir} WHILE A[I] < A[11] DO II+1 END WHILE IF I <> 11 THEN OUTPUT ‘Ditemukan di elemen ke-‘,I ELSE OUTPUT ‘Tidak ketemu’ END IF Jurusan Teknik Informatika


Merupakan metode pencarian yang diterapkan pada kumpulan data yang telah terurut (terurut menaik atau terurut menurun), yang merupakan syarat mutlak dari proses pencarian yang menggunakan metode ini. Pencarian dilakukan dengan membagi dua larik yang sudah terurut, hal ini dilakukan sampai data tersebut ditemukan (nilai yang dicari adalah nilai yang di tengah)

IX/XII - 23


Merupakan metode pencarian yang diterapkan pada kumpulan data yang telah terurut (terurut menaik atau terurut menurun), yang merupakan syarat mutlak dari proses pencarian yang menggunakan metode ini. Pencarian dilakukan dengan membagi dua larik yang sudah terurut, hal ini dilakukan sampai data tersebut ditemukan (nilai yang dicari adalah nilai yang di tengah) Ilustrasi metode Binary Search : • Terdapat suatu larik A yang sudah terurut, dan akan dicari suatu nilai tertentu pada larik tersebut, misalnya nilai X.


Binary Search (Pencarian Bagi Dua


IX/XII - 20

Binary Search (Pencarian Bagi Dua)

Searching (2) Data Tidak Terurut i = N; j=0; scanf(“%d”,&Barang[j]); while (i >= 1 && Barang[i] != Barang[j]) { ii- -; } (i >= 1) ? printf("Barang ditemukan") :printf("Barang tidak ditemukan");

Sequential Search (Sentinel) untuk kondisi data terurut


IX/XII - 22


Ilustrasi metode Binary Search Terdapat suatu larik A yang sudah terurut, dan akan dicari suatu nilai tertentu pada larik tersebut, misalnya nilai X Langkah pertama : bagi dua larik A, yaitu : Tengah = (Kiri + Kanan)/2 Langkah kedua : bandingkan data yang dicari (misal : X) dengan data larik A[Tengah]

Jika X = A[Tengan], pencarian dihentikan (ketemu). Jika X > A[T], pencarian dilakukan pada posisi sebelah kanan. Ubah nilai Kiri menjadi nilai Tengah (Kiri = Tengah), ulangi langkah pertama sampai data ditemukan Jika X < A[T], pencarian dilakukan pada posisi sebelah kiri. Ubah nilai Kanan menjadi nilai Tengah (Kanan =Tengah), ulangi langkah pertama sampai data ditemukan


IX/XII - 24


4

11/11/2010

Searching (3)

SORTING (PENGURUTAN)

Binary Search

DEFINISI PENGURUTAN

kiri = 0; kanan = NN-1; ketemu = 0; while (kiri < kanan && ketemu == 0) { tengah = (kiri + kanan) / 2; if (Barang[tengah] == Cari) ketemu = 1; else { (Barang[tengah]< Cari) ? kiri = tengah + 1 :kanan = tengah - 1; } } (ketemu == 1) ? printf("Barang ditemukan") :printf("Barang tidak ditemukan"); Jurusan Teknik Informatika

IX/XII - 25


Pengurutan (Sorting) adalah suatu proses untuk mengatur sekumpulan data atau objek menurut susunan atau urutan tertentu. Dibedakan menjadi 2 macam, yaitu : • Pengurutan Internal yaitu pengurutan terhadap sekumpulan data yang disimpan dalam media internal komputer, yang dapat diakses setiap elemennya secara langsung dan disebut juga sebagai pengurutan tabel. • Pengurutan Eksternal, yaitu pengurutan data yang disimpan dalam memori sekunder, biasanya data berukuran besar sehingga tidak mampu untuk dimuat semuanya dalam memori komputer disebut juga pengurutan arsip (file).


Sorting (1)

Tujuan : menyusun nilai/elemen (biasanya dalam array atau file) sedemikian rupa berdasarkan aturan tertentu (ascending/descending ascending/descending)) Jenis

Internal Sorting Selection Sort Bubble Sort Insertion Sort


Maksimum-minimum Sort (Selection Sort) Didasarkan pada pemilihan elemen maksimum atau minimum larik sebagai basis pengurutan. Gagasannya adalah memilih elemen maksimum/minimum tersebut dengan elemen terujung larik (ujung kiri atau ujung kanan). Selanjutnya elemen terujung tersebut di-isolasi dan tidak disertakan pada proses selanjutnya. Proses yang sama diulang untuk elemen larik yang tersisa sampai larik terurut.

Eksternal Sorting


IX/XII - 27


Ilustrasi Pengurutan : Secara Ascending(terurut dari kecil ke besar) 20 20 20 20 20 20


5 5 5 5 30 30


IX/XII - 28


Ilustrasi pengurutan : Secara Descending (terurut dari besar ke kecil)

Maksimum Sort :

65 65 40 30 5 5

IX/XII - 26

30 30 30 40 40 40

85 40 65 65 65 65

IX/XII - 29

40 85 85 85 85 85

data asal langkah 1 langkah 2 langkah 3 langkah 4 langkah 5


65 85 85 85 85 85

20 20 65 65 65 65

5 5 5 40 40 40

30 30 30 30 30 30

85 65 20 20 20 20

40 40 40 5 5 5

data asal langkah 1 langkah 2 langkah 3 langkah 4 langkah 5

dan sebaliknya dapat dilakukan untuk Mimimum Sort [Coba lakukan !]


IX/XII - 30


5

11/11/2010

Sorting (2)

Bubble Sort

Selection Sort menggunakan nilai minimum for(i=0;i

Metode ini menggunakan prinsip pengapungan (diinspirasi oleh gelembung sabun yang berada di atas permukaan air). Elemen larik yang berharga paling kecil “diapungkan”, artinya diangkat keatas (atau ujung kiri larik) melalui proses pertukaran. Proses pengapungan ini dilakukan sampai larik terurut.

IX/XII - 31



Ilustrasi Bubble Sort : 15 15 15 15 1 1 1 1 1 1 1 1 1 1

25 25 25 1 15 15 15 15 2 2 2 2 2 2

2 2 1 25 25 25 25 2 15 15 15 7 7 7

7 1 2 2 2 2 2 25 25 7 7 15 15 15


langkah 1

Bubble Sort

langklah 2

langkah 3 langkah 4 hasil pengurutan

IX/XII - 33



Insertion Sort

Merupakan metode pengurutan dengan cara menyisipkan elemen larik pada posisi yang tepat. Pencarian posisi ini dilakukan secara sequential. Selama pencarian posisi ini, dilakukan pergeseran elemen larik. Insertion Sort : (untuk menghasilkan data terurut dari kecil ke 27 29 27 10 10 10


10 10 29 27 27 21

8 8 8 29 29 27

76 76 76 76 76 29 IX/XII - 35

21 21 21 21 21 76

for(i=0;i=i;j for(j=N 1;j>=i;j---)) { if(Barang[j] < Barang[jBarang[j-1]) { //proses pertukaran Temp = Barang[j]; Barang[j] = Barang[jBarang[j-1]; Barang[j--1] = Temp; Barang[j } } } IX/XII - 34


Sorting (4)

Insertion Sort

Ilustrasi besar) 29 27 10 8 8 8


Sorting (3)

sebelum pengurutan

1 7 7 7 7 7 7 7 7 25 25 25 25 25

IX/XII - 32

data asal langkah 1 langkah 2 langkah 3 langkah 4 langkah 5 Universitas Widyatama


for(i=1;i=0 && Ketemu == 0) { if(Temp < Barang[j]) { Barang[j+1] = Barang[j]; j---;; } else { Ketemu = 1;} } Barang[j+1] = Temp; } IX/XII - 36


6

2010. Sequential Search (Tanpa Variabel Logika) untuk kondisi data tidak terurut

Recommend Documents