BLOGGER TEMPLATES - TWITTER BACKGROUNDS

Selasa, 15 Juni 2010

sorting

2.1 Sorting
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.

2.2 Bubble Sort
Bubble sort adalah salah satu metode pengurutan exchanging yang bersifat langsung dan termasuk jenis pengurutan yang paling sederhana. Nama bubble sort sendiri berasal dari sifat nilai elemen terbesar yang selalu naik ke atas (ke akhir dari list) seperti gelembung udara(bubble). Ide dari bubble sort adalah sebagai berikut :
1. Pengecekan dimulai dari elemen paling awal.
2. Elemen ke-1 dan ke-2 dari list dibandingkan.
3. Jika elemen pertama lebih besar dari elemen kedua, dilakukan pertukaran.
4. Langkah 2 dan 3 dilakukan lagi terhadap elemen kedua dan ketiga, seterusnya sampai elemen terakhir.
5. Bila sudah sampai di elemen terakhir dilakukan pengulangan lagi dari awal sampai tidak ada terjadi lagi pertukaran elemen.
6. Bila tidak ada pertukaran elemen lagi, maka elemen list terurut.
2.2.1 Algoritma
void bubble_sort(){
for(int i=1;i=i;j--){
(data[j]0) {
k = j;
}
}
swap(array[i],array[k]);
}
}

2.3.2 Contoh

2 4 6 7 5 9 3 8
2 4 6 5 7 9 3 8
2 4 5 6 7 9 3 8
2 3 4 5 6 7 9 8
2 3 4 5 6 7 8 9


2.4 Selection Sort
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.
Ide utama dari algoritma selection sort adalah memilih elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari i dimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.
Tehnik pengurutan dengan cara pemilihan elemen atau proses kerja dengan memilih elemen data terkecil untuk kemudian dibandingkan dan ditukarkan dengan elemen data awal, dst sampai deagan seluruh elemen shingga akan menghasilkan pola data yang telah di sort.
Prinsip kerja dari tehnik selection ini adalah :
1. Pengecekan dimulai data ke-1 sampai dengan data ke-n.
2. Tentukan bilangan dengan indek terkecil dari data bilangan tersebut.
3. Tukarkan bilangan dengan index terkecil tersebut dengan bilangan pertama ( i= 1 ) dari data bilangan tersebut.
4. Lakukan langkah 2 dan ke 3 untuk bilangan berikutnya ( i= i+1 ) sampai didapatkan urutan yang optimal.

2.4.1 Algoritma
void selectionSort(Object array[], int startIdx, int endIdx) {
int min;
for (int i = startIdx; i < endIdx; i++) { min = i; for (int j = i + 1; j < endIdx; j++) { if (((Comparable)array[min]).compareTo(array[j])>0) {
min = j;
}
}
swap(array[min], array[i]);
}
}
2.4.2 Contoh

2 4 6 7 5 9 3 8
2 4 6 7 5 9 3 8
2 3 6 7 5 9 4 8
2 3 4 7 5 9 6 8
2 3 4 5 7 9 6 8
2 3 4 5 6 9 7 8
2 3 4 5 6 7 9 8
2 3 4 5 6 7 8 9

2.5 Merge Sort
Sebelum mendalami algoritma merge sort, mari kita mengetahui garis besar dari konsep divide and conquer karena merge sort mengadaptasi pola tersebut.

2.5.1 Pola Divide dan Conquer
Beberapa algoritma mengimplementasikan konsep rekursi untuk menyelesaikan permasalahan. Permasalahan utama kemudian dipecah menjadi sub-masalah, kemudian solusi dari sub-masalah akan membimbing menuju solusi permasalahan utama.
Pada setiap tingkatan rekursi, pola tersebut terdiri atas 3 langkah.
1. Divide
Memilah masalah menjadi sub masalah
2. Conquer
Selesaikan sub masalah tersebut secara rekursif. Jika sub-masalah tersebut
cukup ringkas dan sederhana, pendekatan penyelesaian secara langsung akan
lebih efektif
3. Kombinasi
Mengkombinasikan solusi dari sub-masalah, yang akan membimbing menuju
penyelesaian atas permasalahan utama
2.5.2 Memahami Merge Sort
Seperti yang telah dijelaskan sebelumnya, Merge sort menggunakan pola divide and conquer. Dengan hal ini deskripsi dari algoritma dirumuskan dalam 3 langkah berpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Merge sort.
1. Divide
Memilah elemen – elemen dari rangkaian data menjadi dua bagian.
2. Conquer
Conquer setiap bagian dengan memanggil prosedur merge sort secara rekursif.
3. Kombinasi
Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan.
Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagianyang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.
Prinsip kerja merge sort adalah :
1. Kelompokkan deret bilangan ke dalam 2 bagian, 4 bagian, 8 bagian,...dst.
2. Urutkan secara langsung bilangan ke dalam kelompok tersebut.
3. Lakukan langkah diatas untuk kondisi bilangan yang lain sampai didapatkan urutan yang optimal.

2.5.3 Algoritma
void mergeSort(Object array[], int startIdx, int endIdx) {
if (array.length != 1) {
//Membagi rangkaian data, rightArr dan leftArr
mergeSort(leftArr, startIdx, midIdx);
mergeSort(rightArr, midIdx+1, endIdx);
combine(leftArr, rightArr);
}
}



