Rabu, 20 Mei 2009

Radix Sort

Pengertian Sorting
Algoritma adalah kumpulan langkah sistematis untuk memperoleh hasil yang diinginkan. Salah satu contoh dari algoritma adalah Sorting (pengurutan). Sorting dapat didefinisikan sebagai pengurutan sejumlah data berdasarkan nilai tertentu. Pengurutan dapat dilakukan dari nilaiterkecil 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.

Radix Sort
Radix Sort merupakan salah satu algoritma Non-Comparasion Sort (pengurutan tanpa pembandingan). Proses ynang dilakukan dalam metode ini adalah mengklasifikasikan data sesuai dengan kategori terurut yang tertentu, dan tiap kategori dilakukan pengklasifikasian lagi, dan seterusnya sesuai kebutuhan, lalu subkategori-kategori tersebut digabungkan kembali.
Secara harfiah Radix dapat diartikan sebagai posisi dalam angka, karena metode ini pertamakalinya mengurutkan nilai-nilai input berdasarkan radix pertamanya, lalu pengurutan dilakukan berdasarkan radix keduanya, dan begitu seterusnya. Pada system decimal, radix adalah digit dalam angka decimal.
Berikut ini adalah contoh penggunaan algoritma radix sort untuk pengurutan sebuah kumpulan bilangan bulat positif, dengan jumlah digit maksimal 3 :
121 076 823 367 232 434 742 936 274
Pertama kali data dibagi-bai sesuai dengan digit terkanan :
121 076 823 367 232 434 742 936 274
Sehingga dapat ditabelkan :

Kategori Digit Isi
0 -
1 121
2 232, 742
3 823
4 434, 274
5 -
6 076, 936
7 367
8 -
9 -
Kategori Digit Isi
0 -
1 -
2 121, 823
3 232, 434, 936
4 742
5 -
6 367
7 274, 076
8 -
9 -
Tabel 1.1 Hasil Pengkategorian Pertama Tabel 1.2 Hasil Pengkategorian Kedua
Hasil pengkategorian tersebut kemudian digabung kembali menjadi :
121 232 274 823 434 274 076 936 367

Kemudian dilakukan pengkategorian lagi berdasar digit kedua :
121 232 274 823 434 274 076 936 367

Sehingga penabelannya dapat dilihat pada table 1.2
Hasil pengkategorian tersebut kemudian digabung kembali menjadi :
121 823 232 434 936 742 367 274 076

Kemudian langkah ketiga, dilakukan pengkategorian lagi berdasar digit ketiga (terakhir) :
121 823 232 434 936 742 367 274 076

Kategori Digit Isi
0 076
1 121
2 232, 274
3 367
4 434
5 -
6 -
7 742
8 823
9 936
Tabel 1.3 Hasil Pengkattegorian Ketiga

Yang kemudian hasil akhirnya dapat dituliskan :
076 121 232 274 367 434 742 823 936


Pada hasil akhir dapat dilihat bahwa data telah terurut dengan menggunakan metode radix sort. Berikut ini adalah rumus Radix Sort :

Dari langkah-langkah yang telah dilakukan dalam proses pengurutan menggunakan radix sort, jelas tampak bahwa radix sort termasuk algoritma pengurutan tanpa pembanding. Dengan sifatnya yang melihat digit-digit angka sebagai pengontrolnya, Radix Sort dapat diimplementasikan dalam pengurutan bilangan decimal dan bilangan bit. Namun dalam penggunaannya radix sort bisa dimodifikasi sehingga bisa digunakan untuk menggurutkan data-data negatif dan pecahan.
Kelebihan yang dimiliki Radix Sort antara lain adalah merupakan algoritma pengurutan yang cepat, mudah, dan sangat efektif. Namun penggunaannya terbatas pada kasus-kasus tertentu dan memerlukan memori tambahan dalam prosesnya.
Selection sort merupakan sebuah algoritma pengurutan yang secara berulang mencari item yang belum terurut dan mencari paling sedikit satu untuk dimasukkan ke dalam lokasi akhir.

Selection sort salah satu agoritma pengurutan yang mudah untuk dipelajari. Dibandingkan dengan bubble short, frekuensi pertukaran data pada selection short lebih sedikit.
Metode ini memiliki konsep memilih data yang maksimum/minimum dari suatu kumpulan data larik L, lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data maksimum/minimum yang diperoleh, diasingkan ke tempat lain, dan tidak diikutsertakan pada proses pencarian data maksimum/minimum berikutnya. Ide utama dari selection short adalah memiliki elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-1. Nilai dari I dimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.

Prinsip kerja dari Teknik Section sort ini adalah:
1. Pengecekan dimulai dari data 1 sampai dengan data ke n
2. Tentukan bilangan dengan Index terkecil dari data bilangn tersebut
3. Tukar bilangan dengan index terkecil tersebut dengan bilangan pertama (I=1) dari data bilangan tersebut
4. Lakukan langkah 2 dan3 untuk bilangan berikutnya (I=I+1)sampai di dapatkan data yang optimal

Sintaks program fungsi Selection Sort
for ( i=0 ; i <= N-2 ; i++) { kecil = i; for ( k = i+1 ; k <= N-1 ; k++ ) { if (A[k] > A[j])
{
kecil = k;
}
}
temp = A[i];
A[i] = A[kecil];
A[kecil] = temp;
}



