Blogger Templates

09 May 2014

ALGORITMA STACK/TUMPUKAN

Stack atau Tumpukan adalah salah satu algoritma dari bahasa pemrograman,. stack atau tumpukan ini sering juga ditemukan dalam kehidupan sehari-hari, contohnya seperti disetiap pelabuhan pelabuhan itu terdapat box box besar yang akan dibawa oleh perahu, box box tersebut ditumpuk terlebih dahulu sebelum akhirnya dibawa, layaknya tumpukan tersebut barang yang akan diangkat terlebih dahulu ya.... pasti yang paling atas.

sama saja seperti Algoritma Stack proses itu disebut dengan LIFO (last in first out),. atau terakhir masuk pertama kali keluar. gambar dibawah ini adalah contoh dari Algoritma Stack LIFO..



push istilah yang digunakan Algoritma Stack untuk menambahkan Elemen, dan Pop digunakan untuk mengurangi atau menghapus Elemen dalam Algortima Stack.

ilustrasi dari algoritma Stack ini bisa didownload disini

http://www.ziddu.com/download/15438972/ilustrasi_stack.swf.html
Read more »
No comments:
Label: , ,

29 March 2014

INSERTION SORT DAN SELECTION SORT

Pengurutan/Sorting adalah satu hal yang sangat penting dalam dunia keinformatikaan. Terutama dalam pengelolaan data. Sering kali, dengan pengurutan, proses pengelolaan data dapat dilakukan dengan lebih mudah dan efisien. Binary Search contohnya, pasti lebih efisien daripada algoritma pencarian biasa yang lebih konvensional. Namun kita dapat melakukan Binary Search jika data yang bersangkutan belum diurut terlebih dahulu.

SELECTION SORT
Algoritma pengurutan sederhana salah satunya adalah Selection Sort. Ide dasarnya adalah melakukan beberapa kali pass untuk melakukan penyeleksian elemen struktur
data. Untuk sorting ascending (menaik), elemen yang paling kecil di antara elemen-elemen yang belum urut,
disimpan indeksnya, kemudian dilakukan pertukaran nilai elemen dengan indeks yang disimpan tersebut dengan elemen yang paling depan yang belum urut. Sebaliknya, untuk sorting descending (menurun), elemen yang paling besar yang disimpan indeksnya kemudian ditukar. Selection Sort diakui karena kesederhanaan
algoritmanya dan performanya lebih bagus daripada algoritma lain yang lebih rumit dalam situasi tertentu.
Algoritma ini bekerja sebagai berikut:
1. Mencari nilai minimum (jika ascending) atau maksimum (jika descending) dalam sebuah list
2. Menukarkan nilai ini dengan elemen pertama list
3. Mengulangi langkah di atas untuk sisa list dengan dimulai pada posisi kedua.
Secara efisien kita membagi list menjadi dua bagian yaitu bagian yang sudah diurutkan, yang didapat dengan membangun dari kiri ke kanan dan dilakukan pada saat awal, dan bagian list yang elemennya akan diurutkan.

INSERTION SORT
Algoritma insertion sort adalah sebuah algoritma sederhana yang cukup efisien untuk mengurutkan sebuah
list yang hampir terurut. Algorima ini juga bisa digunakan sebagai bagian dari algoritma yang lebih canggih. Cara kerja algoritma ini adalah dengan mengambil elemen list satu-per-satu dan memasukkannya di posisi yang benar seperti namanya. Pada array, list yang baru dan elemen sisanya dapat berbagi tempat di array, meskipun cukup rumit. Untuk menghemat memori, implementasinya menggunakan pengurutan di tempat yang membandingkan elemen saat itu dengan elemen sebelumnya yang sudah diurut, lalu menukarnya terus sampai posisinya tepat. Hal ini terus dilakukan sampai tidak ada elemen tersisa di input. Seperti sudah dibahas di bagian pendahuluan, salah satu implementasinya pada kehidupan sehari-hari adalah saat kita mengurutkan kartu remi. Kita ambil kartu satu-per-satu lalu membandingkan dengan kartu sebelumnya untuk mencari posisi yang tepat. Variasi pada umumnya yang dilakukan terhadap array pada insertion sort adalah sebagai berikut :
• Elemen awal di masukkan sembarang, lalu elemen berikutnya dimasukkan di bagian paling akhir.
• Elemen tersebut dibandingkan dengan elemen ke (x-1). Bila belum terurut posisi elemen sebelumnya digeser sekali ke kanan terus sampai elemen yang sedang diproses menemukan posisi yang tepat atau sampai elemen pertama.
• Setiap pergeseran akan mengganti nilai elemen berikutnya, namun hal ini tidak menjadi persoalan sebab elemen berikutnya sudah diproses lebih dahulu.

