LAPORAN 5 PBO

Laporan  15

Algoritma dan pemograman

TEKNIK ELEKTRONIKA

LAPORAN PRAKTIKUM : 15

Disusun Oleh :

Muhammad Hidayat Saputra

17214033

Dosen Pembimbing :

Sri Nofri Wihandri ,S.Pd,M.Pd.T

Akademi Komunitas Negeri Padang Pariaman

PDDF Universitas Negeri Padang

Tahun 2017

SEARCHING AND SORTING ALGORITHMS

1.      Pengantar

Pencarian merupakan tindakan untuk mendapatkan suatu data dalam kumpulan dataUntuk 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 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.

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

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.

Contoh-contoh program :

1)      Program mengurutkan angka yang diinputkan , kemudian mencari angka yang diinginkan.

#include<stdio.h>

#include<stdio.h>

#define MAX 20

Int intcmp (cont void *v1, const void *v2);

Main ()

{

            Int arr [MAX], count, key, *ptr;

 Printf(“Enter %d integer values; press Enter after each.”)

For(count = 0; count < MAX; count++)

            Scanf (“%d”, &arr[count] );

Puts (“Press a key to sort the values.”);

Getch ();

Qsort (arr, MAX, sizeof(arr[0]), intcmp);

For (count = 0; count, < MAX; count++)

            Printf (“\narr[%d] = %d.”, count, arr[count] );

Puts(“\nPress a key to continue.”);

Getch ();

Printf(“Enter a value to search for: “);

Scanf(“%d”, &key);

Ptr = (int *) bsearch(&key, arr, MAX, sizeof(arr[0]), intcmp);

If ( ptr != NULL )

            Printf(“&d found a arr[%d].”, key, (ptr – arr));

Else

            Printf(“%d not found.”, key);

}