Contoh kasus:
Misalkan tabel A berisi elemen-elemen berikut:
61, 39, 32, 21, 2, 37
Langkah-langkah pengurutan dengan Selection Sort:
Contoh Ilustrasi: Urutkan data berikut 61, 39, 32, 21, 2, 37
Contoh program:
import java.io.*;
class ArrayBil{
private int[] arrBil = new int[5];
ArrayBil(){
}
ArrayBil(int[] arr){
this.arrBil = arr;
}
public void setArrBil(int[] arr){
this.arrBil = arr;
}
public int[] getArrBil(){
return(arrBil);
}
public void inputArray() {
BufferedReader jwb;
for (int i=0;i<5;i++) jwb =" new" i ="0;" n =" 5;" i ="">

Selasa, 19 Mei 2009

Selection Sort

Selection sort merupakan sebuah algoritma pengurutan yang secara berulang mencari item yang belum terurut dan mencari paling sedikit satu untuk dimasukkan ke dalam lokasi akhir. Selection sort salah satu agoritma pengurutan yang mudah untuk dipelajari. Dibandingkan dengan bubble short, frekuensi pertukaran data pada selection short lebih sedikit.
Metode ini memiliki konsep memilih data yang maksimum/minimum dari suatu kumpulan data larik L, lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data maksimum/minimum yang diperoleh, diasingkan ke tempat lain, dan tidak diikutsertakan pada proses pencarian data maksimum/minimum berikutnya. Ide utama dari selection short adalah memiliki elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-1. Nilai dari I dimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.

Prinsip kerja dari Teknik Section sort ini adalah:
1. Pengecekan dimulai dari data 1 sampai dengan data ke n
2. Tentukan bilangan dengan Index terkecil dari data bilangn tersebut
3. Tukar bilangan dengan index terkecil tersebut dengan bilangan pertama (I=1) dari data bilangan tersebut
4. Lakukan langkah 2 dan3 untuk bilangan berikutnya (I=I+1)sampai di dapatkan data yang optimal

Sintaks program fungsi Selection Sort
for ( i=0 ; i <= N-2 ; i++) { kecil = i; for ( k = i+1 ; k <= N-1 ; k++ ) { if (A[k] > A[j])
{
kecil = k;
}
}
temp = A[i];
A[i] = A[kecil];
A[kecil] = temp;
}



Contoh kasus:
Misalkan tabel A berisi elemen-elemen berikut:
61, 39, 32, 21, 2, 37
Langkah-langkah pengurutan dengan Selection Sort:
Contoh Ilustrasi: Urutkan data berikut 61, 39, 32, 21, 2, 37
Contoh program:
import java.io.*;
class ArrayBil{
private int[] arrBil = new int[5];
ArrayBil(){
}
ArrayBil(int[] arr){
this.arrBil = arr;
}
public void setArrBil(int[] arr){
this.arrBil = arr;
}
public int[] getArrBil(){
return(arrBil);
}
public void inputArray() {
BufferedReader jwb;
for (int i=0;i<5;i++) jwb =" new" i ="0;" n =" 5;" i =" 0;i

Kamis, 14 Mei 2009

Sabtu, 02 Mei 2009

stack

1. DEFINISI STACK

Stack merupakan suatu kumpulan data yang seolah-olah ada data yang diletakkan di atas data yang lain. Dimana kita dapat menambah (menyisip) data, dan mengambil (menghapus) data lewat ujung yang sama, yang disebut sebagai ujung atas tumpukan (top of stack).

Stack bersifat LIFO (Last In First Out), yang berarti data yang terakhir masuk ke dalam stack akan menjadi data pertama yang dikeluarkan dari stack. Secara sederhana sebuah stack dapat kita ilustrasikan sebagai berikut:

coba Queue

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;

public class CobaQueue
{
private static int Ukuran;
private static Queue NewQueue;

public static void main(String[] args)
{
BuatQueue();
BacaData();
TulisData();
}

private static void BuatQueue()
{
NewQueue = new LinkedList();
}

private static int InputData()
{
BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
String AngkaInput = null;
try
{
AngkaInput = bfr.readLine();
}
catch (IOException e)
{
e.printStackTrace();
}
int Data = Integer.valueOf(AngkaInput).intValue();
return Data;
}

private static void BacaData()
{
BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
String NewData = null;
String StringInput = null;
int data;
for (int i = 0; i < 8; i++) {
System.out.print("Data ke-" + (i + 1) + " : ");
try
{
StringInput = bfr.readLine();
}
catch (IOException e)
{
e.printStackTrace();
}
NewData = String.valueOf(StringInput);
NewQueue.add(NewData);
}
data = NewQueue.size();
System.out.println("Ukuran QUEUE sekarang adalah " + data);
}

private static void TulisData()
{
int data;
String NewData = null;
System.out.println("\nUrutan keluar elemen dari QUEUE : ");
for (int i = 0; i < 8; i++)
{
NewData = NewQueue.remove();
System.out.println("Data ke-" + (i + 1) + " : " + NewData);
}
data = NewQueue.size();
System.out.println("Ukuran QUEUE sekarang adalah " + data);
}
}