Struktur Data

Dalam kehidupan sehari-hari sebenarnya kita sering melakukan pencarian data.

Sebagai contoh, jika kita menggunakan Kamus untuk mencari kata-kata dalam Bahasa

Inggris yang belum diketahui terjemahannya dalam Bahasa Indonesia. Contoh lain saat

kita menggunakan buku telepon untuk mencari nomor telepon teman atau kenalan dan

masih banyak contoh yang lain.

Pencarian data sering juga disebut table look-up atau storage and retrieval

information adalah suatu proses untuk mengumpulkan sejumlah informasi di dalam

pengingat komputer dan kemudian mencari kembali informasi yang diperlukan secepat

mungkin.

Algoritma pencarian (searching algorithm) adalah algoritma yang menerima

sebuah argumen kunci dan dengan langkah-langkah tertentu akan mencari rekaman

dengan kunci tersebut. Setelah proses pencarian dilaksanakan, akan diperoleh salah

satu dari dua kemungkinan, yaitu data yang dicari ditemukan (successful) atau tidak

ditemukan (unsuccessful).

Metode pencarian data dapat dilakukan dengan dua cara yaitu pencarian internal

(internal searching) dan pencarian eksternal (external searching). Pada pencarian

internal, semua rekaman yang diketahui berada dalam pengingat komputer sedangakan

pada pencarian eksternal, tidak semua rekaman yang diketahui berada dalam pengingat

komputer, tetapi ada sejumlah rekaman yang tersimpan dalam penyimpan luar misalnya

pita atau cakram magnetis.

Selain itu metode pencarian data juga dapat dikelompokka menjadi pencarian

statis (static searching) dan pencarian dinamis (dynamic searching). Pada pencarian

statis, banyaknya rekaman yang diketahui dianggap tetap, pada pencarian dinamis,

banyaknya rekaman yang diketahui bisa berubah-ubah yang disebabkan oleh

penambahan atau penghapusan suatu rekaman.

Ada dua macam teknik pencarian yaitu pencarian sekuensial dan pencarian biner.

Perbedaan dari dua teknik ini terletak pada keadaan data. Pencarian sekuensial

digunakan apabila data dalam keadaan acak atau tidak terurut. Sebaliknya, pencarian

biner digunakan pada data yang sudah dalam keadaan urut.

Pencarian Berurutan (Sequential Searching)

Pencarian berurutan sering disebut pencarian linear merupakan metode pencarian

yang paling sederhana. Pencarian berurutan menggunakan prinsip sebagai berikut : data

yang ada dibandingkan satu per satu secara berurutan dengan yang dicari sampai data

tersebut ditemukan atau tidak ditemukan.

Pada dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai

dengan jumlah data. Pada setiap pengulangan, dibandingkan data ke-i dengan yang

dicari. Apabila sama, berarti data telah ditemukan. Sebaliknya apabila sampai akhir

pengulangan tidak ada data yang sama, berarti data tidak ada. Pada kasus yang paling

buruk, untuk N elemen data harus dilakukan pencarian sebanyak N kali pula.

Algoritma pencarian berurutan dapat dituliskan sebagai berikut :

1 i ← 0

2 ketemu ← false

3 Selama (tidak ketemu) dan (i <= N) kerjakan baris 4

4 Jika (Data[i] = x) maka ketemu ← true, jika tidak i ← i + 1

5 Jika (ketemu) maka i adalah indeks dari data yang dicari, jika tidak data tidak

ditemukan

Di bawah ini merupakan fungsi untuk mencari data menggunakan pencarian

sekuensial.

int SequentialSearch(int x)

{

int i = 0;

bool ketemu = false;

while ((!ketemu) && (i < Max)){

if(Data[i] == x)

ketemu = true;

else

i++;

}

if(ketemu)

return i;

else

return -1;

}

Program 8.1 Fungsi untuk Mencari Data dengan Metode Sekuensial

Fungsi diatas akan mengembalikan indeks dari data yang dicari. Apabila data

tidak ditemukan maka fungsi diatas akan mengembalikan nilai –1.

Pencarian Biner (Binary Search)

Salah satu syarat agar pencarian biner dapat dilakukan adalah data sudah dalam

keadaan urut. Dengan kata lain, apabila data belum dalam keadaan urut, pencarian biner

tidak dapat dilakukan. Dalam kehidupan sehari-hari, sebenarnya kita juga sering

menggunakan pencarian biner. Misalnya saat ingin mencari suatu kata dalam kamus

Prinsip dari pencarian biner dapat dijelaskan sebagai berikut : mula-mula diambil

posisi awal 0 dan posisi akhir = N - 1, kemudian dicari posisi data tengah dengan rumus

(posisi awal + posisi akhir) / 2. Kemudian data yang dicari dibandingkan dengan data

tengah. Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama

dengan posisi tengah –1. Jika lebih besar, porses dilakukan kembali tetapi posisi awal

dianggap sama dengan posisi tengah + 1. Demikian seterusnya sampai data tengah

sama dengan yang dicari.

Untuk lebih jelasnya perhatikan contoh berikut. Misalnya ingin mencari data 17

