Kfighter1234's Blog

Sequential Search Juni 29, 2009

Algoritma searching adalah algoritma untuk mencari sebuah nilai dari sekumpulan nilai yang bertipe sama. Kumpulan data yang dimaksud dalam kuliah Algoritma dan Pemrograman II adalah array (larik). Algoritma searching dapat dikelompokkan menjadi 2, yaitu pencarian terhadap kumpulan data yang belum terurut dan pencarian terhadap kumpulan data yang sudah terurut. Salah satu contoh algoritma searching untuk data tidak terurut adalah Sequential Search, sedangkan contoh algoritma searching untuk data terurut adalah Binary Search.

Algoritma sorting adalah algoritma untuk mengurutkan kumpulan nilai. Seperti pada algoritma searching, kumpulan nilai yang dimaksud dalam kuliah Algoritma dan Pemrograman II adalah array(larik). Ada 2 jenis data terurut, yaitu terurut membesar (ascending) dan terurut mengecil (descending). Banyak metode pengurutan yang sudah ditemukan. Salah satu contoh algoritma pengurutan adalah Insertion Sort.

Untuk array dengan elemen bertype type dasar, seperti integer, real, character, dan string, algoritma searching dan sorting lebih mudah dilakukan. Namun untuk array dengan elemen bertype record (rekaman), sedikit berbeda. Kasus ini disebabkan bahwa searching maupun sorting tidak dapat dilakukan terhadap sebuah nilai rekaman. Searching maupun sorting hanya dapat dilakukan terhadap sebuah field (komponen rekaman).

Binary Seach Juni 29, 2009

Binary search adalah algoritma pencarian untuk data yang terurut. Pencarian
dilakukan dengan cara menebak apakah data yang dicari berada ditengah-tengah data,
kemudian membandingkan data yang dicari dengan data yang ada ditengah. Bila data
yang ditengah sama dengan data yang dicari, berarti data ditemukan. Namun, bila data
yang ditengah lebih besar dari data yang dicari, maka dapat dipastikan bahwa data
yang dicari kemungkinan berada disebelah kiri dari data tengah dan data disebelah
kanan data tengah dapat diabai. Upper bound dari bagian data kiri yang baru adalah
indeks dari data tengah itu sendiri. Sebaliknya, bila data yang ditengah lebih kecil dari
data yang dicari, maka dapat dipastikan bahwa data yang dicari kemungkinan besar
berada disebelah kanan dari data tengah. Lower bound dari data disebelah kanan dari
data tengah adalah indeks dari data tengah itu sendiri ditambah 1. Demikian
seterusnya.

Pencarian secara biner, digunakan ketika sebuah komputer harus mencari posisi sebuah simbol dalam daftar urut. Komputer akan mencari simbol dari tengah daftar sampai data terakhir, dan membandingkannya dengan simbol yang sedang dicari. Apabila simbol tersebut sudah ditemukan, pencarian pada setengah daftar sisanya akan dihentikan.

Implementasi Binary Search
Rekursif
BinarySearch(A[0..N-1], value, low, high) {
if (high < low)
return -1 // not found
mid = (low + high) / 2
if (A[mid] > value)
BinarySearch(A, value, low, mid-1)
else if (A[mid] < value)
BinarySearch(A, value, mid+1, high)
else
return mid // found
}

Iteratif
BinarySearch(A[0..N-1], value) {
low = 0
high = N – 1
while (low <= high) {
mid = (low + high) / 2
if (A[mid] > value)
high = mid – 1
else if (A[mid] < value)
low = mid + 1
else
return mid // found
}
return -1 // not found
}

Sorting Juni 25, 2009

Sorting adalah proses menyusun elemen – elemen dengan tata urut tertentu dan
proses tersebut terimplementasi dalam bermacam aplikasi. Kita ambil contoh pada
aplikasi perbankan. Aplikasi tersebut mampu menampilkan daftar account yang aktif.
Hampir seluruh pengguna pada sistem akan memilih tampilan daftar berurutan
secara ascending demi kenyamanan dalam penelusuran data.
Beberapa macam algoritma sorting telah dibuat karena proses tersebut sangat
mendasar dan sering digunakan. Oleh karena itu, pemahaman atas algoritma –
algoritma yang ada sangatlah berguna.
Setelah menyelesaikan pembahasan pada bagian ini, anda diharapkan mampu :
1. Memahami dan menjelaskan algoritma dari insertion sort, selection sort,
merge sort dan quick sort.
2. Membuat implementasi pribadi menggunakan algoritma yang ada