2.5.4 Contoh

2 4 6 7 5 9 3 8
2 4 6 7 5 9 3 8
2 4 6 7 5 9 3 8
2 3 4 5 6 7 8 9

2.6 Quick Sort
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.
Sort dengan interasi secara urut dari posisi elemen 1, ke-2 san seterusnya. Tukarkan setiap elemen pd posisi tersebut dengan elemen lain yang nilainya memang seharusnya berada pada posisi tersebut.
Prinsip kerja dari quick sort adalah :
1. Tentukan Lower Bound (Batas Bawah) dan Upper Bound (Batas Atas).
2. Bandingka LB dengan UB.
3. Jika LB>UB. Tukar (cari operasi perbandingan yang optimal/terkecil).
4. Jika LB= leftIdx) {
pivotIdx = partition(array, leftIdx, rightIdx);
quickSort(array, leftIdx, pivotIdx-1);
quickSort(array, pivotIdx+1, rightIdx);
}
}





2.6.2 Contoh

2 4 6 7 5 9 3 8
2 3 6 7 5 9 4 8
2 3 4 7 5 9 6 8
2 3 4 5 7 9 6 8
2 3 4 5 6 9 7 8
2 3 4 5 6 7 9 8
2 3 4 5 6 7 8 9


2.7 Heap Sort
Heap Sort adalah algoritma pengurutan data berdasarkan perbandingan, dan termasuk golongan selection sort. Walaupun lebih lambat daripada quick sort pada kebanyakan mesin , tetapi heap sort mempunyai keunggulan yaitu kompleksitas algoritma pada kasus terburuk adalah n log n.

2.7.1 Metode
Heap Sort memiliki dua fungsi utama yaitu , fungsi untuk menginisialisasi heap awal dari list kontigu dengan elemen acak, dan fungsi kedua yaitu fungsi untuk meng-insert heap baru dengan mengambil node awal heap dan mempromosikan elemen lain dibawahnya untuk menggantikan posisinya. Kali ini kami fungsi pertama akan dinamakan dengan BuildHeap() dan InsertHeap() untuk fugnsi kedua.
Untuk fungsi kedua merupakan tahap kedua di mana kita akan mengambil akar pohon heap yang merupakan nilai terbesar/terkecil (tergantung penyusunan) , dan nilai ini akan diletakkan di akhir list. Kita akan meyimpan indeks pengulangan dalam var last_unsorted.

2.7.2 Algoritma
template
void Sortable_list :: heap_sort( )
/* Post: The entries of the Sortable_list have been rearranged so that their keys
are sorted into nondecreasing order.
{
Record current; // temporary storage for moving entries
int last_unsorted; // Entries beyond last_unsorted have been sorted.
build_heap( ); // First phase: Turn the list into a heap.
for (last_unsorted = count − 1; last_unsorted > 0; last_unsorted−−)
{
current = entry[last_unsorted]; // Extract the last entry from the list.
entry[last_unsorted] = entry[0]; // Move top of heap to the end
insert_heap(current, 0, last_unsorted
− 1); // Restore the heap
}
}

2.7.3 Fungsi InsertHeap()
Pada fungsi insert_heap ini akan melakukan penghapusan sebuah simpul pada heaptree, pemilihan sebuah simpul untuk ditempatkan di posisi yang lebih atas, dan menjaga tree tersebut tetap sebuah heaptree.
Langkah-langkanya ialah :
1. Setiap simpul yang dihapus(low) dicari anaknya yang memiliki kunci terbesar/terkecil(large)
2. Anak dengan kunci yang lebih besar dipromosikan ke tempat simpul yang di hapus.

3. Langkah 1 dan 2 akan di lakukan berulang kali sampai simpul yang dihapus tidak punya anak lagi atau simpul yang ingin dipromosikan lebih besar/kecil daripada anak dari simpul yang dihapus yang memiliki kunci terbesar/terkecil.

Prinsip kerja heap sort :
1. Bentuk pohon heap dengan prosedur yang ada.
2. Laksanankan sort, ulangi sampai dengan langkah 10; Q=N, N-1,…..,2.
3. Tentukan nilai record: K[I]←→K[Q].
4. Berikan harga awal I←1; Key← K[I]; J←2.
5. Dapatkan indek dari harga terbesar anak dari record baru.
If J+1K[J] then
J=J+1
6. Buat kembali heap baru., Ulangi sampai langkah 10 apabila JKey.
7. Tukarkan harga record: K[I]←→K[J]
8. Dapatkan anak berikutnya.
I←J; J←Q+1
9. Dapatkan indeks dari anak dengan harga terbesar berikutnya
if J+1K[J] then
J=J+1
Else
if J> N then J=N
10. Copykan record ke dalam tempatnya yang cocok
K[I]←Key I return

Berikut kode program fungsi insert_heap() dalam bahasa c ++ :
template
void Sortable_list :: insert_heap(const Record ¤t, int low, int high)
/* Pre: The entries of the Sortable_list between indices low Ç 1 and high, inclusive,
form a heap. The entry in position low will be discarded.
Post: The entry current has been inserted into the Sortable_list and the entries
rearranged so that the entries between indices low and high, inclusive,
form a heap.
*/
{
int large; // position of child of entry[low] with the larger key
large = 2 * low + 1; // large is now the left child of low.
while (large <= high) { if (large < high && entry[large] < entry[large + 1]) large++; // large is now the child of low with the largest key. if (current >= entry[large]){
break; // current belongs in position low.
}
else { // Promote entry[large] and move down the tree.
entry[low] = entry[large];
low = large;
large = 2 * low + 1;
}
}
entry[low] = current; }