pada sekumpulan data berikut :

Contoh:

Coding Program Binary Search

Data: 11 13 15 18 23 27 29 31 54 58 59 61

Data yang akandicari : 13

Interelasi/ Urutan proses:

Proses 1

11 13 15 18 23 27 29 31 54 58 59 61 lebihbesardengan data ygakandicari ,lakukanpembagian data

Proses 2

11 13 15 18 23 27 lebihbesardari data yang dicari, bagi 2 29 31 54 58 59 61

Proses 3

11 13 15 lebihbesardari data yang dicari, bagi 2 18 23 27 29 31 54 58 59 61

Proses 4

11 lebihkecildari data yang dicari, abaikansaja 13 15 lebihbesardari data yang dicari, bagi 2 18 23 27 29 31 54 58 59 61

Proses 5

1113sesuai data yang dicari15 lebihbesardari data yang dicari18 23 27 29 31 54 58 59 61

Dari proses diatasdapatdisimpulkanbahwa binary search akanmembagi-bagisekumpulan data menjadi 2 bagiansampai data yang dicariditemukan.

Sorting adalah proses menyusun elemen – elemen dengan tata urut tertentu dan proses tersebut terimplementasi dalam bermacam aplikasi. Kita ambil contoh pada aplikasi perbankan. Aplikasi tersebut mampu menampilkan daftar account yang aktif.

Hampir seluruh pengguna pada sistem akan memilih tampilan daftar berurutan secara ascending demi kenyamanan dalam penelusuran data.

Beberapa macam algoritma sorting telah dibuat karena proses tersebut sangat mendasar dan sering digunakan. Oleh karena itu, pemahaman atas algoritma – algoritma yang ada sangatlah berguna.

1. Selection Sort (Ascending):
Pengurutan dilakukan dengan memilih elemen terbesar dan menempatkan pada posisinya,
kemudian mencari element terbesar berikutnya dan menempatkan pada tempatnya, dan
seterusnya.

Proses pengurutan dengan menggunakan metode selection sort secara terurut naik adalah :
1. Mencari data terkecil dari data pertama sampai data terakhir, kemunian di tukar posisinya dengan data pertama.
2. mencari data terkecil dari data kedua sampai data terakhir, kemudian di tukar dengan posisinya dengan data kedua.
3. mencari data terkecil dari data ketiga sampai data terakhir, kemudian di tukar posisinya dengan data ketiga
4. dan seterusnya sampai semua data turut naik. apabila terdapat n buah data yang akan di urutkan, maka membutukan (n - 1) langkah pengurutan, dimana data terakhir yaitu data ke-n tidak perlu di urutkan karena hanya tinggal satu satunya.

Contoh:

2. Bubble Sort
Konsep Buble Sort
Metode pengurutan gelembung (Bubble Sort) diinspirasikan oleh gelembung sabun yang berada dipermukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung ke atas permukaan. Prinsip di atas dipakai pada pengurutan gelembung.

Bubble sort (metode gelembung) adalah metode/algoritma pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat

contoh kasus bubble sort

3. Metode Penyisipan Langsung (Straight Insertion Sort) / Insertion sort
Ilustrasi :
Data dicek satu per satu mulai dari yang kedua sampai dengan yang terakhir. Apabila
ditemukan data yang lebih kecil daripada data sebelumnya, maka data tersebut disisipkan
pada posisi yang sesuai. Akan lebih mudah apabila membayangkan pengurutan kartu.
Pertama-tama anda meletakkan kartu-kartu tersebut di atas meja, kemudian melihatnya
dari kiri ke kanan. Apabila kartu di sebelah kanan lebih kecil daripada kartu di sebelahkiri, maka ambil kartu tersebut dan sisipkan di tempat yang sesuai.

Contoh:

4.Metode Penggabungan (Merge Sort)
Metode penggabungan biasanya digunakan pada pengurutan berkas. Prinsip dari
metode penggabungan sebagai berikut : mula-mula diberikan dua kumpulan data yang
sudah dalam keadaan urut. Kedua kumpulan data tersebut harus dijadikan satu table
sehingga dalam keadaan urut.

Contoh:

5.Quick Sort
Algoritma sortir yang efisien yang ditulis oleh C.A.R. Hoare pada 1962. Dasar strateginya adalah “memecah dan menguasai”. Quicksort dimulai dengan menscan daftar yang disortir untuk nilai median. Nilai ini, yang disebut tumpuan (pivot), kemudian dipindahkan ke satu sisi pada daftar dan butir-butir yang nilainya lebih besar dari tumpuan di pindahkan ke sisi lain.

Contoh

6. Metode Shell (Shell Sort)
Metode ini disebut juga dengan metode pertambahan menurun (diminishing
increment). Metode ini dikembangkan oleh Donald L. Shell pada tahun 1959, sehingga
sering disebut dengan Metode Shell Sort. Metode ini mengurutkan data dengan cara
membandingkan suatu data dengan data lain yang memiliki jarak tertentu, kemudian
dilakukan penukaran bila diperlukan

Contoh: