Pencarian

Pencarian Sekuensial

“Sequential search atau Pencarian sekuensial” bisa disebut dengan pencarian linear yang merupakan model pencarian yang paling simpel dan sederhana banget deh yang dapat dilakukan terhadap suatu kumpulan data. Suatu tekhnik pencarian dalam array (1 dimensi) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu. Keunggulan dari pencarian sekuensial ini adalah jika data yang dicari terletak di indeks array terdepan maka waktu dalam pencarian nya sangat cepat, dalam artian waktu yang minim sekali. Keburukannya adalah kalau jika data indeks array nya yang dicari paling belakang, maka waktu yang dicari tuh lama banget (maksimal). Algoritmanya juga sederhana.Selain itu, sumber data tidak perlu diurut terlebih dahulu sebelum dilakukan pencarian. Namun ada juga kekurangannya, yaitu jika data yang dicari berada pada baris paling akhir, maka waktu pencariannya akan cukup lama. Selain itu beban komputasi akan meningkat jika dilakukan pencarian pada sumber data yang cukup banyak.

Pencarian Biner

Sebuah algoritma pencarian biner (atau pemilahan biner) adalah sebuah teknik untuk menemukan nilai tertentu dalam sebuah larik (array) linear, dengan menghilangkan setengah data pada setiap langkah, dipakai secara luas tetapi tidak secara ekslusif dalam ilmu komputer. Sebuah pencarian biner mencari nilai tengah (median), melakukan sebuah pembandingan untuk menentukan apakah nilai yang dicari ada sebelum atau sesudahnya, kemudian mencari setengah sisanya dengan cara yang sama. Sebuah pencarian biner adalah salah satu contoh dari algoritma divide and conquer (atau lebih khusus algoritma decrease and conquer) dan sebuah pencarian dikotomi (lebih rinci di Algoritma pencarian).

Pencarian Biner (Binary Search) dilakukan untuk :

- memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya.

- Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan).

- Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.

Referensi :

http://askopan1003.blogspot.com

http://id.wikipedia.org/wiki/Pencarian_biner

Pengurutan

Metode Penyisipan Langsung
Proses pengurutan dengan metode penyisipan langsung dapat dijelaskan sebagai berikut :
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 sebelah kiri, maka ambil kartu tersebut dan sisipkan di tempat yang sesuai.

Metode penyisipan langsung dapat dibagi menjadi 2 bagian
– Bagian sebelah kiri data sudah terurut (tujuan)
– Bagian sebelah kanan data belum terurut (sumber)