Contoh :

2.7.4 Fungsi BuildHeap()
Pada bagian build heap ini kiat kan menginisialisasi heap awal dari list yang acak. Untuk melakukan hal tersebut pertama-tama ingat bahwa 2 pohon dengan satu simpul secara otomatis, akan memenuhi ketentuan dari sebuah heap, dengan demikian kita tidak perlu khawatir dengan daun dari pohon; yaitu paruh kedua dari list. Jika kita memulai dari tengah list sampai ke awal, kita dapat menggunakan fungsi insert_heap untuk memasukkan setiap masukan ke bagian heap yang terdiri dari semua masukan yang masuk kemudian yang kemudian membentuk heap yang sempurna.
Berikut ini fungsi build_heap yang ditulis dalam bahasa C++.
template
void Sortable_list :: build_heap( )
/* Post: The entries of the Sortable_list have been rearranged so that it becomes
a heap.
*/and insert_heap. */
{
int low; // All entries beyond the position low form a heap.
for (low = count/2 - 1; low >= 0; low--) {
Record current = entry[low];
insert_heap(current, low, count - 1);
}
}

STACK DAN QUEUE

I. STACK DAN QUEUE DENGAN LINKED LIST
Pengertian Linked list :
• sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari dua bagian
• struktur berupa rangkaian elemen saling berkait dimana setiap elemen dihubungkan elemen lain melalui pointer. Pointer adalah alamat elemen. Penggunaan pointer untuk mengacu elemen berakibat elemen-elemen bersebelahan secara logik walau tidak bersebelahan secara fisik di memori.
Bentuk Umum :
Infotype sebuah tipe terdefinisi yang menyimpan informasi sebuah elemen list
Next address dari elemen berikutnya (suksesor)
Jika L adalah list, dan P adalah address, maka alamat elemen pertama list L dapat diacu dengan notasi :
Sebelum digunakan harus dideklarasikan terlebih dahulu :
Elemen yang diacu oleh P dapat dikonsultasi informasinya dengan notasi :
Beberapa Definisi :
1. List l adalah list kosong, jika First(L) = Nil
2. Elemen terakhir dikenali, dengan salah satu cara adalah karena
Next(Last) = Nil
Nil adalah pengganti Null, perubahan ini dituliskan dengan #define Nil Null
Single Linked List
Pada gambar di atas tampak bahwa sebuah data terletak pada sebuah lokasi memori area. Tempat yang disediakan pada satu area memori tertentu untuk menyimpan data dikenal dengan sebutan node atau simpul. Setiap node memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, dengan demikian hanya diperlukan sebuah variabel pointer. Susunan berupa untaian semacam ini disebut Single Linked List (NULL memilik nilai khusus yang artinya tidak menunjuk ke mana-mana. Biasanya Linked List pada titik akhirnya akan menunjuk ke NULL).
Pembuatan Single Linked List dapat menggunakan 2 metode:
• LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)
• FIFO (First In First Out), aplikasinya : Queue (Antrean)
Double Linked List
Salah satu kelemahan single linked list adalah pointer (penunjuk) hanya dapat bergerak satu arah saja, maju/mundur, atau kanan/kiri sehingga pencarian data pada single linked list hanya dapat bergerak dalam satu arah saja. Untuk mengatasi kelemahan tersebut, dapat menggunakan metode double linked list. Linked list ini dikenal dengan nama Linked list berpointer Ganda atau Double Linked List.
Merupakan double linked list yang simpul terakhirnya menunjuk ke simpul terakhirnya menunjuk ke simpul awalnya menunjuk ke simpul akhir sehingga membentuk suatu lingkaran.
Operasi-Operasi yang ada pada Linked List
• Insert
Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.
• IsEmpty
Fungsi ini menentukan apakah linked list kosong atau tidak.
• Find First
Fungsi ini mencari elemen pertama dari linked list
• Find Next
Fungsi ini mencari elemen sesudah elemen yang ditunjuk now
• Retrieve
Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.
• Update
Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu
• Delete Now
Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut.
• Delete Head
Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.
• Clear
Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.
A. STACK DENGAN SINGLE LINKED LIST
Selain implementasi stack dengan array seperti telah dijelaskan sebelumnya, stack daat diimplementasikan dengan single linked list. Keunggulannya dibandingkan array adalah penggunaan alokasi memori yang dinamis sehingga menghindari pemborosan memori.
Misalnya pada stack dengan array disediakan tempat untuk stack berisi 150 elemen, sementara ketika dipakai oleh user stack hanya diisi 50 elemen, maka telah terjadi pemborosan memori untuk sisa 100 elemen, yang tak terpakai. Dengan penggunaan linked list maka tempat yang disediakan akan sesuai dengan banyaknya elemen yang mengisi stack.
Dalam stack dengan linked list tidak ada istilah full, sebab biasanya program tidak menentukan jumlah elemen stack yang mungkin ada (kecuali jika sudah dibatasi oleh pembuatnya). Namun demikian sebenarnya stack ini pun memiliki batas kapasitas, yakni dibatasi oleh jumlah memori yang tersedia.
Operasi-operasi untuk Stack dengan Linked List
• IsEmpty
Fungsi memeriksa apakah stack yang adamasih kosong.
• Push
Fungsi memasukkan elemen baru ke dalam stack. Push di sini mirip dengan insert dalam single linked list biasa.
• Pop
Fungsi ini mengeluarkan elemen teratas dari stack.
• Clear
Fungsi ini akan menghapus stack yang ada.
B. QUEUE DENGAN DOUBLE LINKED LIST
Selain menggunakan array, queue juga dapat dibuat dengan linked list. Metode linked list yang digunakan adalah double linked list.
Operasi-operasi Queue dengan Double Linked List
• IsEmpty
Fungsi IsEmpty berguna untuk mengecek apakah queue masih kosong atau sudah berisi data. Hal ini dilakukan dengan mengecek apakah head masih menunjukkan pada Null atau tidak. Jika benar berarti queue masih kosong.
• IsFull
Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih bisa menampung data dengan cara mengecek apakah Jumlah Queue sudah sama dengan MAX_QUEUE atau belum. Jika benar maka queue sudah penuh.
• EnQueue
Fungsi EnQueue berguna untuk memasukkan sebuah elemen ke dalam queue (head dan tail mula-mula meunjukkan ke NULL).
• DeQueue
Procedure DeQueue berguna untuk mengambil sebuah elemen dari queue. Hal ini dilakukan dengan cara menghapus satu simpul yang terletak paling depan (head).
II. STACK DAN QUEUE DENGAN ARRAY
1. STACK DENGAN MENGGUNAKAN ARRAY
Pengertian Stack
• Stack atau tumpukan adalah suatu stuktur data yang penting dalam pemrograman
• Bersifat LIFO (Last In First Out)
• Benda yang terakhir masuk ke dalam stack akan menjadi benda pertama yang dikeluarkan dari stack
• Contohnya, karena kita menumpuk Compo di posisi terakhir, maka Compo akan menjadi elemen teratas dalam tumpukan. Sebaliknya, karena kita menumpuk Televisi pada saat pertama kali, maka elemen Televisi menjadi elemen terbawah dari tumpukan. Dan jika kita mengambil elemen dari tumpukan, maka secara otomatis akan terambil elemen teratas, yaitu Compo juga.
Operasi-operasi/fungsi Stack
• Push : digunakan untuk menambah item pada stack pada tumpukan paling atas
• Pop : digunakan untuk mengambil item pada stack pada tumpukan paling atas
• Clear : digunakan untuk mengosongkan stack
• IsEmpty : fungsi yang digunakan untuk mengecek apakah stack sudah kosong
• IsFull : fungsi yang digunakan untuk mengecek apakah stack sudah penuh
Stack with Array of Struct
• Definisikan Stack dengan menggunakan struct
• Definisikan MAX_STACK untuk maksimum isi stack
• Buatlah variabel array data sebagai implementasi stack secara nyata
• Deklarasikan operasi-operasi/function di atas dan buat implemetasinya
Deklarasi MAX_STACK
#define MAX_STACK 10 //hati-hati mulai dari 0 jadi 0-9
Deklarasi STACK dengan struct dan array data
typedef struct STACK{
int top;
char data[10][10]; //misalkan : data adalah array of string
//berjumlah 10 data, masing-masing string
//menampung maksimal 10 karakter
};
Deklarasi/buat variabel dari struct
STACK tumpuk;
Inisialisasi Stack
• Pada mulanya isi top dengan -1, karena array dalam C dimulai dari 0, yang berarti stack adalah KOSONG!
• Top adalah suatu variabel penanda dalam STACK yang menunjukkan elemen teratas Stack sekarang. Top Of Stack akan selalu bergerak hingga mencapai MAX of STACK sehingga menyebabkan stack PENUH!
• Ilustrasi stack pada saat inisialisasi:
Fungsi IsFull
• Untuk memeriksa apakah stack sudah penuh?
• Dengan cara memeriksa top of stack, jika sudah sama dengan
MAX_STACK-1 maka full, jika belum (masih lebih kecil dari MAX_STACK-1) maka belum full
• Ilustrasi:
Fungsi IsEmpty
• Untuk memeriksa apakah stack masih kosong?
• Dengan cara memeriksa top of stack, jika masih -1 maka berarti stack masih kosong!
• Program:
Fungsi Push
• Untuk memasukkan elemen ke stack, selalu menjadi elemen teratas stack
• Tambah satu (increment) nilai top of stack terlebih dahulu setiap kali ada penambahan elemen stack, asalkan stack masih belum penuh, kemudian isikan nilai baru ke stack berdasarkan indeks top of stack setelah ditambah satu (diincrement)
• Ilustrasinya:
Fungsi Pop
• Untuk mengambil elemen teratas dari stack.
• Ambil dahulu nilai elemen teratas stack dengan mengakses top of stack, tampilkan nilai yang akan diambil terlebih dahulu, baru didecrement nilai top of stack sehingga jumlah elemen stack berkurang
• Ilustrasinya:
Programnya:
Fungsi Print
• Untuk menampilkan semua elemen-elemen stack
• Dengan cara looping semua nilai array secara terbalik, karena kita harusmengakses dari indeks array tertinggi terlebih dahulu baru ke indeks yang kecil!
Program:
2. QUEUE DENGAN MENGGUNAKAN ARRAY
• Queue = Antrian
• Elemen yang pertama kali masuk ke antrian akan keluar pertama kalinya
• DEQUEUE adalah mengeluarkan satu elemen dari suatu Antrian
• Antrian dapat dibuat dengan menggunakan: Liniear Array dan Circular
Array
QUEUE DENGAN LINIEAR ARRAY
• Terdapat satu buah pintu masuk di suatu ujung dan satu buah pintu keluar
di ujung satunya
• Sehingga membutuhkan variabel Head dan Tail
• DEKLARASI QUEUE
• OPERASI-OPERASI PADA QUEUE
• - Create()
• o Untuk menciptakan dan menginisialisasi Queue
• o Dengan cara membuat Head dan Tail = -1
• - IsEmpty()
• o Untuk memeriksa apakah Antrian sudah penuh atau belum
• o Dengan cara memeriksa nilai Tail, jika Tail = -1 maka empty
• o Kita tidak memeriksa Head, karena Head adalah tanda untuk kepala
• antrian (elemen pertama dalam antrian) yang tidak akan berubahubah
• o Pergerakan pada Antrian terjadi dengan penambahan elemen
• Antrian kebelakang, yaitu menggunakan nilai Tail
• - IsFull()
• o Untuk mengecek apakah Antrian sudah penuh atau belum
• o Dengan cara mengecek nilai Tail, jika Tail >= MAX-1 (karena MAX-1
• adalah batas elemen array pada C) berarti sudah penuh
• - Enqueue(data)
• o Untuk menambahkan elemen ke dalam Antrian, penambahan
• elemen selalu ditambahkan di elemen paling belakang
• o Penambahan elemen selalu menggerakan variabel Tail dengan cara
• increment counter Tail
• - Dequeue()
• o Digunakan untuk menghapus elemen terdepan/pertama dari Antrian
• o Dengan cara mengurangi counter Tail dan menggeser semua
• elemen antrian kedepan.
• o Penggeseran dilakukan dengan menggunakan looping
• - Clear()
• o Untuk menghapus elemen-elemen Antrian dengan cara membuat
• Tail dan Head = -1
• o Penghapusan elemen-elemen Antrian sebenarnya tidak menghapus
• arraynya, namun hanya mengeset indeks pengaksesan-nya ke nilai
• -1 sehingga elemen-elemen Antrian tidak lagi terbaca
• - Tampil()
• o Untuk menampilkan nilai-nilai elemen Antrian
• o Menggunakan looping dari head s/d tail
Perbandingan Antara
Stack-Queue Dengan Linked List Vs Stack-Queue Dengan Array
1. Stack Dengan Linked List VS Stack Dengan Array
Berikut ini adalah perbandingan algoritma pada operasi-operasi dasar dari Stack Dengan Linked List dan Stack Dengan Array, dengan menggunakan bahasa pemrograman Pascal

Stack Dengan Linked List Stack Dengan Array
operasi : create()
procedure create;
begin
top := nil ;
end; procedure create;
begin
top := 0;
end;
operasi : empty()
function empty : boolean;
begin
empty := false ;
if top = nil then empty := true ;
end; function empty : boolean;
begin
empty := false ;
if top = 0 then empty := true ;
end;
operasi : full()
tidak ada istilah full pada stack.
program tidak menentukan jumlah elemen stack yang mungkin ada. kecuali dibatasi oleh pembuat program dan jumlah memory yang tersedia. tempat akan sesuai dengan banyaknya elemen yang mengisi stack. function full : boolean;
begin
full := false ;
if top = max then full := true ;
end;
operasi : push()
procedure push (elemen : typedata) ;
var now:point ;
begin
now(now) ;
now^.isi := elemen ;
if empty then
now^.next := nil ;
else
now^.next := top ;
top := now ;
end; procedure push (elemen : typedata) ;
begin
if not full then
begin
top := top + 1 ;
stack [top] := elemen ;
end;
end;
operasi : pop()
procedure pop (var elemen : typedata) ;
var now:point ;
begin
if not empty then
begin
elemen := now^.isi ;
now := top ;
top := top^.next ;
dispose(now) ;
end;
end; procedure pop (elemen : typedata) ;
begin
if not empty then
begin
elemen := stack [top] ;
top := top – 1 ;
end;
end;
operasi : clear
procedure clear ;
var trash : typedata ;
begin
while not empty do pop(trash) ;
end; procedure clear ;
begin
top := 0 ;
end;
PEMBAHASAN
Dari perbandingan diatas, dapat dilihat pada linked list tidak dikenal istilah full. Hal ini berkaitan dengan penggunaan alokasi memori pada linked list yang lebih dinamis jika dibandingkan dengan array, sehingga pemborosan memory dapat dihindari. Program tidak menentukan jumlah elemen stack yang mungkin ada. Kecuali dibatasi oleh pembuat program dan jumlah memory yang tersedia. Tempat akan sesuai dengan banyaknya elemen yang mengisi stack.
2. Queue Dengan Linked List VS Queue Dengan Array
Implementasi queue menggunakan array
• Implementasi sederhana
• Ukuran memori harus ditentukan ketika sebuah objek queue dideklarasikan
• Pemborosan tempat (memori) ketika menggunakan jumlah data yang lebih sedikit dari alokasi memori
• Tidak dapat menambahkan data melebihi maksimal ukuran array yang telah dideklarasikan
Implementasi queue menggunakan linked list
• Pengalokasian memori dinamis
• Menggunaka 2 buah pionter, qFront dan qRear, untuk menandai posisi depan dan belakang dari queue

Minggu, 30 Mei 2010

Graph adalah kumpulan dari titik ( node ) dan garis dimana pasangan-pasangan titik ( node ) tersebut dihubungkan oleh segmen garis. Node ini biasa disebut simpul (verteks) dan segmen garis disebut ruas (edge).

Simpul dan ruas dalam graph dapat diperluas dengan penambahan informasi. Sebagai contoh, simpul bisa diberi nomor atau label dan ruas dapat diberi nilai juga. Perluasan dengan pemberian informasi ini sangat berguna dalam penggunaan graph untuk banyak aplikasi komputer. Contoh, graph dengan simpul yang merepresentasikan kota dan ruas merepresentasikan jarak yang ditempuh diantara kota-kota tsb. (atau harga tiket pesawat antara kota-kota tsb.) , dapat digunakan sebagai “transportation network” untuk mempelajari total jarak (atau harga) dari suatu perjalanan dengan banyak kota pemberhentian. Satu kemungkinan pertanyaan yang bisa muncul adalah “Jalur mana yang terpendek dengan satu atau lebih tempat pemberhentian, yang menghubungkan kota tertentu menuju kota tertentu lainnya dalam transportation network tersebut ?”.
Dalam kehidupan sehari-hari maupun dalam bidang akademis banyak persoalan yang dimodelkan dengan graph. Graph dipakai untuk membantu pemecahan masalah. Dari model graph yang dibuat, suatu masalah dapat dipahami menjadi lebih mudah. Untuk kemudian diturunkan metode pemecahannya.