Salah satu algoritma sorting yang paling sederhana adalah insertion sort. Ide dari
algoritma ini dapat dianalogikan seperti mengurutkan kartu. Penjelasan berikut ini
menerangkan bagaimana algoritma insertion sort bekerja dalam pengurutan kartu.
Anggaplah anda ingin mengurutkan satu set kartu dari kartu yang bernilai paling
kecil hingga yang paling besar. Seluruh kartu diletakkan pada meja, sebutlah meja
ini sebagai meja pertama, disusun dari kiri ke kanan dan atas ke bawah. Kemudian
kita mempunyai meja yang lain, meja kedua, dimana kartu yang diurutkan akan
diletakkan. Ambil kartu pertama yang terletak pada pojok kiri atas meja pertama
dan letakkan pada meja kedua. Ambil kartu kedua dari meja pertama, bandingkan
dengan kartu yang berada pada meja kedua, kemudian letakkan pada urutan yang
sesuai setelah perbandingan. Proses tersebut akan berlangsung hingga seluruh kartu
pada meja pertama telah diletakkan berurutan pada meja kedua.
Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi
dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja
kedua). Elemen pertama diambil dari bagian array yang belum diurutkan dan
kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah
diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang
tersisa pada bagian array yang belum diurutkan.

void insertionSort(Object array[], int startIdx, int endIdx) {
for (int i = startIdx; i < endIdx; i++) {
int k = i;
for (int j = i + 1; j < endIdx; j++) {
if (((Comparable) array[k]).compareTo(array[j])>0) {
k = j;
}
}
swap(array[i],array[k]);
}
}

Jika anda diminta untuk membuat algoritma sorting tersendiri, anda mungkin akan
menemukan sebuah algoritma yang mirip dengan selection sort. Layaknya insertion
sort, algoritma ini sangat rapat dan mudah untuk diimplementasikan.
Mari kita kembali menelusuri bagaimana algoritma ini berfungsi terhadap satu paket
kartu. Asumsikan bahwa kartu tersebut akan diurutkan secara ascending. Pada
awalnya, kartu tersebut akan disusun secara linier pada sebuah meja dari kiri ke
kanan, dan dari atas ke bawah. Pilih nilai kartu yang paling rendah, kemudian
tukarkan posisi kartu ini dengan kartu yang terletak pada pojok kiri atas meja. Lalu
cari kartu dengan nilai paling rendah diantara sisa kartu yang tersedia. Tukarkan
kartu yang baru saja terpilih dengan kartu pada posisi kedua. Ulangi langkah –
langkah tersebut hingga posisi kedua sebelum posisi terakhir dibandingkan dan
dapat digeser dengan kartu yang bernilai lebih rendah.

Quicksort ditemukan oleh C.A.R Hoare. Seperti pada merge sort, algoritma ini juga
berdasar pada pola divide-and-conquer. Berbeda dengan merge sort, algoritma ini
hanya mengikuti langkah – langkah sebagai berikut :
1. Divide
Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r]
dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q]
dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan
elemen pada A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada
elemen q merupakan salah satu bagian dari prosedur pemisahan.

2. Conquer
Mengurutkan elemen pada sub-rangkaian secara rekursif
Pada algoritma quicksort, langkah ”kombinasi” tidak di lakukan karena telah terjadi
pengurutan elemen – elemen pada sub-array

Impelementasikan algoritma insertion sort dalam Java untuk mengurutkan
serangkaian data integer. Lakukan percobaan terhadap hasil implementasi anda
terhadap rangkaian data integer yang dimasukkan oleh pengguna melalui command
line.

Impelementasikan algoritma selection sort dalam Java untuk mengurutkan
serangkaian data integer. Lakukan percobaan terhadap hasil implementasi anda
terhadap rangkaian data integer yang dimasukkan oleh pengguna melalui command
line.

Gunakan implementasi merge sort berikut ini terhadap serangkaian data integer.
class MergeSort {
static void mergeSort(int array[], int startIdx,
int endIdx) {
if(startIdx == _____) {
return;
}
int length = endIdx-startIdx+1;
int mid = _____;
mergeSort(array, _____, mid);
mergeSort(array, _____, endIdx);
int working[] = new int[length];
for(int i = 0; i < length; i++) {
working[i] = array[startIdx+i];
}
int m1 = 0;
int m2 = mid-startIdx+1;
for(int i = 0; i < length; i++) {
if(m2 <= endIdx-startIdx) {
if(m1 <= mid-startIdx) {
if(working[m1] > working[m2]) {
array[i+startIdx] = working[m2++];
} else {
array[i+startIdx] = _____;
}
} else {
array[i+startIdx] = _____;
}
} else {
array[_____] = working[m1++];
}
}
}
public static void main(String args[]) {
int numArr[] = new int[args.length];
for (int i = 0; i < args.length; i++) {
numArr[i] = Integer.parseInt(args[i]);
}
mergeSort(numArr, 0, numArr.length-1);
for (int i = 0; i < numArr.length; i++) {
System.out.println(numArr[i]);
}
}
}