Langkah-langkah :
1 : Baca array elemen yang akan diurutkan (n)
2 : Kerjakan langkah 3 sampai langkah 6 untuk i : 1 s/d n-1
3 : Tentukan elemen yang akan disisipkan (Temp = A [i] ; j = i-1;)
4 : Kerjakan langkah 5 selama temp (A [j] dan j >= 0;
5 : A [j+1]= A[j] ; j =j-1;
6 : Tempatkan elemen A [j+1] = Temp;
7 : Selesai

Metode Penyisipan Biner
Metode pengurutan dengan algoritma penyisipan biner (binary insertion sort) memperbaiki metode pengurutan dengan algoritma penyisipan langsung dengan melakukan proses perbandingan yang lebih sedikit sehingga proses pengurutan lebih cepat. Metode penyisipan biner melakukan proses perbandingan dengan membagi dua bagian data dari posisi 0 sampai dengani-1 yang disebut dengan bagian kiri dan kanan. Apabila data pada posisi kei berada pada jangkauan kiri maka proses perbandingan dilakukan hanya pada bagian kiri dan menggeser posisi sampai.

Metode Seleksi
Masukkan dinyatakan sebagai vektor misal vektor A (belum terurut), dan N (missal banyak elemen yang akan diurutkan). Keluaran adalah vektor A yang telah terurut.
Algoritma metode seleksi :
- langkah 0 : Baca vektor yang akan diurutkan (dalam program utama)
- langkah 1 : Kerjakan langkah 2 sampai 4 untuk i = 1 sampai N -1
- langkah 2 : Tentukan awal = i , kerjakan langkah 3 untuk j = i +1 sampai N
- langkah 3 : (Mencari data terkecil)
Tes : apakah A[awal] > A[j], jika ya maka ubah awal = j
- langkah 4 : Tukarkan nilai A[awal] dengan A[i]
- langkah 5 : selesai

Metode Shell
Metode ini dikembangkan oleh Donald L. Shell pada tahun 1959. Dalam metode ini jarak antara dua elemen yang dibandingkan dan ditukarkan tertentu. Secara singkat metode ini dijelaskan sebagai berikut. Pada langkah pertama, kita ambil elemen pertama dan kita bandingkan dengan elemen pada jarak tertentu dari elemen pertama tersebut. Kemudian elemen kedua kita bandingkan dengan elemen lain dengan jarak yang sama seperti diatas. Demikian seterusnya sampai seluruh elemen dibandingkan. Pada langkah kedua proses diulang dengan langkah yang lebih kecil, pada langkah ketiga jarak tersebut diperkecil lagi seluruh proses dihentikan jika jarak sudah sama dengan satu.

Referensi :
http://andika-thedarknight.blogspot.com/2008/10/metode-penyisipan-langsung-straight.html
http://www.scribd.com/doc/17512096/Praktikum-Struktur-Data-7
http://www.kurakuralincah.co.cc

Algoritma Layer by Layer pada Rubik

Algoritma Layer-by-Layer

Rubik’s Cube ditemukan oleh Erno Rubik dan telah dipatenkan atas namanya [5]. Benda ini sekilas terlihat sebagai sebuah kubus yang terdiri atas 27 kubus kecil, padahal sebenarnya hanya terdapat 26 kubus kecil karena kubus kecil yang paling dalam tidak pernah tersentuh. Cara memainkan kubus ini adalah dengan mengacak sisisisinya lalu mengembalikannya ke keadaan tersusun, di mana keenam sisinya memiliki warna yang uniform. Hingga saat ini, banyak orang yang menganggap bahwa Rubik’s Cube hanya dapat diselesaikan oleh orang-orang yang memiliki IQ tinggi, padahal sudah banyak algoritm yang ditemukan untuk menyelesaikan Rubik’s Cube, sehingga siapa pun dapat menyelesaikannya. Salah satu algoritma yang termudah adalah algoritma Layer-by-Layer
yang menyelesaikan Rubik’s Cube mulai layer pertama, kedua, lalu ketiga. Selain itu, ada juga algoritma Fridrich yang memerlukan sekitar 120 algoritma untuk dihapal namun dapat menyelesaikan Rubik’s Cube dalam rata-rata 50 gerakan. Karena solusi Rubik’s Cube telah ditemukan dalam bentuk algoritma, maka program komputer untuk menyelesaikannya pun dapat dibuat. Makalah ini membahas bagaimana cara membuat program komputer yang mengimplementasikan algoritma Layer-by-Layer
untuk menyelesaikan Rubik’s Cube.

Secara garis besar, algoritma Layer-by-Layer dapat ditulis sebagai berikut :
1. Selesaikan layer pertama/atas.
a. Bentuk cross di sisi atas, sesuaikan dengan warna keempat sisi di samping.
b. Isi keempat sudut atas dengan kubus yang sesuai.
2. Selesaikan layer kedua/tengah.
a. Isi keempat kubus pada layer kedua dengan kubus yang sesuai.
3. Selesaikan layer ketiga/bawah.
a. Bentuk cross di sisi bawah, tanpa merusak kedua layer di atas.
b. Tempatkan keempat sudut bawah di tempat sebenarnya, disesuaikan dengan warna dari ketiga sisi yang bersisian dengannya.
c. Bentuk supaya sisi bawah memiliki warna yang uniform.
d. Pertukarkan kubus-kubus yang belum sesuai pada tempatnya


Referensi :
http://www.informatika.org/

Rekursi

Rekursi adalah konsep pengulangan yang penting dalam ilmu komputer. Konsep ini dapat digunakan untuk merumuskan solusi sederhana dalam sebuah permasalahan yang sulit untuk diselesaikan secara iteratif dengan menggunakan loop for, while do. Pada saat tertentu konsep ini dapat digunakan untuk mendefinisikan permasalahan dengan konsisten dan sederhana. Pada saat yang lain, rekursi dapat membantu untuk mengekspresikan algoritma dalam sebuah rumusan yang menjadikan tampilan algoritma tersebut mudah untuk dianalisa.
Rekursi adalah cara untuk menetapkan proses dengan dirinya sendiri. Lebih jelasnya (dan untuk menghalaukan penampilan kesirkularan dalam definisi), langkah-langkah "rumit" dari proses dijelaskan dengan langkah-langkah yang lebih "sederhana", dan kejadian yang paling "sederhana" diberi secara gamblang. Dalam bahasa pemrograman, rekursi berarti memanggil suatu fungsi dari dalam fungsi itu sendiri.
Rekursi merupakan teknik pemrograman yang menyebabkan suatu fungsi/prosedur memanggil dirinya sendiri. Pemanggilan diri sendiri ini berlangsung terus menerus sampai batas terkecil yang nilai dari fungsi tersebut disebutkan secara eksplisit. Salah satu contoh dari penerapan rekursi adalah perhitungan faktorial.

Referensi :
http://bc-omu.blogspot.com/

Subrutin

Prosedur
Prosedur adalah suatu program terpisah dalam blok sendiri yang berfungsi sebagai subprogram (program bagian). Prosedur diawali dengan kata cadangan Procedure di dalam bagian deklarasi prosedur. Prosedur dipanggil dan digunakan di dalam blok program yang lainnya dengan menyebutkan judul prosedurnya.
Prosedur banyak digunakan pada program yang terstruktur, karena:
1.Merupakan penerapan konsep program modular, yaitu memecah-mecah program yang rumit menjadi program-program bagian yang lebih sederhana dalam bentuk prosedur-prosedur.
2.Untuk hal-hal yang sering dilakukan berulang-ulang, cukup diruliskan sekali saja dalam prosedur dan dapat dipanggil atau dipergunakan sewaktu-waltu bila diperlukan.

Fungsi
Fungsi hampir sama dengan prosedur, hanya fungsi harus dideklarasikan dengan tipenya. Tipe deklarasi ini menunjukkan tipe hasil dari fungsi. Tipe tersebut ditulis pada akhir deklarasi fungsi yang didahului dengan titik koma.

Referensi :
http://buyungwisnuadjie.files.wordpress.com

Struktur Pengulangan

For
Dalam bahasa pemrograman C++ untuk melakukan perulangan (looping) yang paling umum digunakan adalah pernyataan For. Pernyataan For berguna untuk melakukan perulangan (looping) terhadap satu atau sejumlah pernyataan.

For Bersarang
Kita juga bisa menuliskan pernyataan for di dalam penyataan for. Kontruksi semacam ini sering disebut dengan penyataan for bersarang. Perhatikan contoh berikut:

for x := 1 to 3 do
for y :=1 to 2 do
writeln (x, ‘ ‘ y);

Looping for yang luar (dengan pencacah variabel x) akan menjalankan looping yang dalam (dengan pencacah y) sebanyak 3 kali. Dan pada setiap pengulangan di layar akan dituliskan nilai x dan y. Berikut ini adalah keluaran dari program di atas:
1 1
1 2
2 1
2 2
3 1
3 2
Pada saat x bernilai 1, y diulang sebanyak 2 kali. Jadi pada layar akan tertulis 1 1 dan 1 2. Demikian juga pada saat x bernilai 2, y diulang sebanyak 2 kali. Jadi pada layar akan tertulis 2 1 dan 2 2. Hal yang sama terjadi pada saat x bernilai 3, y diulang sebanyak 2 kali. Sehingga pada layar tertulis 3 1 dan 3 2.

While
Perulangan while memiliki bentuk

while (suatu_kondisi)
perintah

perintah bisa juga berupa blok yang berisi kumpulan perintah-perintah di antara { dan }. perintah ini disebut juga dengan inti perulangan. Inti perulangan akan terus dieksekusi selama suatu_kondisi bernilai true. suatu_kondisi ini disebut juga penguji perulangan.

Repeat – Until
Pernyataan pengulangan ini hampir sama denganpernyataan pengulangan while, dan biasanya digunakanbila jumlah pengulangan belum dapat ditentukan padasaat program ditulis. Perbedaan pernyataan repeat..until dan while terletak pada letak pengecekan kondisi. Jika pada pernyataan while, kondisi dicek pada awal kalang, sedangkan pada pernyataan repeat..until, kondisi dicek pada akhir kalang. Perbedaan yang lain, bila pernyataan while mengulang pernyataan selama kondisi masih terpenuhi, pernyataan repeat..until mengulang pernyataan selam kondisi belum terpenuhi.

Referensi :
http://softekno.blogspot.com/
http://latifrudianto.blogspot.com/

Struktur Percabangan

If…Else

Pernyataan if-else mempunyai sintaks:
if (kondisi)
pernyataan-1
else
pernyataan-2;

Maksud dari pernyataan if-else adalah:
Jika kondisi benar, maka pernyataan-1 dijalankan, Sedangkan jika kondisi bernilai salah, maka pernyataan-2 yang akan dijalankan. Masing-masing pernyataan-1 dan pernyataan-2 dapat berupa sebuah pernyataan tunggal maupun pernyataan majemuk. If… Else berfungsi melibatkan pernyataan majemuk yaitu pernyataan A dan B. Jika pernyataan bukan merupakan pernyataan A, maka yang akan dijalankan merupakan pernyataan B.

If…Else If
Pernyataan untuk if else if hamper sama dengan if else namun disini hanya menambahkan suatu kondisi lagi setelah kondisi yang pertama yaitu pada if pertama

Case
Hampir sama dengan struktur percabangan IF, tetapi lebih cocok digunakan jika kondisi yang diperiksa sangat banyak. Kondisi yang diperiksa harus berupa data ordinal (bertipe integer atau char), dan tidak boleh bertipe real. Menggunakan operator relasional = (sama dengan) untuk melakukan pemeriksaan kondisi.

Referensi :
http://zenkychan.blogspot.com/