Kelahiran Teori Graph

Gbr1. Jembatan Konigsberg
Menurut catatan sejarah, masalah jembatan Konigsberg adalah masalah yang pertama kali menggunakan graph (th. 1736). Masalah Jembatan Konigsberg adalah : “ apakah mungkin melalui tujuh buah jembatan masing-masing tepat satu kali. Dan kembali lagi ke tempat semula ?” . Tak seorangpun yang dapat memecahkan masalah ini. Barulah Euler yang pertama kali menemukan jawabannya. Ia memodelkan masalah dengan memodelkannya ke dalam graph. Daratan (titik-titik yang dihubungkan oleh jembatan) dinyatakannya sebagai simpul (vertex) dan jembatan sebagai sisi. Graph dibuat oleh Euler diperlihatkan pada gambar dibawah atas.
Jawabannya adalah : Orang tidak mungkin berjalan melalui ketujuh jembatan masing-masing satu kali dan kembali ke tempat asal keberangkatan. Singkatnya, tidak terdapat siklus Euler pada Graph tersebut.
Graph yang memenuhi kondisi diatas tersebut kemudian dikenal dengan nama Graph Euler dan perjalanannya disebut perjalanan euler.
Perjalanan Euler adalah :
Perjalanan dari suatu simpul kembali ke simpul tersebut dengan melalui setiap ruas tepat satu kali.
Perjalanan Euler akan terjadi, jika :
- Graf terhubung.
- Banyaknya ruas yang datang pada setiap simpul adalah genap
Jenis Graph
Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graph, maka graph digolongkan menjadi dua jenis:
1. Graph sederhana (simple graph).
Graph yang tidak mengandung gelung maupun sisi-ganda dinamakan graph sederhana.
2. Graph tak-sederhana (unsimple-graph/multigraph).
Graph yang mengandung ruas ganda atau gelung dinamakan graph tak-sederhana (unsimple graph atau multigrapf).
Berdasarkan jumlah simpul pada suatu graph, maka secara umum graph dapat digolongkan menjadi dua jenis:
1. Graph berhingga (limited graph)
Graph berhingga adalah graph yang jumlah simpulnya, n, berhingga.
2. Graph tak-berhingga (unlimited graph)
Graph yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graph tak-berhingga.
Berdasarkan orientasi arah pada sisi, maka secara umum graph dibedakan atas 2 jenis:
1. Graph tak-berarah (undirected graph)
Graph yang sisinya tidak mempunyai orientasi arah disebut graph tak-berarah.
2. Graph berarah (directed graph atau digraph)

Graph adalah kumpulan dari titik ( node ) dan garis dimana pasangan-pasangan titik ( node ) tersebut dihubungkan oleh segmen garis. Node ini biasa disebut simpul (verteks) dan segmen garis disebut ruas (edge).

