Algoritma Pada Pemrograman Java

Posted by : smkn1blitar Sabtu, 10 Januari 2015

Algoritma JAVA

A. Algoritma Sorting

Pengertian Algoritma Sorting adalah kumpulan langkah sistematis atau secara berutan untuk memperoleh hasil yang diinginkan. Salah satu contoh dari algoritma untuk langkah ini adalah Sorting (pengurutan). Sorting dapat didefinisikan sebagai pengurutan sejumlah data berdasarkan nilai tertentu. Pengurutan dapat dilakukan dari nilai terkecil ke nilai terbesar (ascending) atau sebaliknya. Sorting dapat dibedakan menjadi dua yaitu Comparasion Sort (Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort) dan Non-Comparasion Sort (Radix Sort, Counting Sort). Comparasion Sort / penggurutan dengan pembandingan adalah algoritma yang dalam proses pengurutannya melakukan pembandingan antar data. Non-Comparasion Sort / pengurutan tanpa pembandingan adalah algoritma pengurutan dimana dalam prosesnya tidak melakukan perbandingan antar data.

1. Metode Counting sort

Adalah sebuah algoritma sorting linear yang digunakan untuk mengurutkan ‘item’ ketika urutannya telah ditentukan dan memiliki panjang yang terbatas. Bilangan interval yang telah tetap, katakana k1 ke k2 adalah contoh dari ‘item’ tersebut. Counting sort sebenarnya merupakan metode pengurutan yang memanfaatkan index variabel array. Hanya effektif pada data yang nilainya kecil.

Algoritma ini diproses dengan mendefinisikan sebuah hubungan urutan antara ‘item’ yang akan disorting. Katakana ‘item’ yang akan disorting adalah variable A. Maka, terdapat sebuah array tambahan dengan ukuran yang serupa dengan array A. katakana array tersebut adalah array B. untuk setiap element di A, sebut e, algoritma ini menyimpan jumlah ‘item’ di A lebih kecil dari atau sama dengan e di B(e). jika hasil sorting yang terakhir disimpan di array C, maka untuk masing-masing e di A, dibuat dalam arah yang sebaliknya, yaitu C[B(e)]=e. setelah step di atas, niali dari B(e) berkurang dengan 1.

Algoritma ini membuat 2 passover A dan passover B. Jika ukuran dari range k lebih kecil dari ukuran input n, maka time complexity = O(n). perhatikan juga bahwa algoritma ini stabil yang berarti bahwa sambungan diselesaikan dengan langsung mengabarkan element-element yang muncul pertama kali.

Adapun syarat algoritma ini berjalan dengan baik ialah:

Data harus bilangan bulat yang bernilai lebih besar atau sama dengan nol
Range data diketahui

Ada 3 macam array yang terlibat:

Array untuk mengisi bilangan yang belum diurutkan.
Array untuk mengisi frekuensi bilangan itu, sekaligus sebagai penghitung kejadian.
Array untuk mengisi bilangan yang sudah diurutkan.

Algoritmanya :

countingsort(A[], B[], min, max, n)
for i = min to max do
C[i] = 0
for j = 1 to n do C[A[j]] = C[A[j]] + 1
for i = min + 1 to max do
C[i] = C[i] + C[i-1]

for j = n downto 1 do
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j]] – 1

Gambar 3.3 Diagram Counting Sort

