materi struktur data: Juni 2015

Searching (sequential search dan binarry search)

Searching

Searching adalah pencarian data dengan cara menelusuri data-data tersebut.

Tempat pencarian data dapat berupa array dalam memori, bisa juga pada file

pada external storage.

Sequensial Search

Disebut juga sebagai metode pencarian urut adalah metode pencarian

yang paling mudah.

suatu teknik pencarian data dalam array ( 1 dimensi) yang akan menelusuri

semua elemen-elemen array dari awal sampai akhir, dimana data-data

tidak perlu diurutkan terlebih dahulu.

Ada 2 Kemungkinan dalam Sequensial Search

Kemungkinan terbaik (best case) adalah jika data yang dicari terletak di indeks

array terdepan (elemen array pertama) sehingga waktu yang dibutuhkan untuk

pencarian data sangat sebentar (minimal).

Kemungkinan terburuk (worst case) adalah jika data yang dicari terletak di indeks

array terakhir (elemen array terakhir) sehingga waktu yang dibutuhkan untuk

pencarian data sangat lama (maksimal).

Binary Search

Proses pencarian binary search

hanya dapat dilakukan pada

kumpulan data yang sudah

diurutkan terlebih dahulu.

Prinsip dari Binary Search

1.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.

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

dengan posisi tengah –1.

3.Jika lebih besar, proses dilakukan kembali tetapi posisi awal dianggap sama

dengan posisi tengah +1.

4.Jika data sama, berarti data ditemuka

Kesimpulan

Sequential search lebih efektif jika digunakan pada sekumpulan data yang

sedikit, sedangkan binary search efektif jika digunakan pada sekumpulan data

yang berjumlah banyak.

Sequential search dapat digunakan pada sekumpulan data yang urut ataupun

tidak urut, sedangkan binary search harus pada data yang sudah urut.

SORTING

Suatu proses pengurutan data yang sebelumnya disusun secara acak atau tidak teratur menjadi urut dan teratur menurut suatu aturan tertentu.

Pada umumnya ada 2 macam pengurutan :

1. Pengurutan secara ascending ( urutan naik)

2. Pengurutan secara descending (urutan turun)

Contoh

Data Acak : 5 6 8 1 3 25 10

Ascending : 1 3 5 6 8 10 25

Descending : 25 10 8 6 5 3 1

Selection Sort

1.Merupakan kombinasi antara sorting dan searching

2.Untuk setiap proses, akan dicari elemen elemen yang belum diurutkan yang

memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di

dalam array

3.Selama proses pembandingan dan pengubahan hanya dilakukan pada indeks

pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.

INSERTION SORT

Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan ke tempat yang seharusnya

Pengurutan dimulai dari data ke 2 sampai dengan data terakhir , jika ditemukan data yang lebih kecil, maka akan di tempatkan (diinsert) di posisiyang seharusnya.

Pada penyisipan elemen maka elemen – elemen lain akan bergeser ke belakang

QUEUE/antrean

QUEUE/antrean
Queue Dengan Array

Antrian dapat diartikan sebagai suatu kumpulan data yang seolah – olah terlihat seperti ada data yang diletakkan disebelah data yang lain.

Bersifat FIFO (First In First Out)

Elemen yang pertama masuk ke antrian akan keluar pertama kalinya

DEQUEUE adalah mengeluarkan satu elemen dari suatu Antrian

Contoh :

Penjualan karcis kereta, bioskop

Penjadualan pencetakan (spooling system)

Penjadualan pemakaian CPU

Pemakaian I/O pada sistem komputer

Penyimpan barang di Apotek

Operasi-operasi:

Create()

Untuk menciptakan dan menginisialisasi Queue

Dengan cara membuat Head dan Tail = -1

IsEmpty()

Untuk memeriksa apakah Antrian kosong atau tidak.

Dengan cara memeriksa nilai Tail, jika Tail = -1 maka empty

Kita tidak memeriksa Head, karena Head adalah tanda untuk kepala

antrian (elemen pertama dalam antrian) yang tidak akan berubah-ubah

Pergerakan pada Antrian terjadi dengan penambahan elemen Antrian

kebelakang, yaitu menggunakan nilai Tail

Fungis IsFull

Untuk mengecek apakah Antrian sudah penuh atau belum

Dengan cara mengecek nilai Tail, jika Tail >= MAX-1 (karena MAX-1 adalah

batas elemen array pada C) berarti sudah penuh

Enqueue

Untuk menambahkan elemen ke dalam Antrian, penambahan elemen

selalu ditambahkan di elemen paling belakang

Penambahan elemen selalu menggerakan variabel Tail dengan cara

increment counter Tail terlebih dahulu

Dequeue()

Digunakan untuk menghapus elemen terdepan/pertama (head) dari Antrian

Dengan cara menggeser semua elemen antrian kedepan dan mengurangi Tail dgn 1

Penggeseran dilakukan dengan menggunakan looping

stack

Definisi STACK

•Stack atau tumpukan bisa diartikan sebagai kumpulan data yang seolah – olah diletakkan di atas data yang lain.

•Stack adalah suatu urutan elemen yang elemennya dapat diambil dan ditambah hanya pada posisi akhir (top) saja

•Stact Bersifat LIFO (Last In First Out).

Operasi pada Stack

-IsFull Mengecek apakah STACK sudah penuh

-IsEmpty Mengecek apakah STACK sudah kosong

-Push Menambahkan data pada STACK pada tumpukan paling atas

-Pop mengambil data pada STACK pada tumpukan paling atas

-Print mencetak semua data dalam tumpukan

Fungsi Push

Untuk memasukkan elemen ke stack, selalu menjadi elemen teratas stack.

Tambah satu (increment) nilai top of stack terlebih dahulu setiap kali ada

penambahan elemen stack, asalkan stack masih belum penuh, kemudian isikan

nilai baru ke stack berdasarkan indeks top of stack setelah ditambah satu

(diincrement).

Seperti gambar di berikut ini.

Fungsi Pop

Untuk mengambil elemen teratas dari stack. Ambil dahulu nilai elemen teratas stack dengan mengakses top of stack, tampilkan nilai yang akan diambil terlebih dahulu, baru didecrement nilai top of stack sehingga jumlah elemen stack berkurang.