December 12, 2008
Bubble Sort
Bubble Sort adalah algoritma Sorting yang paling populer, paling gampang diimplementasikan dan juga paling rakus memakan resource.
Algoritma ini mengiterasi seluruh elemen array dari awal sampai akhir dan membandingkan setiap dua buah elemen array yang bertetanggaan.
Jika didapati kedua elemen yang bertetanggaan itu berbeda (salah satu elemen lebih besar/kecil dari elemen lain), maka kedua elemen itu akan “ditempatkan” pada urutan yang benar.
Jika metode pengurutan yang diinginkan adalah ascending (dari kecil ke besar), maka elemen yang lebih besar akan ditempatkan setelah elemen yang lebih kecil.
Begitu juga sebaliknya, jika metode pengurutan yang diinginkan adalah descending (dari besar ke kecil), maka elemen yang lebih besar akan ditempatkan sebelum elemen yang lebih kecil.
Untuk lebih jelasnya silahkan perhatikan dua buah ilustrasi di bawah ini (ascending)
- Ilustrasi dengan angka (dari Wikipedia)
Iterasi pertama:
( 5 1 4 2 8 ) -> ( 1 5 4 2 8 ) Algoritma ini membandingkan dua elemen pertama dan menukarnya
( 1 5 4 2 8 ) -> ( 1 4 5 2 8 ) swap
( 1 4 5 2 8 ) -> ( 1 4 2 5 8 ) swap
( 1 4 2 5 8 ) -> ( 1 4 2 5 8 )Iterasi kedua:
( 1 4 2 5 8 ) -> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) -> ( 1 2 4 5 8 ) swap
( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )Sebenarnya, array ini sudah terurut dengan baik, tetapi algoritma kita belum tau. Algoritma kita hanya tahu bahwa dia harus mengiterasi lagi dan baru berhenti jika tidak terjadi swap sama sekali.
Iterasi ketiga:
( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )Akhirnya, algoritma kita sadar bahwa tidak ada swap lagi dan algoritma pun berhenti mengiterasi.
- Ilustrasi dengan gambar (refresh browser anda jika gambar tidak bergerak)
Berikut ini saya sediakan implementasi Bubble Sort dalam Java..
public class Sort {
private Sort(){}
public static <T extends Comparable<T>> T[] bubble(T[] arr){
boolean swapped;
for (int i = 0; i < arr.length; i++){
swapped = false;
for (int j = arr.length - 1; j >= i + 1; j--){
if (arr[j - 1].compareTo(arr[j]) > 0){
T t = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = t;
swapped = true;
}
}
if (!swapped) break;
}
return arr;
}
}
Sayangnya, method bubble di atas hanya bisa mengurutkan ascending dan ini kurang baik. Untuk mengembangkan method bubble di atas agar bisa mengurutkan secara ascending dan descending, kita tambahkan beberapa perubahan seperti ini :
public class Sort {
private Sort(){}
public static <T extends Comparable<T>> T[] bubble(T[] arr, boolean isAscending){
boolean swapped;
for (int i = 0; i < arr.length; i++){
swapped = false;
for (int j = arr.length - 1; j >= i + 1; j--){
if ((isAscending && (arr[j - 1].compareTo(arr[j]) > 0)) ||
(!isAscending && (arr[j - 1].compareTo(arr[j]) < 0)))
{
T t = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = t;
swapped = true;
}
}
if (!swapped) break;
}
return arr;
}
public static <T> T[] bubble(T[] arr, Comparator<T> comparator, boolean isAscending){
boolean swapped;
for (int i = 0; i < arr.length; i++){
swapped = false;
for (int j = arr.length - 1; j >= i + 1; j--){
if ((isAscending && (comparator.compare(arr[j - 1], arr[j]) > 0)) ||
(!isAscending && (comparator.compare(arr[j - 1], arr[j]) < 0)))
{
T t = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = t;
swapped = true;
}
}
if (!swapped) break;
}
return arr;
}
}
Penjelasan kode program di atas masih agak rumit, mengingat blog ini belum membahas tentang Generic. Sebagai gambaran saja, method bubble pada kode program di atas
akan meminta input berupa array of T. Dimana T adalah suatu kelas yang mengimplement interface Comparable. Mengapa Comparable? Karena
interface inilah yang mampu menjanjikan bahwa suatu object yang mengimplement dirinya akan dapat dibandingkan dengan object lain.
public class Student {
private String name;
private int point;
public Student (String name, int point){
this.name = name;
this.point = point;
}
public String getName() {return name;}
public int getPoint() {return point;}
@Override
public String toString(){
return name + ":" + point;
}
public static void main(String[] args) {
Integer[] integers = new Integer[]{1, -10, 3, 0, 6, 7, 4, 2, 1, 15, 5, -6};
String[] strings = new String[]{"pisang", "apel", "nangka",
"jambu", "rambutan", "melon", "nanas"};
Student[] students = new Student[]{
new Student("basana", 64), new Student("tika", 68), new Student("ingel", 98),
new Student("bule", 45), new Student("septa", 78), new Student("hartoyo", 85),
new Student("jaya", 97), new Student("lukas", 25), new Student("lia", 77),
new Student("akub", 68)
};
for (Integer i : Sort.bubble(integers, true))System.out.print(i + " ");
System.out.println();
// Mengeluarkan output -10 -6 0 1 1 2 3 4 5 6 7 15
for (String s : Sort.bubble(strings, false))System.out.print(s + " ");
System.out.println();
// Mengeluarkan output rambutan pisang nangka nanas melon jambu apel
}
for (Student st : Sort.bubble(students, new StudentComparator(), true))
System.out.print(st + " ");
System.out.println();
// Mengeluarkan output lukas:25 bule:45 basana:64 akub:68 tika:68 lia:77
// septa:78 hartoyo:85 jaya:97 ingel:98
}
Ini kelas comparatornya :
public class StudentComparator implements Comparator<Student> {
@Override
public int compare(Student s1, Student s2) {
int i = s1.getPoint() - s2.getPoint();
if (i == 0) return s1.getName().compareTo(s2.getName());
return i;
}
}
Sekedar tambahan, ada pengembangan dari Bubble Sort dimana algoritma tidak hanya mengiterasi array dari elemen paling awal, tetapi juga dari elemen paling akhir. Pengembangan ini dikenal dengan nama “Bidirectional Bubble Sort” dan inilah implementasinya di Java
public class Sort {
private Sort(){}
public static <T extends Comparable> T[] bidirectionalBubble(T[] arr, boolean isAscending){
int top = arr.length;
int bot = -1;
boolean swapped;
while (bot < top) {
swapped = false;
bot++;
top--;
for (int i = bot; i < top; i++) {
if ((isAscending && (arr[i].compareTo(arr[i + 1]) > 0)) ||
(!isAscending && (arr[i].compareTo(arr[i + 1]) < 0)))
{
T t = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = t;
swapped = true;
}
}
if (!swapped) break;
for (int j = top; --j >= bot;) {
if ((isAscending && (arr[j].compareTo(arr[j + 1]) > 0)) ||
(!isAscending && (arr[j].compareTo(arr[j + 1]) < 0)))
{
T t = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = t;
swapped = true;
}
}
if (!swapped) break;
}
return arr;
}
public static T[] bidirectionalBubble(T[] arr, Comparator comparator, boolean isAscending){
int top = arr.length;
int bot = -1;
boolean swapped;
while (bot < top) {
swapped = false;
bot++;
top--;
for (int i = bot; i < top; i++) {
if ((isAscending && (comparator.compare(arr[i], arr[i + 1]) > 0)) ||
(!isAscending && (comparator.compare(arr[i], arr[i + 1]) < 0)))
{
T t = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = t;
swapped = true;
}
}
if (!swapped) break;
for (int j = top; --j >= bot;) {
if ((isAscending && (comparator.compare(arr[j], arr[j + 1]) > 0)) ||
(!isAscending && (comparator.compare(arr[j], arr[j + 1]) < 0)))
{
T t = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = t;
swapped = true;
}
}
if (!swapped) break;
}
return arr;
}
}
December 11, 2008
Access Modifier di Java
Di Java, dikenal empat buah Access Modifier, yaitu private, protected, public dan default. Ada baiknya jika kita mempelajari lagi keempat access modifier ini
- Access modifier private adalah access modifier yang paling tertutup. Field maupun method yang dinyatakan private tidak akan bisa diakses (visible) oleh kelas manapun dimanapun, kecuali kelas itu sendiri.
- Access modifier default adalah access modifier yang akan anda peroleh jika anda tidak memberikan access modifier apapun di suatu field ataupun method. Acces modifier default sifatnya visible terhadap kelas-kelas yang terdapat dalam package yang sama. Sekedar catatan, keyword default di Java dipakai dalam conditional switch, artinya anda tidak bisa secara eksplisit mengetikkan kata default sebagai access modifier di suatu field ataupun method. Dengan membiarkan access modifier-nya kosong, maka suatu field ataupun method akan diberi access modifier default.
- Access modifier protected mirip dengan default, hanya saja protected harus ditulis secara eksplisit dalam kode program. Selain itu, protected juga memiliki sifat tambahan, yaitu field dan method yang diberi access modifier ini akan diturunkan ke subclass.
- Access modifier public – gampangnya – berarti world-accessable. Artinya, kelas manapun dimanapun dapat mengakses field atau method yang ditandai public.
Sebagai tambahan untuk pembaca. Sebuah kelas akan terlihat “telanjang bulat” di hadapan inner class-nya. Artinya, field-field ataupun method-method yang ditandai private pun tetap dapat diakses oleh inner class. Begitu juga sebaliknya.
Contoh 1 :
package buah;
private class Pepaya {}
Kode program di atas akan menghasilkan compile error, karena deklarasi kelas tidak boleh menggunakan access modifier private. (Sebenarnya, ada kasus-kasus dimana boleh, tapi itu tidak dibahas di post ini)
Contoh 2 :
package buah;Kode program di atas akan menghasilkan kelas Pepaya dengan access modifier default dan juga atribut ‘nama’ dengan access modifier default.
class Pepaya {
String nama = "Pepaya mentah";
}
Untuk mengaksesnya, kita buat kelas Mangga (dengan access modifier default) yang berada di package yang sama
package buah; Sesuai harapan.. anda akan menerima output berupa tulisan ‘Pepaya Mentah’. Sebagai catatan, kelas Mangga tidak harus menggunakan access modifier default , access modifier protected maupun public pun bisa dipakai.
class Mangga {
public static void main(String... args){
Pepaya p = new Pepaya();
System.out.println(p.nama);
}
}
Contoh 3 :
package buah;
protected class Jambu {
protected String nama = "Jambu ga jelas";
}
Untuk mengakses kelas Jambu yang protected beserta atribut ‘nama’-nya yang protected. Kita harus meng-inherit kelas Jambu tersebut. Perlu diperhatikan bahwa post ini tidak membahas soal inheritance, tetapi pada access modifier. Oleh karena itu detail tentang inheritance tidak akan dibahas.
package sayur;
import buah.Jambu;
public class JambuKlutuk extends Jambu {
public String nama = "Jambu klutuk";
}
package buah;
public class Mangga{
public static void main(String... args){
Jambu j = new Jambu();
System.out.println(j.nama);
}
}
Ada beberapa hal yang harus diperhatikan :
- Access modifier protected tidak harus di-akses via inheritance. Kelas-kelas yang berada dalam package yang sama juga dapat mengakses kelas/atribut/method yang protected
- (Sedikit menyimpang) Dalam inheritance, access modifier tidak boleh semakin tertutup. Kelas JambuKlutuk yang meng-inherit kelas Jambu harus menggunakan access modifier yang lebih terbuka dari protected, misalnya public.
Untuk akses modifier public, tampaknya tidak perlu dibahas lagi. Access modifier ini sangat lazim dipakai dan tidak perlu dibahas lagi.
Sebagai penutup, ini table access modifier yang mungkin bisa dijadikan panduan :
December 10, 2008
Membuat Oracle JDeveloper Berlari Seperti Anjing
Secara default, JDeveloper keluaran Oracle akan berlari seperti siput. Saya tidak tahu bagaimana caranya membuat JDeveloper berlari seperti cheetah ataupun kuda. Tapi saya tahu bagaimana cara membuat JDeveloper berlari seperti anjing 
Oke.. sebelumnya, kita samakan dulu environment yang dipakai. Dalam post ini, saya menggunakan Ubuntu Linux dengan user bernama wks309. Artinya, home directory saya adalah /home/wks309 dan JDeveloper saya install di /home/wks309/master/jdev. Oh iya, memori fisik yang dimiliki oleh workstation saya adalah 2 GB, silahkan sesuaikan setting anda 
Nah inilah langkah-langkah yang dapat anda coba untuk membuat JDeveloper anda berlari seperti anjing
- Edit konfigurasi JDeveloper
JDeveloper mempunyai file konfigurasi yang akan dibaca pada saat dijalankan, file tersebut terletak di /home/wks309/master/jdev/jdev/bin/jdev.conf. Sebelum membuka file tersebut, buatlah backup file tersebut dan beri nama jdev.conf.bak.
Sekarang, kita edit beberapa entry pada file tersebut…
dari AddVMOption -Xmx512M
menjadi AddVMOption -Xmx1024M
Anda tidak perlu mengalokasikan memori dalam jumlah yang terlalu besar, karena perubahan yang dihasilkan oleh entry ini tidak signifikandari # AddVMOption -DVFS_ENABLE=true
menjadi AddVMOption -DVFS_ENABLE=truedari # AddVMOption -Dsun.java2d.noddraw=true
menjadi AddVMOption -Dsun.java2d.noddraw=true - Minimalkan entry yang ada di faces_config.xml
Salah satu trik yang bisa dipakai untuk membuat JDeveloper berlari lebih cepat adalah dengan meminimalkan entri-entri pada faces_config.xml.
Pada project yang besar, entri pada faces_config bisa sampai beribu-ribu baris dan JDeveloper akan berlari seperti siput. Untuk mengakali hal ini, hapus/komen semua entri-entri di faces_config.xml yang tidak anda perlukan dan dijamin JDeveloper akan berlari lebih kencang, seperti seekor anjing. Guk!! Guk!! Sebagai tambahan, dalam project yang besar biasanya faces config yang dimiliki tidak hanya satu buah. Anda juga perlu menghapus/meng-komen entri-entri di file faces config lain untuk mempercepat lari JDeveloper anda
- Disable ekstensi-ekstensi yang tidak diperlukan
Jika anda masuk ke Help -> About -> Extensions anda akan melihat fitur-fitur apa saja yang disediakan oleh JDeveloper.
Sekarang, anda dapat mempercepat laju JDeveloper anda dengan men-disable ekstensi-ekstensi yang tidak diperlukan
Caranya :- Daftarkan ekstensi yang tidak anda perlukan
Buat satu file kosong, sebut saja “disabled-extension.txt” dan letakkan di /home/wks309. Lalu isi file tersebut dengan ekstensi-ekstensi yang tidak anda perlukan, misalnya :
oracle.bibeans
oracle.jdeveloper.cvs
oracle.vcr.10.1.3
oracle.wireless.dt
oracle.portlets
oracle.jviews-registration
oracle.struts
oracle.bpm.workflow
oracle.extapp
- Jalankan JDeveloper dengan opsi tambahan -J-Dide.noextensions
Untuk men-disable ekstensi-ekstensi yang anda daftarkan itu, jalankan JDeveloper dengan opsi tambahan -J-Dide.noextensions=@/home/wks309/disabled-extension.txt. Dalam environment saya, perintah lengkapnya menjadi /home/wks309/master/jdev/jdev/bin/jdev -J-Dide.noextensions=@/home/wks309/disabled-extension.txt
Sekarang anda dapat cek kembali ekstensi-ekstensi yang di-load oleh JDeveloper dan hasilnya akan tampak seperti ini :
- Daftarkan ekstensi yang tidak anda perlukan
Dengan mengikuti cara-cara yang disebutkan di atas, seharusnya JDeveloper anda dapat berlari lebih cepat. Walaupun tidak secepat cheetah atau kuda, secepat anjing pun bolehlah
Faktor Persekutuan Terbesar (FPB) & Kelipatan Persekutuan Terkecil (KPK)
Jika kita mempunyai dua buah bilangan bukan 0, sebut saja a dan b, maka FPB didefinisikan sebagai bilangan bulat terbesar yang habis membagi kedua bilangan tersebut (a dan b).
Menurut pengamatan saya, anak-anak SD jauh lebih tangkas dalam menghitung FPB ketimbang orang dewasa , karena anak-anak SD mempelajari FPB untuk menghadapi ulangan di sekolah sementara orang dewasa tidak lagi memperhatikan hal-hal menarik dalam bilangan.
Alih-alih memberikan penjelasan tentang FPB, post ini akan memberikan contoh FPB karena pembaca pasti sudah pernah mendengar tentang FPB, hanya perlu diingatkan kembali…
- FPB(30, 24)
Faktor dari 30 : 2 x 3 x 5
Faktor dari 24 : 2 x 2 x 2 x 3
FPB dari 30 dan 24 = 2 x 3 = 6 - FPB(12, 140)
Faktor dari 12 : 2 x 2 x 3
Faktor dari 140 : 2 x 2 x 5 x 7
FPB dari 12 dan 140 = 2 x 2 = 4 - FPB(52, 260)
Faktor dari 52 : 2 x 2 x 13
Faktor dari 260 : 2 x 2 x 5 x 13
FPB dari 52 dan 260 = 2 x 2 x 13 = 52
Bagaimana? Sudah ingat tentang FPB? Jika anda sudah ingat tentang FPB, mari kita lanjutkan pembahasan menuju Bézout’s identity.
Dalam teori bilangan, ada sebuah lemma yang mengatakan “Jika a dan b adalah dua buah bilangan bulat bukan 0 dengan FPB d, maka pastilah ada bilangan bulat x dan y yang memenuhi persamaan ax + by = d” Lemma inilah yang dikenal sebagai Bézout’s lemma dan x dan y disebut Bézout’s identity
Sesuai dengan contoh FPB di atas, maka
- FPB(30, 24)
x = 1, y = -1
.:. 30 . 1 + 24 . (-1) = FPB(30, 24) = 6 - FPB(12, 140)
x = 12, y = -1
.:. 12 . 12 + 140 . (-1) = FPB(12, 140) = 4 - FPB(52, 260)
x = 1, y = 0
.:. 52 . 1 + 260 . 0 = FPB(52, 260) = 52
Mengenai pembuktian tentang Bézout’s identity, saya serahkan sepenuhnya kepada matematikawan-matematikawan
Selain Bézout’s identity, di dalam FPB juga dikenal satu istilah lagi, koprima (coprime). Koprima atau biasa juga disebut relatif prima terjadi jika FPB dari a dan b adalah 1. Artinya, a dan b tidak memiliki satu pun faktor persekutuan, kecuali 1. Mirip dengan definisi bilangan prima bukan? Coba baca post tentang bilangan prima ini untuk memperjelas.
Berikut ini adalah potongan program dalam Java untuk mencari Bézout’s identity, menghitung FPB dan tentu saja menentukan apakah suatu pasangan bilangan adalah koprima atau bukan. Potongan program ini menggunakan kelas Pair, mungkin ada baiknya anda lompati dulu pembacaan source code dari kelas Pair karena kita belum membahas tentang Generic
public class Pair<L extends Comparable<L>, R extends Comparable<R>>
implements java.io.Serializable, Comparable<Pair<L, R>>
{
private static final long serialVersionUID = -3392433628448662871L;
private L left;
private R right;
public Pair(){}
public Pair(L left, R right){
this.left = left;
this.right = right;
}
public L getLeft() {return left;}
public void setLeft(L left) {this.left = left;}
public R getRight() {return right;}
public void setRight(R right) {this.right = right;}
@Override
public int compareTo(Pair<L, R> p) {
return left.compareTo(p.left) != 0 ? left.compareTo(p.left) : right.compareTo(p.right);
}
}
public class Math{
private Math(){}
public static Pair<Integer, Integer> getBezoutIdentity(int a, int b){
if ((a % b) == 0) return new Pair<Integer, Integer>(0, 1);
else {
Pair<Integer, Integer> bi = getBezoutIdentity(b, a % b);
return new Pair<Integer, Integer>(bi.getRight(), bi.getLeft() - bi.getRight() * (a / b));
}
}
public static int gcd(int a, int b){
Pair<Integer, Integer> bezoutIdentity = getBezoutIdentity(a, b);
return a * bezoutIdentity.getLeft() + b * bezoutIdentity.getRight();
}
public static boolean isCoprime(int a, int b){return gcd(a, b) == 1;}
}
Jika berbicara FPB, biasanya kita juga membicarakan KPK. Intinya, KPK, dalam definisi non-formal adalah bilangan positif terkecil yang merupakan kelipatan dari a dan b (masih dalam konteks FPB). Sekarang, kita gunakan contoh-contoh di atas untuk menyegarkan kembali ingatan kita tentang KPK.
- KPK(30, 24)
Kelipatan dari 30 : 30, 60, 90, 120, dst…
Kelipatan dari 24 : 24, 48, 72, 96, 120, dst..
KPK dari 30 dan 24 = 120 - KPK(12, 140)
Kelipatan dari 12 : 12, 24, 36, 48, 60, 72, 84, 96, 108, 120, .. 396, 408, 420, dst…
Kelipatan dari 140 : 140, 280, 420, dst…
KPK dari 12 dan 140 = 140 - KPK(52, 260)
Kelipatan dari 52 : 52, 104, 156, 208, 260, dst…
Kelipatan dari 260 : 260, 520, 780, dst…
KPK dari 52 dan 260 = 260
Secara matematis, KPK dinyatakan sebagai hasil bagi antara perkalian a dan b dengan FPB-nya.
Alhasil, mudahlah bagi kita untuk membuat method untuk menghitung KPK.
public class Math{
/*
* method-method sebelumnya ....
*/
public static int lcm(int a, int b){return a * b / gcd(a, b);}
}
Variabel Swap
Dalam pemrograman komputer, dikenal istilah Swap, yaitu suatu tindakan menukar nilai antar dua buah variabel.
Sebagai ilustrasi, misalkan anda mempunyai variabel x dengan nilai 10 dan y dengan nilai 15. Setelah di-swap, maka nilai x akan menjadi 15 dan y menjadi 10.
Ada banyak cara untuk melakukan swap, yang paling mudah adalah dengan menggunakan suatu variabel temporer (dummy variable). Seperti ini :
public class Main{
public static void main (String[] args){
Object a = "first";
Object b = 2;
Object c = a; // c adalah variabel temporer
a = b;
b = c;
System.out.println(a + " " + b);
// Mengeluarkan output 2 first
}
}
Cara ini memang sangat mudah tapi juga sangat naif, karena menggunakan sebuah variabel temporer yang kesannya males mikir
Dalam dunia algoritma, dikenal dua buah metode swap lagi yang tidak membutuhkan variabel temporer seperti pada kode program di atas. Sayangnya, kedua algoritma ini hanya berlaku untuk beberapa tipe data primitif saja.
Berikut ini adalah algoritma swap yang hanya menggunakan operasi tambah dan kurang. Algoritma ini tidak memerlukan variabel temporer. Sayangnya, algoritma ini hanya dapat diaplikasikan pada tipe data integer (int dan Integer) saja.
public class Main{
public static void main(String[] args){
int a = 24;
int b = 7;
a = a + b;
b = a - b;
a = a - b;
System.out.println(a + " " + b);
// Mengeluarkan output 7 24
}
}
Algoritma swap yang kedua jelas lebih cerdas dan lebih cepat dibanding algoritma yang pertama kali disuguhkan. Lebih cerdas karena tidak menggunakan variabel temporer dan lebih cepat karena hanya melakukan operasi penjumlahan.
Algoritma swap terakhir yang akan dibahas dalam post ini adalah algoritma yang menggunakan operator XOR (Exclusive OR). Algoritma ini berlaku untuk tipe data integer (int dan Integer), char (char dan Character), dan boolean (boolean dan Boolean).
Sekedar menyegarkan ingatan kembali, berikut saya lampirkan tabel kebenaran untuk AND, OR dan XOR
| p | q | p & q | p | q | p ^ q |
| T | T | T | T | F |
| T | F | F | T | T |
| F | T | F | T | T |
| F | F | F | F | F |
Dengan memanfaatkan operasi XOR, kita dapat menghasilkan sebuah algoritma swap yang lebih manis, sebagai berikut :
public class Main{
public static void main(String[] args){
// XOR Swap dengan memakai Integer sebagai contoh
// Berlaku juga untuk Boolean, Character serta primitif int, boolean, dan char
Integer a = 24;
Integer b = 7;
a ^= b;
b ^= a;
a ^= b;
System.out.println(a + " " + b);
// Mengeluarkan output 7 24
}
}
Lantas bagaimana jika kita menginginkan suatu method yang meminta dua buah object sebagai parameter dan menukar nilai keduanya? Mengingat sifat Java yang copy by reference, kita tidak dapat mengganti state dari sebuah object yang dilempar sebagai parameter. Untuk mengganti state dari object tersebut, haruslah disediakan setternya. Sayangnya, di Java ada beberapa object yang sifatnya immutable, artinya object-object ini tidak dapat diganti lagi statenya setelah diinisiasi. Integer, String, Character dan Boolean tergolong dalam object-object yang immutable. Oleh karena itu, sampai saat ini saya masih beranggapan mustahil mengubah state object-object immutable dalam sebuah method dimana object-object tersebut dikirim sebagai parameter.
Supaya tidak menjadi bingung, perihal copy by reference dan immutable akan dibahas di post lain. Saat ini anggap saja bahwa “object yang dikirim sebagai parameter haruslah menyediakan setter jika ingin diubah nilainya”. Dengan demikian dirancanglah kelas-kelas berikut ini :
public class Dummy {
private Character initial;
private Integer age;
private Boolean active;
public Dummy(Character initial, Integer age, Boolean active){
this.active = active;
this.initial = initial;
this.age = age;
}
public Boolean getActive() {return active;}
public void setActive(Boolean active) {this.active = active;}
public Character getInitial() {return initial;}
public void setInitial(Character initial) {this.initial = initial;}
public Integer getAge() {return age;}
public void setAge(Integer age) {this.age = age;}
public String toString(){return initial + " " + age + " " + active;}
}
public class DummySwapper {
private DummySwapper(){}
public static void swap (Dummy d1, Dummy d2){
// INITIAL - Character
d1.setInitial((char) (d1.getInitial() ^ d2.getInitial()));
d2.setInitial((char) (d2.getInitial() ^ d1.getInitial()));
d1.setInitial((char) (d1.getInitial() ^ d2.getInitial()));
// AGE - Integer
d1.setAge(d1.getAge() ^ d2.getAge());
d2.setAge(d2.getAge() ^ d1.getAge());
d1.setAge(d1.getAge() ^ d2.getAge());
// ACTIVE - Boolean
d1.setActive(d1.getActive() ^ d2.getActive());
d2.setActive(d2.getActive() ^ d1.getActive());
d1.setActive(d1.getActive() ^ d2.getActive());
}
}
public class Main {
public static void main(String... args) {
Dummy d1 = new Dummy('A', 11, true);
Dummy d2 = new Dummy('Z', 99, false);
DummySwapper.swap(d1, d2);
System.out.println(d1);
// Mengeluarkan output Z 99 false
System.out.println(d2);
// Mengeluarkan output A 11 true
}
}
December 9, 2008
Bilangan Prima
Bilangan prima secara matematis didefinisikan sebagai bilangan asli yang mempunyai tepat dua buah faktor, yaitu 1 dan bilangan itu sendiri. Contoh bilangan prima adalah :
- 2
Karena 2 adalah bilangan asli dan faktor dari 2 adalah 1 dan 2. - 31
Karena 31 hanya habis dibagi oleh 1 dan 31. - dst
Sampai saat ini, umat manusia belum bisa menemukan dengan pasti formula dari bilangan prima ke-n. Banyak algoritma ditawarkan, tetapi algoritma-algoritma tersebut masih memiliki kelemahan.
Bilangan prima, dalam dunia teknologi informasi banyak dimanfaatkan di bidang kriptografi sebagai “bahan baku enkripsi”, karena sifatnya yang masih non-determinable. Salah satu algoritma enkripsi yang menggunakan bilangan prima sebagai bahan bakunya adalah RSA, yang sampai saat ini masih tangguh menghadapi cobaan
Alih-alih mencari formula menentukan bilangan prima ke-n, matematikawan lebih suka menciptakan algoritma penentuan keprimaan suatu bilangan.
Cara yang paling lazim dipakai untuk menentukan keprimaan suatu bilangan adalah Brute Force Attack, dimana program akan memeriksa semua bilangan dari 2 sampai n-1 habis membagi n. Algoritma ini memang mujarab untuk memeriksa keprimaan suatu bilangan, sayangnya algoritma ini memiliki kompleksitas yang tinggi dan sudah pasti tidak layak diterapkan untuk memeriksa bilangan yang bermilyar-milyar
Sebagai contoh : Untuk memeriksa apakah 215 itu adalah bilangan prima atau bukan, maka bagilah 215 dengan 2, 3, … 214. Jika ditemukan satu saja bilangan yang dapat membagi habis 215, maka 215 bukanlah bilangan prima
Salah satu akal-akalan (heuristic) bagi algoritma di atas. adalah dengan membatasi pencarian tidak kepada n-1, melainkan kepada . Hal ini secara matematis dapat dijelaskan begini : Jika suatu bilangan asli memiliki faktor selain 1 dan dirinya sendiri, maka salah satu dari faktor-faktor tersebut pasti kurang dari atau sama dengan
Dengan demikian , kita tidak perlu memeriksa seluruh bilangan dari 2 sampai 214, melainkan cukup memeriksa bilangan dari 2 sampai 15 (pembulatan dari 14,6).
Cara lain yang lazim dipakai adalah dengan menggunakan dengan Sieve. Perhatikan ilustrasi pada gambar di bawah ini :
Jika diketahui suatu bilangan adalah prima, maka semua kelipatan dari bilangan itu pasti bukan prima. Contohnya adalah bilangan 2, karena 2 adalah bilangan prima, maka pastilah semua bilangan kelipatan 2, yaitu 4, 6, 8.. bukanlah bilangan prima. Selanjutnya adalah 3, karena 3 adalah bilangan prima, maka pastilah semua bilangan kelipatan 3, yaitu 6, 9, 12.. bukanlah bilangan prima dan seterusnya…
Dengan menggunakan Sieve, maka kita tinggal memeriksa bilangan mana saja yang tidak ditandai sebagai “bilangan non-prima”. Cara ini lebih cepat ketimbang cara Brute Force yang lebih dulu ditawarkan. Untuk lebih jelasnya tentang Sieve, anda dapat membaca lebih lanjut di Sieve of Eratosthenes dan Sieve of Atkin
Sebenarnya, masih banyak cara-cara lain yang dapat digunakan untuk mempercepat pemeriksaan keprimaan suatu bilangan. Tetapi, pada post ini saya akan memadukan antara Sieve of Eratosthenes dan Brute Force Attack.
Ide utama dari algoritma di bawah ini adalah dengan membuat semacam kamus bilangan prima yang sudah dikenal. Lalu memeriksa apakah bilangan yang dimasukkan habis dibagi oleh bilangan-bilangan tersebut atau tidak. Jika iya, maka bilangan tersebut bukanlah bilangan prima. Disinilah pemanfaatan dari Sieve of Eratosthenes.
Jika bilangan yang dimasukkan tidak habis dibagi oleh satupun bilangan yang ada di kamus tersebut gunakan cara Brute Force yang sudah diberi heuristik untuk menghemat waktu.
Jelasnya lihat potongan programnya :
public class Math{
private static int[] knownPrimeNumberSeries={
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293,
307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499,
503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,
601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691,
701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797,
809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887,
907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997
};
public static boolean isPrime(int number) {
if (number < 0) return false;
if (number <= 997){
for (int i : knownPrimeNumberSeries) {
if (i > number) return false;
if (i == number) return true;
}
}
// Sieve of Eratosthenes
if (number > 997)
for (int i : knownPrimeNumberSeries)
if (number % i == 0) return false;
// BRUTE FORCE ATTACK
int top = (int) (java.lang.Math.ceil(java.lang.Math.sqrt(number)));
for (int i = 1001; i <= top; i++)
if (number % i == 0) return false;
return true;
}
}
Pada kode di atas.. jika input yang diberikan adalah suatu bilangan antara 0 s.d 997, maka program akan memeriksanya di kamus bilangan prima yang sudah diketahui, yaitu bilangan-bilangan prima antara 0 sampai 997.
Jika bilangan yang dimasukkan lebih besar, maka kita akan menggunakan metode Sieve of Eratosthenes, dimana kita membagi bilangan tersebut dengan seluruh bilangan yang ada di kamus.
Jika masih belum ditemukan jawaban, barulah kita menggunakan cara yang paling kasar tapi efektif, yaitu Brute Force Attack.
Potongan program ini cukup mumpuni untuk bilangan-bilangan prima sehari-hari. Tetapi, jika anda berencana untuk mengikuti kontes pencarian bilangan prima terbesar, maka sebaiknya implementasikan algoritma yang lain yang dapat menentukan keprimaan suatu bilangan dengan lebih cepat .
Kode Morse
Kode morse biasanya digunakan oleh anak-anak pramuka untuk mengirimkan pesan dengan peluit. Dalam kepentingan telekomunikasi, kode morse dipakai untuk mengirim telegram. Dalam kepentingan militer, kode morse dipakai untuk mengirim pesan radio. Sayangnya, dalam kepentingan teknologi informasi, kita hanya mengenal gelombang digital (0 dan 1) sehingga sebenarnya kode morse tidaklah perlu dipelajari.
Post ini akan menampilkan program untuk membaca kode morse dan menerjemahkannya menjadi bahasa manusia dan sebaliknya. Walaupun tidak penting, tetapi ada baiknya membaca kode program di bawah ini untuk hiburan
Buatlah file Morse.properties yang isinya seperti ini :
A = ._ B = _...
C = _._. D = _..
E = . F = .._.
G = __. H = ....
I = .. J = .___
K = _._ L = ._..
M = __ N = _.
O = ___ P = .__.
Q = __._ R = ._.
S = ... T = _
U = .._ V = ..._
W = .__ X = _.._
Y = _.__ Z = __..
0 = _____ 1 = .____
2 = ..___ 3 = ...__
4 = ...._ 5 = .....
6 = _.... 7 = __...
8 = ___.. 9 = ____.
. = ._._._ , = __..__
? = ..__.. ' = .____.
/ = _.._. ( = _.__.
) = _.__._ & = ._...
: = ___... ; = _._._.
+ = ._._. - = _...._
_ = ..__._ " = ._.._.
$ = ..._.._ @ = .__._.
public final class Morse {
private static Properties characters;
private static Properties codes;
public Morse(){
characters = new Properties();
try {
characters.load(new java.io.FileInputStream("Morse.properties"));
characters.setProperty("!", "_._.__");
characters.setProperty("=", "_..._");
codes = new Properties();
for (Object o : characters.keySet())
codes.setProperty(characters.getProperty((String)o), (String)o);
}
catch (java.io.FileNotFoundException e) {e.printStackTrace();}
catch (java.io.IOException e) {e.printStackTrace();}
}
public String getCode(char c){
return characters.getProperty(new String(new char[]{Character.toUpperCase(c)}));
}
public char getCharacter(String code){
String property = codes.getProperty(code);
if (property != null){
char[] chars = property.toCharArray();
if (chars.length != 1) return 0;
return chars[0];
}
return 0;
}
public String translateToMorse(String word){
String retval = "";
for (char c : word.toCharArray()) {
String s = getCode(c);
if (s != null) retval += s + " ";
}
return retval;
}
public String translateToWord(String morse){
String[] words = morse.trim().split(" ");
char[] chars = new char[morse.trim().length()];
int i = 0;
for (String s : words) chars[i++] = getCharacter(s);
return new String(chars);
}
}
Lalu jalankan main programnya :
public class Main {
public static void main(String[] args) {
Morse m = new Morse();
System.out.println(m.translateToMorse("hendra"));
// Mengeluarkan output .... . _. _.. ._. ._
System.out.println(m.translateToWord(".___ ._ _.__ ._"));
// Mengeluarkan output JAYA
}
}
December 4, 2008
Array di Java
Array adalah salah satu struktur data yang paling klasik dan mungkin struktur data yang pertama kali dipelajari di jurusan teknik informatika di kampus manapun. Penguasaan array dalam dunia pemrograman adalah suatu kewajiban dan pembahasan di post ini adalah array di Java.
Di Java, indeks array selalu dimulai dari 0 dan terurut naik. Selain itu, panjang array haruslah bilangan cacah (0, 1, 2.. ). Dengan demikian, berlaku sifat-sifat berikut ini :
- myArray[-1] akan melempar ArrayIndexOutOfBoundsException
- untuk array dengan panjang n, myArray.length == n
- untuk array dengan panjang n, myArray[n] akan melempar ArrayIndexOutOfBoundsException
- untuk array dengan panjang n, indeks terendah adalah 0 dan indeks tertinggi adalah n – 1
- boleh mendeklarasi array dengan panjang 0, tetapi anda akan terlihat seperti orang idiot
- untuk array dengan panjang di bawah 0, JVM akan melempar NegativeArraySizeException
- Array satu dimensi
Untuk mendefinisikan array satu dimensi sangat mudah :
- Tipe data primitif : int, boolean, dkk.
public class ArrayOfPrimitive{
public static void main(String... args){
// CARA MENDEKLARASIKAN ARRAY OF PRIMITIVE :
// 1. <primitive>[] <arrayName> = new <primitive> [length];
int[] first = new int[10];
assert first[5] == 0;// 2. <primitive>[] <arrayName> = new <primitive>[] { [enumerasi nilai array] };
int[] second = new int[]{1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
assert second[5] == 36;// CARA MENGAKSES ARRAY OF PRIMITIVE :
// 1. for (<primitive> <var> : <array>) ;
for (int i : first) System.out.println(i);
// Mengeluarkan output angka 0 10x
// TIDAK DIANJURKAN MENGGUNAKAN METODE INI
// UNTUK MENGGANTI NILAI ELEMEN ARRAY PADA SAAT RUNTIME// 2. var[<index>]
for (int i = 0; i < 10; i++) System.out.println(second[i]);
// Mengeluarkan output angka 1, 4, 9, 16, 25, 36, 49, 64, 81, 100
// GUNAKAN METODE INI UNTUK MENGGANTI NILAI ELEMEN ARRAY PADA SAAT RUNTIME
// Contoh : second[5] = 35;}
}
Metode deklarasi yang pertama lazim digunakan jika array yang akan dibuat sudah diketahui panjangnya, tetapi belum diketahui isinya. Sedangkan metode deklarasi yang kedua lazim digunakan jika array yang akan dibuat sudah diketahui panjangnya dan juga sudah diketahui isinya.Sesuai karakternya, setiap primitif memiliki nilai default. Pada int, nilai default yang diberikan adalah 0 dan pada boolean adalah false. Dengan adanya default value pada primitif ini, programmer tidak perlu menginisialisasi setiap elemen pada array (dari tipe data primitif) untuk mencegah NullPointerException.
- Object : Integer, String, dkk
Dalam perihal mendeklarasi array, tidak terdapat perbedaan antara tipe data primitif ataupun object. Hanya saja object tidak memiliki nilai default, sehingga jika tidak diinisialisasi JVM akan melempar NullPointerException
public class ArrayOfObject{
public static void main(String... args){
Integer[] first = new Integer[10];
assert first[5] == null;
first[2] = new Integer(144);
assert first[2] == 144;String[] second = new String[10];
second[3] = "Java programming language";
assert second[3].equalsIgnoreCase("JAVA PROGRAMMING LANGUAGE");
}
}Dalam array of object, array tidak memberikan nilai default seperti pada array of primitive. Sesuai contoh di atas, JVM hanya menyediakan 10 slot kosong(null) yang HANYA BOLEH diisi oleh object dari kelas yang dijanjikan (Integer, String dkk). Kompiler menjamin hal ini.
Untuk perihal mengakses, array of object tidak berbeda dengan array of primitive.
- Tipe data primitif : int, boolean, dkk.
- Array dua (multi) dimensi
- Varargs
Satu hal lagi yang perlu diketahui perihal array di Java adalah varargs.
Bagi pembaca yang teliti, mungkin akan menyadari bahwa argumen yang saya berikan dalam main method menggunakan notasi yang tidak biasanya. Kebanyakan kita menggunakan notasi String[] args, tetapi pada main method yang saya cantumkan di atas, saya menggunakan String… args yang merupakan varargs.Sebenarnya, tidak ada yang membedakan antara penggunaan notasi String[] args dengan String… args, ini hanya masalah kebiasaan saja.
Untuk diketahui, varargs hanya bisa digunakan dalam parameter dan hanya sebagai argumen terakhir. Varargs tidak bisa digunakan dalam deklarasi array ataupun return value.
public class WrongSample{
public static void main(String... args){ // BENAR
Integer... first = new Integer[10];
}
public int... badSample(){
return new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
}
public int badSample(int... arr, boolean b){
return 0;
}
public int goodSample(boolean b, int... arr){
return 0;
}
}
Di Java, array multi dimensi dipandang sebagai array of array. Maksudnya array of array adalah : “Setiap elemen yang biasanya diisi dengan primitive atau object, kini diganti oleh array”. Dalam array of array, setiap elemen array dipandang sebagai object. Sehingga, sifat-sifat array of object pada contoh di atas juga berlaku.
Perhatikan contoh di bawah ini:
public class TwoDimensionsArray{
public static void main(String... args){
Integer[][] first = new Integer[3][];
// Baris di atas berbunyi "first adalah sebuah array yang terdiri dari 3 elemen.
// Masing-masing elemennya adalah array of Integer.
first[0] = new Integer[2];
first[1] = new Integer[15]
first[2] = new Integer[1];
// Setiap elemen dari first adalah array of integer,
// sehingga setiap elemennya harus diinisialisasi lagi.
first[0][0] = new Integer(72);
first[0][1] = 99;
// Sekarang barulah elemen terkecil dari array of array ini bisa diinisialisasi dan diakses
}
}
Dalam contoh di atas, array of array-nya adalah array of array of Integer. Jangan bingung tentang cara membacanya, bacalah dari belakang seperti ini : array of (array of integer).
Karena pengertiannya yang seperti itu, maka array of array tidak harus berbentuk seperti matriks 1×1, 2×2, 3×3, 4×4 dan seterusnya, melainkan sangat fleksibel. Secara visual dilukiskan sebagai berikut
array of array di Java :
[*][*]
[*][*][*][*][*][*][*][*][*][*][*][*][*][*][*]
[*]
[*][*][*][*][*]
[*][*][*][*][*][*][*][*][*]
dimana [*] bermakna Integer
dan [*][*][*][*][*] dimaknai barisan Integer (array of Integer)
Balangan – Bali Selatan
Pantai Balangan mungkin pantai terindah yang pernah saya kunjungi. Pantai ini adalah sebuah pantai kecil yang terletak di Bali Selatan. Sayangnya, Balangan jarang sekali diekspos oleh Tour Guide manapun yang membahas Bali. Tour Guide – Tour Guide ini hanya membahas tempat-tempat terkenal yang sudah ramai dikunjungi dan sudah “dibangun”, seperti Pantai Kuta, Pantai Sanur, Danau Kintamani, Danau Bedugul, Pura Agung Besakih, Pura Agung Tanah Lot dan kadang kala Taman Wisata Sangeh. Padahal keindahan pantai Balangan sungguh menawan dan mengundang kita untuk datang kembali memeluk ombaknya.
Kesan pertama yang akan anda temui saat pertama kali menjejakkan kaki di pantai ini adalah pasir putih yang terhampar luas, pantai yang biru dan bersih, langit yang cerah dan kedamaian hidup. Mungkin terdengar berlebihan, tapi sejujurnya tidak ada satu pun yang saya lebih-lebihkan, karena pantai ini memang sungguh indah.
Karena jarang terekspos media, pengunjung pantai ini sangat sedikit. Hanya segelintir orang saja yang pernah mengunjungi pantai ini dan mayoritas pengunjungnya adalah bule. Dengan jumlah pengunjung yang sedikit, tampaknya membuat pembangunan infrastruktur di pantai ini tersendat. Hal ini terbukti dengan buruknya jalan menuju pantai ini. Yap, jalan ke pantai ini sangat kecil dan berlobang-lobang. Tetapi, penderitaan anda sepanjang perjalanan akan terbayar lunas ketika sudah melihat pemandangan di pantai ini
Ombak di Balangan tergolong besar, itulah sebabnya sebagian besar turis asing yang datang ke tempat ini ingin menghabiskan waktu dengan berseluncur. Jika anda datang ke sini untuk berenang bersiaplah untuk tergores, karena kerikil di Balangan tergolong tajam 
Untuk masalah perut dan penginapan, anda tidak perlu kuatir akan kekurangan. Karena pantai ini – walaupun kecil – mempunyai beberapa warung makan dan penginapan yang harganya memang sedikit mahal. Maklum harga turis Tetapi, pengunjung lokal mungkin tidak perlu berpikir untuk menginap/makan di pantai, karena jarak antara Balangan ke jalan raya hanya 3 Km, dapat dengan cepat ditempuh oleh kendaraan bermotor. Untuk mencapai pantai Balangan dari Denpasar, anda tinggal memacu kendaraan anda sampai Garuda Wisnu Kencana (GWK). Setelah tiba di GWK, anda tinggal lurus saja sampai ketemu sebuah perempatan yang cukup besar yang ada swalayannya di sebelah kanan jalan. Setelah tiba di perempatan ini, belok kanan dan 3 Km lagi anda akan tiba di Balangan.
Selain bermain di pantai, anda juga dapat bermain-main di bukit hijau di sekitar pantai. Bukit-bukit ini sering dipakai untuk pacaran karena tempatnya yang memang indah dan strategis. Berikut ini saya tampikan foto-foto yang menggambarkan keindahan pantai Balangan (foto diambil oleh Yohanes Widisono) :
