Laporan Praktikum Pert 15 Searching and Sorting

Desember 05, 2016

Laporan Praktikum Pert 15 Searching and Sorting

Laporan Praktikum Pert 15 Searching and Sorting

B.Teori Dasar

SEARCHING AND SORTING

ALGORITHMS

A. Algoritma Searching (Pencarian)

1. Pengantar

Pencarian merupakan tindakan untuk mendapatkan suatu data dalam kumpulan data. Dalam kehidupan sehari-hari, seringkali kita berurusan dengan pencarian; misalnya untuk menemukan nomor telepon seseorang pada buku telepon atau mencari suatu istilah dalam kamus. Pada aplikasi komputer, pencarian kerap dilakukan; misalnya untuk mendapatkan sata dari seseorang mahasiswa, mendapatkan informasi suatu kata dalam kamus digital, mendapatkan nomor telepon berdasarkan suatu alamat atau nama perusahaan.

Untuk keperluan mencari data, terdapat beragam algoritma pencarian (search algorithm). Yang dimaksud dengan algoritma pencarian adalah “algoritma yang menerima sebuah arguman a dan mencoba untuk menemukan sebuah rekaman yang memiliki kunci a” (Tenembaum dan Augensten, 1981, hal. 425). Sebagai contoh, dikehendaki untuk mendapatkan mahasiswa dengan nomor 9834567. Hasilnya adalah rekaman yang berisi data mahasiswa tersebut; yang barangkali berisi nama, alamat, tanggal lahir, dan nama program studi. Dalam implementasi, algoritma bisa jadi memberikan nilai balik berupa sebuah rekaman yang diperoleh, tetapi bisa pula hanya memberikan pointer yang menunjuk ke sebuah rekaman.

Pencarian dapat dilakukan terhadap data yang secara keseluruhan berada dalam memori komputer ataupun terhadap data yang berada dalam penyimpanan eksternal (harddisk). Pencarian yang dilakukan terhadap data yang berada dalam memori komputer dikenal dengan sebutan pencarian internal, sedangkan pencarian yang dilakukan pada media penyimpanan eksternal disebut pencarian eksternal. Pencarian model pertamalah yang dibahas kali ini.

2. Pencarian Sekuensial

Pencarian sekuensial (atau disebut juga pencarian linear) merupakan model pencarian yang paling sederhana yang dilakukan terhadap suatu kumpulan data. Algoritma untuk melakukan hal ini sebenarnya telah diperkenalkan pada pelajaran sebelumnya.

Secara konsep, penjelasannya adalah seperti berikut: Terdapat L yang perupakan larik yang berisi n buah data (L[0], L[1], ..., L[n-1]) dan k adalah data yang hendak dicari. Pencarian dilakukan untuk menemukan

L[i] = k

Dengan i adalah bilangan indeks terkecil yang memenuhi kondisi 0 < k < n-1. Tentu saja ada kemungkinan bahwa data yang dicari tidak ditemukan. Contoh;

L ß [10,9,4,6,4,3,2,5]

Dimanakah posisi 4 yang pertama? Dalam hal ini k adalah 4 dan k ditemukan pada posisi dengan indeks berupa 2.

3. Pencarian terhadap Data Urut

Apabila kumpulan data sudah dalam keadaan urut, pencarian data dengan menggunakan pencarian sekuensial akan memakan waktu yang lama jika jumlah data dalam kumpulan data tersebut sangat banyak. Untuk mengatasi hal itu terdapat algoritma yang dirancang agar pencarian data dapat dilakukan secara efisien. Metode yang digunakan dikenal dengan sebutan pencarian biner (binary search).

Pencarian biner dilakukan dengan membagi larik menjadi dua bagian dengan jumlah yang sama atau berbeda 1 jika jumlah data semula ganjil. Data yang dicari kemudian dibandingkan dengan data terakhir pada bagian pertama. Dalam hal ini ada tiga kemungkinan yang terjadi:

- Data yang dicari sama dengan elemen terakhir pada bagian pertama dalam larik. Jika kondisi ini terpenuhi, data yang dicari berarti ditemukan

- Data yang dicari bernilai kurang dari nilai elemen terakhir pada bagian pertama dalam larik. Pada keadaan ini, pencarian diteruskan pada bagian pertama.

- Data yang dicari bernilai lebih dari nilai elemen terakhir pada bagian pertama dalam larik. Pada keadaan ini, pencarian diteruskan pada bagian kedua.

B. Pengurutan Data (Sorting)

1. Pengantar

Proses pengurutan banyak ditemukan dalam komputer. Hal itu karena data yang sudah urut akan lebih cepat untuk dicari. Untuk membentuk data yang tidak urut, terdapat berbagai algoritma yang bisa digunakan.

Perlu diketahui bahwa pengurutan sendiri dapat dilakukan terhadap data yang secara keseluruhan diletakkan dalam memori ataupun terhadap data yang tersimpan pada pengingat eksternal.

Di dalam pengurutan data terdapat istilah ascending dan descending. Pengurutan dengan dasar nilai yang kecil menuju ke nilai yang besar disebut ascending (urut naik), sedangkan yang disusun atas dasar nilai besar ke kecil disebut descending (urut turun).

2. Metode Buble Sort

Metode ini merupakan metode tersederhana untuk melakukan pengurutan data, tetapi memiliki kinerja yang terburuk untuk data yang besar. Pengurutan dilakukan dengan membandingkan sebuah bilangan dengan seluruh bilangan yang terletak sesudah bilangan tersebut. Penukaran dilakukan suatu kriteria dipenuhi.

3. Metode Pengurutan Seleksi

Pengurutan seleksi (selection sort) mempunyai mekanisme seperti berikut: Mula-mula suatu penunjuk (diberi nama posAwal), yang menunjuk ke lokasi awal pengurutan data, diatur agar berisi indeks pertama dalam larik. Selanjutnya dicari bilangan terkecil yang terletak antara posisi sesudah yang ditunjuk oleh penunjuk tersebut hingga elemen yang terakhir dalam larik. Lokasi bilangan ini ditunjuk oleh posMin. Lalu tukarkan nilai bilangan terkecil tersebut dengan nilai yang ditunjuk oleh posAwal. Proses seperti itu diulang dari posAwal bernilai 0 hingga n-2, dengan n menyatakan jumlah elemen dalam larik.

C.Langkah Kerja
1.Buka aplikasi Dev C++

2.Klik File, New, Source file atau (Ctrl + N)