B. Algoritma Searching

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 dan pencarian eksternal . (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.

1. Linear Search

Linear Search adalah algoritma pencarian yang paling sederhana. Linear Search bekerja dengan membandingkan nilai yang dicari dengan setiap element pada array ( pada umumnya ) secara sequen. Berikut ini implementasi algoritma linear search pada bahasa pemrograman Java yang terdiri dari 2 file .java, nama file : LinearGenerator.java

package linearsearch;
import java.util.Random;

/**
*
* @author Taeyeon
*/
public class LinearGenerator {
private int [] data;
static private Random randomValue = new Random();
public LinearGenerator(int sizeArray)
{
data = new int [ sizeArray];
for(int i=0;i<sizeArray;i++)
{
data[i]= 1 + randomValue.nextInt(125);
}
}
public int linearSearch(int searchKey)
{
for(int index=0; index < data.length; index++)
if(data[index]== searchKey)
return index;
return -1;
}
@Override
public String toString()
{
StringBuffer temp = new StringBuffer();
for(int element:data)
temp.append(element + " ");
temp.append("\n");
return temp.toString();
}
}

Nama file : Main.java
package linearsearch;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
/**
*
* @author Taeyeon
*/
public class Main {

/**
* @param args the command line arguments
*/
public static void main(String[] args) throws IOException {
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

int searchKey;
int position;
int arrayLength;
arrayLength = 25;
LinearGenerator searchArray = new LinearGenerator(arrayLength);
System.out.println(searchArray);

System.out.println("Masukkan nilai yang akan dicari:");
searchKey = Integer.parseInt(input.readLine());

while (searchKey != -1)
{
position = searchArray.linearSearch(searchKey);

if(position == -1)
System.out.println("Nilai tidak ditemukan");
else
System.out.println("Nilai "+searchKey+" ditemukan di index "+(position+1));

System.out.println("input -1 untuk keluar");
searchKey = Integer.parseInt(input.readLine());
}
}

}

Contoh keluar program :

2. 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 :

3	9	11	12	15	17	20	23	31	35

awal				tengah					akhir

Mula-mula dicari data tengah, dengan rumus (0 + 9) / 2 = 4. Berarti data tengah adalah data ke-4, yaitu 15. Data yang dicari, yaitu 17, dibandingkan dengan data tengah 81 ini. Karena 17 > 15, berarti proses dilanjutkan tetapi kali ini posisi awal dianggap sama dengan posisi tengah + 1 atau 5.

3	9	11	12	15	17	20	23	31	35

					awal		tengah		akhir

Data tengah yang baru didapat dengan rumus (5 + 9) / 2 = 7. Berarti data tengah yang baru adalah data ke-7, yaitu 23. Data yang dicari yaitu 17 dibandingkan dengan data tenah ini. Karena 17 < 23, berarti proses dilanjukkan tetapi kali ini posisi akhir dianggap sama dengan posisi tengah – 1 atau 6.

3	9	11	12	15	17	20	23	31	35

awal = tengah akhir

Data tengah yang baru didapat dengan rumus (5 + 6) / 2 = 5. Berarti data tengah yang baru adalah data ke-5, yaitu 17. data yang dicari dibandingkan dengan data tengah ini dan ternyata sama. Jadi data ditemukan pada indeks ke-5. Pencarian biner ini akan berakhir jika data ditemukan atau posisi awal lebih besar daripada posisi akhir. Jika posisi sudah lebih besar daripada posisi akhir berarti data tidak ditemukan. Untuk lebih jelasnya perhatikan contoh pencarian data 16 pada data diatas. Prosesnya hampir sama dengan pencarian data 17. Tetapi setelah posisi awal 5 dan posisi akhir 6, data tidak ditemukan dan 16 < 17, maka posisi akhir menjadi posisi tengah – 1 atau = 4 sedangkan posisi awal = 5.

3	9	11	12	15	17	20	23	31	35

akhir awal

Disini dapat dilihat bahwa posisi awal lebih besar daripada posisi akhir, yang artinya data tidak ditemukan.

Algoritma pencarian biner dapat dituliskan sebagai berikut :

1. L ← 0

2. R ← N - 1

3. ketemu ← false

4. Selama (L <= R) dan (tidak ketemu) kerjakan baris 5 sampai dengan 8

5. m ← (L + R) / 2

8. 2

6. Jika (Data[m] = x) maka ketemu ← true

7. Jika (x < Data[m]) maka R ← m – 1

8. Jika (x > Data[m]) maka L ← m + 1

9. Jika (ketemu) maka m adalah indeks dari data yang dicari, jika tidak data tidak ditemukan

Di bawah ini merupakan fungsi untuk mencari data menggunakan pencarian biner.

int BinarySearch(int x)

{

int L = 0, R = Max-1, m; bool ketemu = false;

while((L <= R) && (!ketemu))

{

m = (L + R) / 2; if(Data[m] == x) ketemu = true;

else if (x < data[m]) R = m - 1;

else

L = m + 1;

}

if(ketemu) return m;

else

return -1;

}

Fungsi Pencarian Data dengan Metode Biner

Fungsi diatas akan mengembalikan indeks dari data yang dicari. Apabila data tidak ditemukan maka fungsi diatas akan mengembalikan nilai –1. Jumlah pembandingan minimum pada pencarian biner adalah 1 kali, yaitu apabila data yang dicari tepat berada di tengah-tengah. Jumlah pembandingan maksimum yang dilakukan dengan pencarian biner dapat dicari menggunakan rumus logaritma, yaitu : C = 2log(N)

Sekian pembahasan contoh algoritma yang digunakan pada pemrograman Java.