Soal :
1. Urutkan 10 bilangan berikut dengan insertion sort dan selection sort
Insertion sort
INDEX
0
1
2
3
4
5
6
7
8
9
awal
5
20
3
16
21
8
25
4
50
28
i = 2
5
20
3
16
21
8
25
4
50
28
i = 3
3
5
20
16
21
8
25
4
50
28
i = 4
3
5
16
20
21
8
25
4
50
28
i = 5
3
5
16
20
21
8
25
4
50
28
i = 6
3
5
8
16
20
21
25
4
50
28
i = 7
3
5
8
16
20
21
25
4
50
28
i = 8
3
4
5
8
16
20
21
25
50
28
i = 9
3
4
5
8
16
20
21
25
50
28
i = 10
3
4
5
8
16
20
21
25
28
50

Selection sort
INDEX
0
1
2
3
4
5
6
7
8
9
awal
5
20
3
16
21
8
25
4
50
28
i = 0
3
20
5
16
21
8
25
4
50
28
i = 1
3
4
5
16
21
8
25
20
50
28
i = 2
3
4
5
16
21
8
25
20
50
28
i = 3
3
4
5
8
21
16
25
20
50
28
i = 4
3
4
5
8
16
21
25
20
50
28
i = 5
3
4
5
8
16
20
25
21
50
28
i = 6
3
4
5
8
16
20
21
25
50
28
i = 7
3
4
5
8
16
20
21
     25
50
28
i = 8
3
4
5
8
16
20
21
     25
28
50
akhir
3
4
5
8
16
20
21
     25
28
50

REFERENSI

Negara, Setia B. Tjaru. Kompleksitas Algoritma Pengurutan Selection Sort dan Insertion Sort. BAB 1 dan 2 http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2009-2010/Makalah0910/ MakalahStrukdis0910-074.pdf. Diakses pada tanggal 29 Maret 2014.
No comments:
Label: , ,

15 March 2014

Algoritma Pencarian Linier dan Pencarian Binary

Pencarian (searching) merupakan suatu pekerjaan yang sering dikerjakan dalam kehidupan sehari – hari. Ada kalanya kita mencari sesuatu dengan tujuan hanya untuk mengetahui apakah data tersebut ada dalam sekumpulan data atau tidak, sementara di lain waktu mungkin kita menginginkan posisi dari data yang dicari tersebut. 
Dalam ilmu komputer terdapat bermacam – macam algoritma untuk metoda pencarian (searching). Beberapa metoda pencarian yang pernah dipelajari adalah metoda pencarian linier (Linear / Sequential Search), pencarian biner (Binary Search) dan pencarian interpolasi (Interpolation Search). Masing – masing algoritma memiliki prasyarat dan cara serta waktu pelaksanaan yang berbeda. Pemilihan atas metoda pencarian dilakukan berdasarkan keadaan dan keinginan pengguna metoda yang biasanya tergantung pada jumlah data, jenis data dan struktur data yang digunakan.

PENCARIAN LINIER
Pencarian Linier atau Pencarian Sekuensial (Bah.Ingg: Linear Search atau Sequential Search) adalah pencarian data secara linier (garis lurus), artinya adalah pencarian dilakukan secara teratur (secara sekuensial) dari awal sampai akhir data (atau bisa juga dari akhir ke awal data). Berikut adalah 2 fakta penting tentang pencarian linier:
·         Hanya bagus untuk dipakai pada data yang acak/tak terurut (unsorted)
·         Kompleksitasnya adalah O(n)
Berikut contoh soalnya:

0
1
2
3
4
5
6
7
8
9
10
-2
4
0
1
2
8
13
9
10
11
14

A.      Cari nilai 8 dengan pencarian linier
Jawab : data diurutkan dahulu
0
1
2
3
4
5
6
7
8
9
10
-2
0
1
2
4
8
9
10
11
13
14

8 = -2     (tidak!)
8 = 0       (tidak!)
8 = 1       (tidak!)
8 = 2       (tidak!)
8 = 4       (tidak!)
8 = 8       (ya!) => output : 5 (index)



PENCARIAN BINARY
Pencarian Biner (Bah.Ingg: Binary Search) adalah pencarian data secara eliminasi biner berulang/terus-menerus. Maksudnya adalah pada saat pencarian data, 1 kelompok data yang sudah urut dibagi menjadi 2 subkelompok. Lalu salah satu subkelompok dieliminasi, sehingga ruang lingkup pencarian data menjadi lebih sedikit. Kemudian subkelompok yang tersisa dibagi lagi menjadi 2 subkelompok lagi, demikian dilakukan secara berulang-ulang.
Sebagai contoh, misalnya diinginkan mencari data nama Irawan di sekumpulan data nama yang sudah terurut. Apabila kelompok data ini dibagi 2, ternyata di bagian tengah terdapat nama Leny. Maka subkelompok data sesudah Leny akan dieliminasi, karena tidak mungkin nama Irawan akan terdapat pada data huruf L s/d Z. Sedangkan, subkelompok sebelum Leny, kemudian akan dibagi 2 lagi, dan diperiksa ulang. Ternyata kali ini di bagian tengah terdapat nama Gery. Maka kelompok data sebelum Gery akan dieliminasi, karena tidak mungkin terdapat data Irawan pada huruf A s/d G. Demikian seterusnya terjadi, proses eliminasi ruang lingkup pencarian data menjadi semakin sedikit secara berulang.
Berikut adalah 3 fakta penting mengenai pencarian biner:
·         Hanya bisa berfungsi pada data yang sudah terurut (sorted), ini adalah syarat mutlak dari pencarian biner
·         Merupakan salah satu contoh penerapan cara kerja dari konsep Divide and Conquer
·         Kompleksitasnya adalah O(lg n)
Berikut contoh soalnya:

0
1
2
3
4
5
6
7
8
9
10
-2
4
0
1
2
8
13
9
10
11
14

B.     Cari nilai 13 dengan pencarian binary
A = awal, B = tengah, C = akhir
0
1
2
3
4
5
6
7
8
9
10
-2
0
1
2
4
8
9
10
11
13
14
A
B
C
 13 > 8 awal = tengah + 1
0
1
2
3
4
5
6
7
8
9
10
-2
0
1
2
4
8
9
10
11
13
14
A
B
C
13 > 11 awal = tengah + 1
0
1
2
3
4
5
6
7
8
9
10
-2
0
1
2
4
8
9
10
11
13
14
A=B=C

13 = 13 data ditemukan


REFERENSI
Manurung, Hotler. Perancangan Perangkat Lunak Pencarian Data. BAB 1. http://jurnalcoreit.lppm-stmik.ibbi.ac.id/document/AMIfv95BOaOK8tD_e0XZPo24v_q6z5HZSIWhMVEK_zHbK8nb_EDFd6-8_HT8qJqd1aCabVHS1bqUqiH65qbbwHOolQjLnzncUZaX7qMREbD3X5CevJhhvcx8TQhJGfCRCQJ7vWO495NmcWeENam4EtTR-6ZY4EsCv3T4rljx5C6tEAH6yAwRgto. Diakses pada tanggal 29 Maret 2014

wikibuku. Ayo Membuat Program Pascal/Algoritma Pencarian. http://id.wikibooks.org/wiki/Ayo_Membuat_Program_Pascal/Algoritma_Pencarian. Diakses pada tanggal 29 Maret 2014


No comments:
Label: , ,
Subscribe to: Posts (Atom)