Gunakan implementasi quicksort berikut ini terhadap serangkaian data integer.
class QuickSort {
static void quickSort (int[] array, int startIdx,
int endIdx) {
// startIdx adalah index bawah
// endIdx is index atas
// dari array yang akan diurutkan
int i=startIdx, j=endIdx, h;
//pilih elemen pertama sebagai pivot
int pivot=array[_____];
// memilah
do {
while (array[i]_____pivot) {
i++;
}
while (array[j]>_____) {
j–;
}
if (i<=j) {
h=_____;
array[i]=_____;
array[j]=_____;
i++;
j–;
}
} while (i<=j);
// rekursi
if (startIdx<j) {
quickSort(array, _____, j);
}
if (i<endIdx) {
quickSort(array, _____, endIdx);
}
}
public static void main(String args[]) {
int numArr[] = new int[args.length];
for (int i = 0; i < args.length; i++) {
numArr[i] = Integer.parseInt(args[i]);
}
quickSort(numArr, 0, numArr.length-1);
for (int i = 0; i < numArr.length; i++) {
System.out.println(numArr[i]);
}
}
}

Linked List Juni 16, 2009

penggunaan pointer adalah pada senarai berantai (linked list). Senarai berantai
tersusun atas beberapa node (simpul) yang terhubung menjadi satu kesatuan. Pada
gambar dibawah ini senarai berantai mengandung 3 buah simpul. Sebuah pointer
menunjuk ke simpul terkiri, dan setiap simpul mempunyai pointer yang menunjuk ke
simpul berikutnya. Pointer pada simpul terakhir tidak menunjuk kemana-mana (berisi
NIL)

Simpul (node) pada senarai berantai terdiri dari 2 komponen utama :
Data, terdiri dari satu elemen data atau beberapa elemen data
Pointer, yang menunjuk ke simpul yang lain.

simpul berisi data nama dan telpon serta sebuah pointer dengan
nama lanjutan yang menunjuk ke struktur simpul. Ptrsimpul menyatakan pointer yang
menunjuk ke struktur simpul.
Operasi-operasi dasar pada suatu linked List
Menambah data/simpul
Menampilkan seluruh data pada senarai
Mencari sebuah data pada senarai
Menghapus sebuah simpul
Mendefinisikan pointer pertama
adanya pointer pertama yang menunjuk ke simpul
Pointer ini diperlukan agar semua simpul pada senarai berantai dapat diakses.
Pendeklarasiannya adalah sebagai berikut :
Pertama : PtrSimpul;

Hal yang penting dilakukan adalah pointer ini harus diinisialisasi dengan NIL
sebelum menunjuk ke simpul pada senarai berantai.
Menambah Simpul
Untuk menambah simpul lakukan langkah-langkah berikut ini:

1. Langkah awal
Sebuah pointer baru (yang menunjuk ke simpul ‘baru’ yang akan kita sisipkan), mulamula
diciptakan.

2. Langkah penambahan
Mengalokasikan simpul baru di heap dan kemudian ditunjuk oleh pointer
baru.
Data nama dan telepon diisikan ke simpul yang tercipta.
Pointer lanjutan pada simpul yang ditunjuk oleh baru diatur agar menunjuk ke
simpul yang ditunjuk oleh pertama.
Pointer pertama diatur agar menunjuk ke simpul yang ditunjuk oleh baru
Dengan cara seperti ini maka setiap simpul baru akan menempati posisi terkiri dan
langsung ditunjuk oleh pointer pertama.

penambahan dilakukan pada Senarai berantai yang sudah ada isinya

Penambahan yang kita lakukan diatas adalah penambahan yang dilakukan pada

simpul yang paling awal, ada lagi beberapa penambahan yaitu : penambahan ditengah dan penambahan di akhir.

Menampilkan seluruh simpul
Untuk menampilkan seluruh simpul dapat dilakukan dengan mudah, caranya adalah
dengan menelusuri simpul-simpul dimulai dari simpul yang ditunjuk pertama. Perlu
diketahui penelusuran dilakukan dengan perantaraan pointer lainnya (bukan pertama).
Langkah ini dapat dilihat pada prosedur berikut ini :
procedure TampilkanSenarai(pertama : PtrSimpul);

Menghapus Simpul
Sebagai suatu struktur data yang dinamis, operasi penghapusan suatu simpul juga
dapat dilakukan pada senarai berantai. Pada penghapusan simpul ada 2 kondisi yang
perlu diperhatikan :
Simpul yang dihapus adalah simpul yang tidak memiliki pendahulu (simpul
yang paling awal (ditunjuk oleh pointer pertama)).
Simpul yang dihapus memiliki pendahulu (bukan simpul yang ditunjuk oleh
pertama).
Pada kondisi pertama, penghapusan dilakukan dengan mula-mula mengatur pointer
pertama agar menunjuk simpul yang ditunjuk oleh pointer lanjutan milik simpul yang
ditunjuk oleh pertama.

Kemudian simpul yang ditunjuk oleh PtrPosisiData dihapus dengan dispose.
Pada kondisi kedua, mula-mula pointer lanjutan milik simpul yang ditunjuk oleh
PtrPendahulu .