Simpul dan ruas dalam graph dapat diperluas dengan penambahan informasi. Sebagai contoh, simpul bisa diberi nomor atau label dan ruas dapat diberi nilai juga. Perluasan dengan pemberian informasi ini sangat berguna dalam penggunaan graph untuk banyak aplikasi komputer. Contoh, graph dengan simpul yang merepresentasikan kota dan ruas merepresentasikan jarak yang ditempuh diantara kota-kota tsb. (atau harga tiket pesawat antara kota-kota tsb.) , dapat digunakan sebagai “transportation network” untuk mempelajari total jarak (atau harga) dari suatu perjalanan dengan banyak kota pemberhentian. Satu kemungkinan pertanyaan yang bisa muncul adalah “Jalur mana yang terpendek dengan satu atau lebih tempat pemberhentian, yang menghubungkan kota tertentu menuju kota tertentu lainnya dalam transportation network tersebut ?”.
Dalam kehidupan sehari-hari maupun dalam bidang akademis banyak persoalan yang dimodelkan dengan graph. Graph dipakai untuk membantu pemecahan masalah. Dari model graph yang dibuat, suatu masalah dapat dipahami menjadi lebih mudah. Untuk kemudian diturunkan metode pemecahannya.



Kelahiran Teori Graph

Gbr1. Jembatan Konigsberg
Menurut catatan sejarah, masalah jembatan Konigsberg adalah masalah yang pertama kali menggunakan graph (th. 1736). Masalah Jembatan Konigsberg adalah : “ apakah mungkin melalui tujuh buah jembatan masing-masing tepat satu kali. Dan kembali lagi ke tempat semula ?” . Tak seorangpun yang dapat memecahkan masalah ini. Barulah Euler yang pertama kali menemukan jawabannya. Ia memodelkan masalah dengan memodelkannya ke dalam graph. Daratan (titik-titik yang dihubungkan oleh jembatan) dinyatakannya sebagai simpul (vertex) dan jembatan sebagai sisi. Graph dibuat oleh Euler diperlihatkan pada gambar dibawah atas.
Jawabannya adalah : Orang tidak mungkin berjalan melalui ketujuh jembatan masing-masing satu kali dan kembali ke tempat asal keberangkatan. Singkatnya, tidak terdapat siklus Euler pada Graph tersebut.
Graph yang memenuhi kondisi diatas tersebut kemudian dikenal dengan nama Graph Euler dan perjalanannya disebut perjalanan euler.
Perjalanan Euler adalah :
Perjalanan dari suatu simpul kembali ke simpul tersebut dengan melalui setiap ruas tepat satu kali.
Perjalanan Euler akan terjadi, jika :
- Graf terhubung.
- Banyaknya ruas yang datang pada setiap simpul adalah genap
Jenis Graph
Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graph, maka graph digolongkan menjadi dua jenis:
1. Graph sederhana (simple graph).
Graph yang tidak mengandung gelung maupun sisi-ganda dinamakan graph sederhana.
2. Graph tak-sederhana (unsimple-graph/multigraph).
Graph yang mengandung ruas ganda atau gelung dinamakan graph tak-sederhana (unsimple graph atau multigrapf).
Berdasarkan jumlah simpul pada suatu graph, maka secara umum graph dapat digolongkan menjadi dua jenis:
1. Graph berhingga (limited graph)
Graph berhingga adalah graph yang jumlah simpulnya, n, berhingga.
2. Graph tak-berhingga (unlimited graph)
Graph yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graph tak-berhingga.
Berdasarkan orientasi arah pada sisi, maka secara umum graph dibedakan atas 2 jenis:
1. Graph tak-berarah (undirected graph)
Graph yang sisinya tidak mempunyai orientasi arah disebut graph tak-berarah.
2. Graph berarah (directed graph atau digraph)

array

Array adalah suatu tipe data terstruktur yang terdapat dalam memori yang
terdiri dari sejumlah elemen (tempat) yang mempunyai tipe data yang sama dan
merupakan gabungan dari beberapa variabel sejenis serta memiliki jumlah
komponen yang jumlahnya tetap.
Fungsi array adalah sebagai langkah efisiensi penggunan memori komputer, sebab data elemen array dialokasikan pada suatu deretan sel memori tertentu. Selain itu agar memudahkan programmer dalam menyusun aplikasi yang berhubungan dengan banyak data terutama dalam masalah pencarian dan pengurutan data secara cepat.

Cara mendeklarasikan array diawali dengan nama variabel array diikuti dengan indeks array yang dituliskan didalam tanda “[]” , diikuti dengan kata cadangan of dan tipe data yang dibutuhkan.
Tiga hal yang harus diketahui dalam mendeklarasi array:
• Type data array
• Nama variable array
• Subkrip / index array
Cara alokasi penggunaan array dibagi menjadi dua:
a) Array Static (Static Array)
Array static adalah model pendeklarasian array dimana tipe data yang digunakan mempunyai nilai yang tetap. Nilai yang digunakan untuk menentukan jangkauan pada umumnya bernilai integer. Array Static juga bisa disebut Array dengan deklarasi tipe indeks subrange integer.
b) Array Dinamis (Dynamic arrays)
Larik atau array dinamis merupakan array yang tidak mempunyai suatu jangkauan atau ukuran yang tetap. Tetapi ketika program dijalankan maka memori untuk suatu array dinamis direalokasikan ketika kita menugaskan suatu nilai kepada array. Dynamic-Array jenis ditandai oleh konstruksi (menyangkut) format.

Mendefinisikan array artinya menentukan besar array yang diinginkan. Setelah pendefinisian array, maka memori akan dialokasikan untuk menyimpan data dari array. Besar memori yang dialokasikan tergantung dari tipe data variabel array dan jumlah elemen array yang didefinisikan.
Keunggulan dan Kelemahan Array adalah
a. Keunggulan array adalah sebagai berikut:
• Array sangat cocok untuk mengakses acak. Sembarangan elemen di array acak secara langsung tanpa melalui elemen-elemen lain.
• Jika berada di suatu suatu elemen, maka sangat mudah menelusuri keelemen-elemen tetangga baik elemen pendahulu atau elemen penerus.
• Jika elemen-elemen array adalah nilai-nilai independen dan seluruhnya harus terjaga, maka penggunaan penyimpanannya sangat efisien,
• Sebagai tipe data dibandingkan dengan penggunaan tipe data yang lain adalah kemampuannya yang dapat mengumpulkan beberapa data yang bertipe sama dalam satu variabel, sehingga dalam pembuatan program yang terdiri dari beberapa tipe yang sama, tidak membutuhkan banyak variable.
b. Kelemahan array adalah sebagai berikut:
• Array harus bertipe homogen. Kita tidak dapat mempunyai array dimana satu elemen adlah karakter, elemen lain bilangan, dan elemen lain adalah tipe-tipe lain.
• Kebanyakan bahasa pemrograman mengimplementasikan array static yang sulit diubah ukurannya di waktu eksekusi. Bila penambahan dan pengurangan terjadi terus menerus, maka representasi statis.
• Tidak efisien dalam penggunaan memory.
• Pada suatu aplikasi, representasi statis tidak dimungkinkan..
Jenis-jenis array adalah
a) Array Dimensi Satu (One Dimensional Array)
Merupakan sebuah variabel yang menyimpan sekumpulan data yang memiliki tipe sama dan elemen yang akan diakses hanya melalui 1 indeks atau subskrip.
b) Array Dimensi Dua (Two Dimensional Array)
Merupakan sebuah variabel yang menyimpan sekumpulan data yang memiliki type sama dan elemen yang akan diakses melalui 2 indeks atau subskrip yaitu indeks baris dan indeks kolom.
c) Array multidimen
Selain array satu dimensi dan array dua dimensi, dapat juga membuat array multidimensi pada Java. Array multidimensi merupakan array yang terdiri dari array yang tidak terbatas hanya dua dimensi saja.

Minggu, 11 April 2010

di abil dari nicky

Array merupakan kumpulan data dimana setiap elemen memakai nama yang sama dan bertipe sama.  Pada array, setiap elemen diakses dengan membedakan indeksnya.  Contoh Array :

Misal nya ada Variabel array A yang terbagi menjadi  5 bagian   yaitu  :

23      15         45        12        14

A[0]   A[1]    A[2]    A[3]    A[4]

masing-masing nilai di setiap lokasi mempunyai identitas yang sama yaitu A dan nomor indeks yang ditulis di dalam tanda kurung siku ‘[..]‘.  sehingga terlihat bahwa : A[0] terisi nilai 23 atau biasa ditulis A[0]=23, A[1]=15, A[2]=45, A[3]=12, A[4]=14.

Jenis Array

1. Array Dimensi satu

Array dimensi satu adalah suatu variabel yang terbagi atas beberapa baris atau beberapa kolom.  Banyaknya indeks yang menandakan alamat pada variabel array ini hanya satu saja, yaitu yang menandakan baris ke-  atau kolom ke-.

Deklarasi array :     nama_variabel [ukuran]

dengan Type  menyatakan jenis elemen array (int, char, unsigned dan lain-lain)

Ukuran  menyatakan jumlah maksimal elemen array

Contoh :   int   A[10];      –> berarti Varibel A terbagi menjadi 10 baris/kolom dengan type integer

Untuk menginputkan nilai, mengoperasikan dan menampilkan nilai pada variabel array, dapat dideklarasikan satu per satu atau menggunakan fungsi perulangan agar lebih simple dalam penulisan programnya.

Contoh Program :

#include
#include
main()
{  int  A[10], i;
for(i=0;i<=9;i++)
A[i]=i+1;
for(i=0;i<=9;i++)
cout<<<”     “;
getch();
}

2. Array Dimensi Dua

Array dimensi dua adalah variabel array yang terbagi berdasarkan baris dan kolom. Banyaknya indeks yang menandakan alamat pada array ini ada dua yaitu menunjuk  (baris, kolom) ke-

Deklarasi Array dimensi dua :      nama_variabel[ukuran_baris][ukuran_kolom]

dengan                  type    adalah type data pada array

ukuran baris adalah banyaknya pembagian baris pada array

ukuran kolom adalah banyaknya pembagian kolom pada array

Contoh array dimensi dua adalah matrik (merupakan susunan angka yang ditulis berdasarkan baris dan kolom)

Program :

#include

#include

main()

{  int  A[10][10], i,j ;

for(i=0;i<=9;i++)

{ for(j=1;j<=9;j++)

cin>>A[i][j]; }

for(i=0;i<=9;i++)

{  {for(j=0;j<=9;j++)

cout<<<”      “;

} cout<

getch();

}