Kode Huffman pada dasarnya merupakan kode Initialize model prefiks (prefix code) yang merupakan himpunan yang berisi sekumpulan kode biner. Kode prefiks direpresentasikan sebagai pohon biner berlabel dimana setiap sisi diberi label 0 (cabang kiri) atau 1 (cabang kanan).
Rangkaian bit yang terbentuk pada setiap lintasan dari akar ke daun merupakan kode prefiks untuk karakter yang berpadanan.
Kode ini pun memiliki berbagai macam variasi antara lain :
1. Adaptive kode Huffman
2. Length-Limited kode Huffman
3. N-Ary Huffman Template Algoritma
4. Huffman With Unequal Letter Costs
1. Macam-macam Variasi Kode Huffman
A. Adaptive kode Huffman
Metode Adaptive digunakan pada saat pembaharuan (update) model algoritma baru baik dari proses kompresi maupun dekompresi
Konsep Dasar :
Encoder :
Initialize_model
Repeat for each character
{
Encode character
Update_model
}
Decoder
Initialize_model
Repeat for each character
{
Decode character
Update_model
}
Masalahnya adalah bagaimana meng-update model algoritma yang terdiri dari menambah jumlah dan mengupdate pohon Huffman. Caranya adalah dengan meng-update bagian pohon di mana terjadi proses pemampatan/nirmampat.
Pohon Huffman diinisialisasikan dengan simpul single yang dikenal dengan Not-Yet-Transmitted (NYT) Code yang dikirimkan setiap kali ditemukan karakter baru. Algoritma bekerja dengan penomoran yang unik pada simpul dengan jumlah daun yang berbeda.
Langkah-langkah peng-update-an model
1. Jika kode yang pertama kali ditemukan adalah NYT, maka tambahkan dua simpul pada simpul NYT. Satu simpul sebagai simpul NYT dan simpul yang lain sebagai daun. Tambahkan jumlah daun. Jika bukan NYT, langsung menuju daun.
2. Jika pada blok tidak terdapat angka tertinggi, tukarkan dengan angka tertinggi pada blok.
3. Tambahkan jumlah dari simpul tersebut.
4. Periksa apakah simpul tersebut merupakan simpul akar. Jika bukan pergi ke simpul parent.
B. Length-Limited Huffman Coding
Variasi Huffman ini digunakan untuk mendapatkan jarak kedalaman terkecil dari suatu simbol, dengan batasan bahwa panjang masing-masing yang dimasukkan tidak kurang dari nilai konstanta yang diberikan. Metode ini biasanya digunakan pada GNU gzip.
Langkah-langkah dalam Metode Length-Limited Huffman adalah :
1. Memilih dua atau lebih simbol yang ingin dimampatkan
2. Gabungkan simbol-simbol tersebut dan gantikan dengan pseudo-symbol beserta frekuensinya.
3. Lakukan langkah di atas secara Literatif sampai semua simpul yang ada menjadi satu simpul akar.
4. Jika simpul-simpul tersebut memiliki frekuensi yang sama, maka pilihlah simpul dengan kedalaman terpendek.
C. Binary Huffman Template Algorima
Algoritma ini sebenarnya mirip dengan algoritma Huffman biasa. Bedanya, pohon Huffman yang digunakan dalam algoritma ini memiliki lebih dari dua akar (0 dan 1). Sementara dengan Huffman template algorithm, memungkinkan untuk menggunakan ukuran non-numerik (ukuran selain biaya dan frekuensi).
D. Huffman With Unequal Letter Costs
Pada metode ini terdapat suatu permasalahan dimana suatu set kode yang terdiri dari beberapa huruf dengan frekuensi kemunculan dan biaya (cost) yang berbeda. Metode ini ditujukan untuk mencari kode prefiks (prefix code) dan menghitung biaya minimumnya (minimum cost). Prefiks Kode merupakan sekumpulan kode yang prefix-free. Biaya (cost ) dari ini merupakan jumlah biaya dari masing-masing huruf pada kode tersebut.
Langkah-langkah umum metode Kode Huffman with Unequal Letter Cost :
1. Mencari kode K-Prefiks yang optimal.
2. Mengubah kode K-Prefiks menjadi kode prefiks yang optimal.
3. Setelah didapat kode hasil kemudian hitung biaya (cost)-nya.
Kesimpulan
Kode Huffman ternyata memiliki banyak variasi, di antaranya adalah Kode Adaptive Huffman,Kode Length-limited Huffman, n-ary Huffman template algoritma, dan Kode Huffman dengan unequal letter costs. Berbagai teknik ini dapat digunakan pada aplikasi yang berbeda-beda, tetapi umumnya digunakan untuk pemampatan data. Hal ini wajar saja terjadi karena inti dari seluruh variasi teknik ini adalah sama dengan kode Huffman, yaitu memecahkan permasalahan optimasi.
Friday, March 19, 2010
Tree dalam Heap Sort
Tree Dalam Heap Sort
2.1 Pengertian Heap
Adalah struktur data yang berbentuk pohon yang memenuhi sifat-sifat heap yaitu jika B adalah anak dari A, maka nilai yang tersimpan di simpul A lebih besar atau sama dengan nilai yang tersimpan di simpul B. Hal ini mengakibatkan elemen dengan nilai terbesar selalu berada pada posisi akar, dan heap ini disebut max heap. (Bila perbandingannya diterbalikkan yaitu elemen terkecilnya selalu berada di simpul akar, heap ini disebut adalah min heap). Karena itulah, heap biasa dipakai untuk mengimplementasikan prioriti queue.
Operasi-operasi yang digunakan untuk heap adalah :
• Delete-max atau delete-min: menghapus simpul akar dari sebuah max atau min heap.
• Increase-key atau decrease-key: mengubah nilai yang tersimpan di suatu simpul.
• Insert: menambahkan sebuah nilai ke dalam heap.
• Merge: menggabungkan dua heap untuk membentuk sebuah heap baru yang berisi semua elemen pembentuk heap tersebut.
2.1 Pengertian Heap
Adalah struktur data yang berbentuk pohon yang memenuhi sifat-sifat heap yaitu jika B adalah anak dari A, maka nilai yang tersimpan di simpul A lebih besar atau sama dengan nilai yang tersimpan di simpul B. Hal ini mengakibatkan elemen dengan nilai terbesar selalu berada pada posisi akar, dan heap ini disebut max heap. (Bila perbandingannya diterbalikkan yaitu elemen terkecilnya selalu berada di simpul akar, heap ini disebut adalah min heap). Karena itulah, heap biasa dipakai untuk mengimplementasikan prioriti queue.
Operasi-operasi yang digunakan untuk heap adalah :
• Delete-max atau delete-min: menghapus simpul akar dari sebuah max atau min heap.
• Increase-key atau decrease-key: mengubah nilai yang tersimpan di suatu simpul.
• Insert: menambahkan sebuah nilai ke dalam heap.
• Merge: menggabungkan dua heap untuk membentuk sebuah heap baru yang berisi semua elemen pembentuk heap tersebut.
Heap Sort
Diagram Pohon Dalam Heap Sort
Pengertian Heap Adalah struktur data yang berbentuk pohon yang memenuhi sifat-sifat heap yaitu jika B adalah anak dari A, maka nilai yang tersimpan di simpul A lebih besar atau sama dengan nilai yang tersimpan di simpul B.
Hal ini mengakibatkan elemen dengan nilai terbesar selalu berada pada posisi akar, dan heap ini disebut max heap.
(Bila perbandingannya diterbalikkan yaitu elemen terkecilnya selalu berada di simpul akar, heap ini disebut adalah min heap).
Karena itulah, heap biasa dipakai untuk mengimplementasikan priority queue. Operasi-operasi yang digunakan untuk heap adalah:
• Delete-max atau delete-min: menghapus simpul akar dari sebuah max atau min heap.
• Increase-key atau decrease-key: mengubah nilai yang tersimpan di suatu simpul.
• Insert: menambahkan sebuah nilai ke dalam heap.
• Merge: menggabungkan dua heap untuk membentuk sebuah heap baru yang berisi semua elemen pembentuk heap tersebut.
.2 Jenis-jenis Heap
.2.1 Binary heap
adalah heap yang dibuat dengan menggunakan pohon biner.
.2.2 Binomial heap
adalah heap yang dibuat dengan menggunakan pohon binomial.
Pohon binomial bila didefinisikan secara rekursif adalah:
• Sebuah pohon binomial dengan tinggi 0 adalah simpul tunggal
• Sebuah pohon binomial dengan tinggi k mempunyai sebuah simpul akar yang anak-anaknya adalah akar-akar pohon pohon binomial.
.2.3 Fibonacci Heap
Fibonacci heap adalah kumpulan pohon yang membentuk minimum heap.
Pohon dalam struktur data ini tidak memiliki bentuk yang tertentu dan pada kasus yang ekstrim heap ini memiliki semua elemen dalam pohon yang berbeda atau sebuah pohon tunggal dengan tinggi Keunggulan dari Fibonacci heap adalah ketika menggabungkan heap cukup dengan menggabungkan dua list pohon.
Heap Sort
HeapSort 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.
Algoritma pengurutan heap sort ini mengurutkan isi suatu larik masukan dengan memandang larik masukan sebagai suatu Complete Binary Tree (CBT).
Setelah itu Complete Binary Tree (CBT) ini dapat dikonversi menjadi suatu heap tree. Setelah itu Complete Binary Tree (CBT) diubah menjadi suatu priority queue.
Algoritma pengurutan heap dimulai dari membangun sebuah heap dari kumpulan data yang ingin diurutkan, dan kemudian menghapus data yang mempunyai nilai tertinggi dan menempatkan dalam akhir dari larik yang telah terurut.
Setelah memindahkan data dengan nilai terbesar, proses berikutnya adalah membangun ulang heap dan memindahkan nilai terbesar pada heap tersebut dan menempatkannya dalam tempat terakhir pada larik terurut yang belum diisi data lain.
Proses ini berulang sampai tidak ada lagi data yang tersisa dalam heap dan larik yang terurut penuh. Dalam implementasinya kita membutuhkan dua larik – satu untuk menyimpan heap dan satu lagi untuk menyimpan data yang sudah terurut.
Tetapi untuk optimasi memori, kita dapat menggunakan hanya satu larik saja.
Yaitu dengan cara menukar isi akar dengan elemen terakhir dalam heap tree.
Jika memori tidak menjadi masalah maka dapat tetap menggunakan dua larik yaitu larik masukan dan larik hasil.
Heap Sort memasukkan data masukan ke dalam struktur data heap.
Nilai terbesar (dalam max-heap) atau nilai terkecil (dalam min-heap) diambil satu per satu sampai habis, nilai tersebut diambil dalam urutan yang terurut.
Algoritma untuk heap sort :
function heapSort(a, count) is
input: sebuah larik tidak terurut a dengan panjang length
(pertama letakkan a dalam max-heap) heapify(a, count)
end := count -1
while end > 0 do
remove ( )
reheapify ( )
end := end – 1
Algoritma Heapify
Algoritma Heapify adalah membangun sebuah heap dari bawah ke atas, secara berturut-turut berubah ke bawah untuk membangun heap.
Permasalahan pertama yang harus kita pertimbangkan dalam melakukan operasi heapify adalah dari bagian mana kita harus memulai.
Bila kita mencoba operasi heapify dari akar maka akan terjadi operasi runut-naik seperti algoritma bubble sort yang akan menyebabkan kompleksitas waktu yang ada akan berlipat ganda.
Sebuah versi lain adalah membangun heap secara atas-bawah dan berganti-ganti ke atas untuk secara konseptual lebih sederhana untuk ditangani.
Versi ini mulai dengan sebuah heap kosong dan secara berturut-turut memasukkan data.
Versi lainnya lagi adalah dengan membentuk pohon heap-pohon heap mulai dari subtree-subtree yang paling bawah.
Jika subtree-subtree suatu simpul sudah membentuk heap maka pohon dari simpul tersebut mudah dijadikan pohon heap dengan mengalirkannya ke bawah.
Setelah diuji, maka ide yang paling efisien adalah versi yang terakhir, yang kompleksitas algoritmanya pada kasus terburuk adalah O(n), sedangkan versi membentuk heap tree-heap tree dari atas ke bawah kompleksitas nya O(n log n)Jadi, algoritma utama heapify adalah melakukan iterasi mulai dari internal simpul paling kanan bawah (pada representasi larik, adalah elemen yang berada di indeks paling besar) hingga akar, kemudian kearah kiri dan naik ke level di atasnya, dan seterusnya hingga mencapai akar (sebagai larik [0..N-1]). Oleh karena itu, iterasi dilakukan mulai dari j= N/2 dan berkurang satu-satu hingga mencapai j=0. Pada simpul internal tersebut, pemeriksaan hanya dilakukan pada simpul anaknya langsung (tidak pada level-level lain di bawahnya). Pada saat iterasi berada di level yang lebih tinggi, subtree subtree selalu sudah membentuk heap. Jadi, kasus akan mengalirkan simpul tersebut kearah bawah. Dengan demikian, heapify versi ini melakukan sebanyak N/2 kali iterasi, dan pada kasus yang paling buruk akan melakukan iterasi sebanyak log (N) kali.
Algoritma Remove
Algoritma remove ini menukar akar (yang berisi nilai maksimum) dari heap dengan elemen terakhir. Secara logika, simpul yang berada paling kanabawah dipindahkan ke akar untuk menggantikan simpul akar yang akan diambil.
Algoritma Reheapify
Algoritma reheapify ini melakukan pembuatan ulang heap dari atas ke bawah seperti halnya iterasi terakhir dari algoritma metoda heapify. Perbedaan antara metode heapify dengan metode reheapify ada pada iterasi yang dilakukan oleh kedua algoritma tersebut. Algoritma metode reheapify ini hanya melakukan iterasi terakhir dari algoritma heapify. Hal ini disebabkan baik subtree kiri maupun subtree kanannya sudah merupakan heap, sehingga tidak perlu dilakukan iterasi lengkap seperti algoritma heapify. Dan setelah reheapify maka simpul yang akan diiterasikan berikutnya akan berkurang satu.
Representasi Alokasi Dinamis Algoritma Pengurutan Heap Sort
Karakteristik dari algoritma pengurutan heap sort adalah bahwa dalam implementasinya heap sort menggunakan heap tree agar dapat diselesaikan secara heap sort. Oleh karena itu, untuk mengimplementasikan algoritma pengurutan heap sort dalam suatu program aplikasi, dibutuhkan adanya alokasi dinamis dengan menggunakan struktur data tree (pohon). Prinsip-prinsip dasar mengenai struktur data tree yang digunakan untuk merealisasikan heap tree adalah sebagai berikut:
a. Simpul-simpul saling berhubungan dengan menggunakan pointer.
Pada struktur data tree ini digunakan minimal dua buah pointer pada setiap simpul,masing-masing untuk menunjuk ke cabang kiri dan cabang kanan dari tree tersebut. Misalnya dalam bahasa C, struktur data tree dideklarasikan sebagai berikut:
Class BinaryTreeSimpul {
keyType key;
infoType info;
BinaryTreeSimpul Left,
Right; // metoda-metoda
}
b. Left dan Right berharga NULL apabila tidak ada lagi cabang pada arah yang bersangkutan.
c. Struktur dari binary tree, termasuk hubungan-hubungan antar-simpul, secara eksplisit direpresentasikan oleh Left dan Right. Apabila diperlukan penelusuran naik (backtrack), maka hal tersebut dapat dilakukan dengan penelusuran ulang dari root, penggunaan algoritma-algoritma yang bersifat rekursif, atau penggunaan stack.
d. Alternatif lain adalah dengan menambahkan adanya pointer ke parent.
Namun hal ini akan mengakibatkan bertambahnya jumlah tahapan pada proses-proses penambahan/penghapusan simpul
Perbandingan Dengan Algoritma Pengurutan Lain
Heapsort hampir setara dengan quick sort, algoritma pengurutan data lain berdasarkan perbandingan yang sangat efisien. Quick sort sedikit lebih cepat, karena cache dan faktor-faktor lain, tetapi pada kasus terburuk
kompleksitasnya O(n), yang sangat lambat untuk data yang berukuran sangat besar. Lalu karena heap sort memiliki (N log N) maka sistem yang memerlukan pengamanan yang ketat biasa memakai heap sort sebagai algoritma pengurutannya. Heap sort juga sering dibandingkan dengan merge sort, yang mempunyaikompleksitas algoritma yang sama, tetapi kompleksitas ruang nya (n) yang lebih besar dari heap sort. Heap sort juga lebih cepat pada mesin dengancache data yang kecil atau lambat.
Kesimpulan
Dengan memanfaatkan struktur data pohon, kita bisa mendapatkan algoritma pengurutan data yang mangkus yang bisa dimanfaatkan untuk membangun program aplikasi yang baik. Algoritma pengurutan heap sort bisa dimasukkan ke dalam algoritma divide and conquer yang disebabkan pembagian dilakukan dengan terlebih dahulu menerapkan algoritma metoda heapify sebagai inisialisasi untuk mentransformasi suatu tree menjadi heap tree, dan pada setiap tahapan diterapkan algoritma metoda reheapify untuk menyusun ulang heap tree.
Pengertian Heap Adalah struktur data yang berbentuk pohon yang memenuhi sifat-sifat heap yaitu jika B adalah anak dari A, maka nilai yang tersimpan di simpul A lebih besar atau sama dengan nilai yang tersimpan di simpul B.
Hal ini mengakibatkan elemen dengan nilai terbesar selalu berada pada posisi akar, dan heap ini disebut max heap.
(Bila perbandingannya diterbalikkan yaitu elemen terkecilnya selalu berada di simpul akar, heap ini disebut adalah min heap).
Karena itulah, heap biasa dipakai untuk mengimplementasikan priority queue. Operasi-operasi yang digunakan untuk heap adalah:
• Delete-max atau delete-min: menghapus simpul akar dari sebuah max atau min heap.
• Increase-key atau decrease-key: mengubah nilai yang tersimpan di suatu simpul.
• Insert: menambahkan sebuah nilai ke dalam heap.
• Merge: menggabungkan dua heap untuk membentuk sebuah heap baru yang berisi semua elemen pembentuk heap tersebut.
.2 Jenis-jenis Heap
.2.1 Binary heap
adalah heap yang dibuat dengan menggunakan pohon biner.
.2.2 Binomial heap
adalah heap yang dibuat dengan menggunakan pohon binomial.
Pohon binomial bila didefinisikan secara rekursif adalah:
• Sebuah pohon binomial dengan tinggi 0 adalah simpul tunggal
• Sebuah pohon binomial dengan tinggi k mempunyai sebuah simpul akar yang anak-anaknya adalah akar-akar pohon pohon binomial.
.2.3 Fibonacci Heap
Fibonacci heap adalah kumpulan pohon yang membentuk minimum heap.
Pohon dalam struktur data ini tidak memiliki bentuk yang tertentu dan pada kasus yang ekstrim heap ini memiliki semua elemen dalam pohon yang berbeda atau sebuah pohon tunggal dengan tinggi Keunggulan dari Fibonacci heap adalah ketika menggabungkan heap cukup dengan menggabungkan dua list pohon.
Heap Sort
HeapSort 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.
Algoritma pengurutan heap sort ini mengurutkan isi suatu larik masukan dengan memandang larik masukan sebagai suatu Complete Binary Tree (CBT).
Setelah itu Complete Binary Tree (CBT) ini dapat dikonversi menjadi suatu heap tree. Setelah itu Complete Binary Tree (CBT) diubah menjadi suatu priority queue.
Algoritma pengurutan heap dimulai dari membangun sebuah heap dari kumpulan data yang ingin diurutkan, dan kemudian menghapus data yang mempunyai nilai tertinggi dan menempatkan dalam akhir dari larik yang telah terurut.
Setelah memindahkan data dengan nilai terbesar, proses berikutnya adalah membangun ulang heap dan memindahkan nilai terbesar pada heap tersebut dan menempatkannya dalam tempat terakhir pada larik terurut yang belum diisi data lain.
Proses ini berulang sampai tidak ada lagi data yang tersisa dalam heap dan larik yang terurut penuh. Dalam implementasinya kita membutuhkan dua larik – satu untuk menyimpan heap dan satu lagi untuk menyimpan data yang sudah terurut.
Tetapi untuk optimasi memori, kita dapat menggunakan hanya satu larik saja.
Yaitu dengan cara menukar isi akar dengan elemen terakhir dalam heap tree.
Jika memori tidak menjadi masalah maka dapat tetap menggunakan dua larik yaitu larik masukan dan larik hasil.
Heap Sort memasukkan data masukan ke dalam struktur data heap.
Nilai terbesar (dalam max-heap) atau nilai terkecil (dalam min-heap) diambil satu per satu sampai habis, nilai tersebut diambil dalam urutan yang terurut.
Algoritma untuk heap sort :
function heapSort(a, count) is
input: sebuah larik tidak terurut a dengan panjang length
(pertama letakkan a dalam max-heap) heapify(a, count)
end := count -1
while end > 0 do
remove ( )
reheapify ( )
end := end – 1
Algoritma Heapify
Algoritma Heapify adalah membangun sebuah heap dari bawah ke atas, secara berturut-turut berubah ke bawah untuk membangun heap.
Permasalahan pertama yang harus kita pertimbangkan dalam melakukan operasi heapify adalah dari bagian mana kita harus memulai.
Bila kita mencoba operasi heapify dari akar maka akan terjadi operasi runut-naik seperti algoritma bubble sort yang akan menyebabkan kompleksitas waktu yang ada akan berlipat ganda.
Sebuah versi lain adalah membangun heap secara atas-bawah dan berganti-ganti ke atas untuk secara konseptual lebih sederhana untuk ditangani.
Versi ini mulai dengan sebuah heap kosong dan secara berturut-turut memasukkan data.
Versi lainnya lagi adalah dengan membentuk pohon heap-pohon heap mulai dari subtree-subtree yang paling bawah.
Jika subtree-subtree suatu simpul sudah membentuk heap maka pohon dari simpul tersebut mudah dijadikan pohon heap dengan mengalirkannya ke bawah.
Setelah diuji, maka ide yang paling efisien adalah versi yang terakhir, yang kompleksitas algoritmanya pada kasus terburuk adalah O(n), sedangkan versi membentuk heap tree-heap tree dari atas ke bawah kompleksitas nya O(n log n)Jadi, algoritma utama heapify adalah melakukan iterasi mulai dari internal simpul paling kanan bawah (pada representasi larik, adalah elemen yang berada di indeks paling besar) hingga akar, kemudian kearah kiri dan naik ke level di atasnya, dan seterusnya hingga mencapai akar (sebagai larik [0..N-1]). Oleh karena itu, iterasi dilakukan mulai dari j= N/2 dan berkurang satu-satu hingga mencapai j=0. Pada simpul internal tersebut, pemeriksaan hanya dilakukan pada simpul anaknya langsung (tidak pada level-level lain di bawahnya). Pada saat iterasi berada di level yang lebih tinggi, subtree subtree selalu sudah membentuk heap. Jadi, kasus akan mengalirkan simpul tersebut kearah bawah. Dengan demikian, heapify versi ini melakukan sebanyak N/2 kali iterasi, dan pada kasus yang paling buruk akan melakukan iterasi sebanyak log (N) kali.
Algoritma Remove
Algoritma remove ini menukar akar (yang berisi nilai maksimum) dari heap dengan elemen terakhir. Secara logika, simpul yang berada paling kanabawah dipindahkan ke akar untuk menggantikan simpul akar yang akan diambil.
Algoritma Reheapify
Algoritma reheapify ini melakukan pembuatan ulang heap dari atas ke bawah seperti halnya iterasi terakhir dari algoritma metoda heapify. Perbedaan antara metode heapify dengan metode reheapify ada pada iterasi yang dilakukan oleh kedua algoritma tersebut. Algoritma metode reheapify ini hanya melakukan iterasi terakhir dari algoritma heapify. Hal ini disebabkan baik subtree kiri maupun subtree kanannya sudah merupakan heap, sehingga tidak perlu dilakukan iterasi lengkap seperti algoritma heapify. Dan setelah reheapify maka simpul yang akan diiterasikan berikutnya akan berkurang satu.
Representasi Alokasi Dinamis Algoritma Pengurutan Heap Sort
Karakteristik dari algoritma pengurutan heap sort adalah bahwa dalam implementasinya heap sort menggunakan heap tree agar dapat diselesaikan secara heap sort. Oleh karena itu, untuk mengimplementasikan algoritma pengurutan heap sort dalam suatu program aplikasi, dibutuhkan adanya alokasi dinamis dengan menggunakan struktur data tree (pohon). Prinsip-prinsip dasar mengenai struktur data tree yang digunakan untuk merealisasikan heap tree adalah sebagai berikut:
a. Simpul-simpul saling berhubungan dengan menggunakan pointer.
Pada struktur data tree ini digunakan minimal dua buah pointer pada setiap simpul,masing-masing untuk menunjuk ke cabang kiri dan cabang kanan dari tree tersebut. Misalnya dalam bahasa C, struktur data tree dideklarasikan sebagai berikut:
Class BinaryTreeSimpul {
keyType key;
infoType info;
BinaryTreeSimpul Left,
Right; // metoda-metoda
}
b. Left dan Right berharga NULL apabila tidak ada lagi cabang pada arah yang bersangkutan.
c. Struktur dari binary tree, termasuk hubungan-hubungan antar-simpul, secara eksplisit direpresentasikan oleh Left dan Right. Apabila diperlukan penelusuran naik (backtrack), maka hal tersebut dapat dilakukan dengan penelusuran ulang dari root, penggunaan algoritma-algoritma yang bersifat rekursif, atau penggunaan stack.
d. Alternatif lain adalah dengan menambahkan adanya pointer ke parent.
Namun hal ini akan mengakibatkan bertambahnya jumlah tahapan pada proses-proses penambahan/penghapusan simpul
Perbandingan Dengan Algoritma Pengurutan Lain
Heapsort hampir setara dengan quick sort, algoritma pengurutan data lain berdasarkan perbandingan yang sangat efisien. Quick sort sedikit lebih cepat, karena cache dan faktor-faktor lain, tetapi pada kasus terburuk
kompleksitasnya O(n), yang sangat lambat untuk data yang berukuran sangat besar. Lalu karena heap sort memiliki (N log N) maka sistem yang memerlukan pengamanan yang ketat biasa memakai heap sort sebagai algoritma pengurutannya. Heap sort juga sering dibandingkan dengan merge sort, yang mempunyaikompleksitas algoritma yang sama, tetapi kompleksitas ruang nya (n) yang lebih besar dari heap sort. Heap sort juga lebih cepat pada mesin dengancache data yang kecil atau lambat.
Kesimpulan
Dengan memanfaatkan struktur data pohon, kita bisa mendapatkan algoritma pengurutan data yang mangkus yang bisa dimanfaatkan untuk membangun program aplikasi yang baik. Algoritma pengurutan heap sort bisa dimasukkan ke dalam algoritma divide and conquer yang disebabkan pembagian dilakukan dengan terlebih dahulu menerapkan algoritma metoda heapify sebagai inisialisasi untuk mentransformasi suatu tree menjadi heap tree, dan pada setiap tahapan diterapkan algoritma metoda reheapify untuk menyusun ulang heap tree.
Algoritma
Algoritma berasal ari kata Algorism yang berati proses menghitung dengan angka Arab.
kata Algorism sendiri berasal dari seorang penulis buku Arab yang terkenal, yaitu Abu Ja'far Muhammad Ibnu Musa al-Khuwarizmi ( al-Khuwarizmi dibaca orang Barat menjadi Algorism).Al-Khuwarizmi menulis buku yang berjudul " Kitab Al Jabar Wal-Muqabala", yang artinya " Buku pemugaran dan pengurangan" (The book of restoration and reduction).
Perubahan dari Algorism menjadi kata Algorith muncul karena kata Algorism sering di salah artikan denga Arithmetic, sehingga akhiran -sm berubah menjadi -thm.
Akhirnya kata Algorithm berangsur angsur dipakai sebagai metode perhitungan (Komputasi) secara umum, sehingga kehilangan makna aslinya. Dalam Bahasa Indonesia menjadi ALGORITMA.
Algoritma adalah gambaran dari urutan langkah langkah yang sistematis dalam menyelesaikan suatu masalah.
Suatu Algoritma yang baik dan benar harus mepunyai sifat sifat yaitu:
kata Algorism sendiri berasal dari seorang penulis buku Arab yang terkenal, yaitu Abu Ja'far Muhammad Ibnu Musa al-Khuwarizmi ( al-Khuwarizmi dibaca orang Barat menjadi Algorism).Al-Khuwarizmi menulis buku yang berjudul " Kitab Al Jabar Wal-Muqabala", yang artinya " Buku pemugaran dan pengurangan" (The book of restoration and reduction).
Perubahan dari Algorism menjadi kata Algorith muncul karena kata Algorism sering di salah artikan denga Arithmetic, sehingga akhiran -sm berubah menjadi -thm.
Akhirnya kata Algorithm berangsur angsur dipakai sebagai metode perhitungan (Komputasi) secara umum, sehingga kehilangan makna aslinya. Dalam Bahasa Indonesia menjadi ALGORITMA.
Algoritma adalah gambaran dari urutan langkah langkah yang sistematis dalam menyelesaikan suatu masalah.
Suatu Algoritma yang baik dan benar harus mepunyai sifat sifat yaitu:
FINITENES(finish)
Sebuah algoritma harus berakhir setelah melakukan sejumlah langkah tertentu.
DEFINITENESS (DEFINISI)
Setiap step dari Algoritma harus didefinisikan secara tepat,aksi aksi yang harus diselesaikan secra mendetail harus tertera pada masing masing kasus.
INPUT (masukan)
Algoritma mempunyai input masukan nol atau lebih yaitu besaran awal yang diberikan sebelum algoritma dimulai.
OUTPUT(keluaran)
Besaran yang mempunyai hubungan khusus dengan input input.
EFFECTIVENESS ( Efectif)
Semua operasi yang digunakan harus cukup mendasar dan tepat.
EFFICIENT (Efisien)
Semua operasi yang digunakan selau dikaitkan dengan dana, sumber daya yang dipakai dalam hal Algoritma yang aik sehingga mampu menyelesaikan masalah.
COMMUNICATIVE (KOMUNIKATIF)
Algoritma yang dibuat harus bisa dimengerti oleh sipembuat setelah selang beberapa waktu algoritma itu ditulis serta algoritma itu harus bisa dipergunakan oleh orang lain.
Implementasi Algoritma dalam program
Beberapa contoh:
ConsoleApplicationGreedyAlgorithm.rar
http://www.ziddu.com/download/8718538/ConsoleApplicationGreedyAlgorithm.rar.html
ConsoleApplicationGenericList.rar
http://www.ziddu.com/download/8718509/ConsoleApplicationGenericList.rar.html
ConsoleApplicationForEach.rar
http://www.ziddu.com/download/8718500/ConsoleApplicationForEach.rar.html
ConsoleApplicationFaktorial.rar
http://www.ziddu.com/download/8718478/ConsoleApplicationFaktorial.rar.html
ConsoleApplicationEnumeration.rar
http://www.ziddu.com/download/8718434/ConsoleApplicationEnumeration.rar.html
ConsoleApplicationDynamicProgramming.rar
http://www.ziddu.com/download/8718406/ConsoleApplicationDynamicProgramming.rar.
ConsoleApplicationDynamicProgramming1.rar
http://www.ziddu.com/download/8718387/ConsoleApplicationDynamicProgramming1.rar.html
ConsoleApplicationDatabase.rar
http://www.ziddu.com/download/8718339/ConsoleApplicationDatabase.rar.html
ConsoleApplicationCar.rar
http://www.ziddu.com/download/8718326/ConsoleApplicationCar.rar.html
ConsoleApplicationBilanganPrima.rar
http://www.ziddu.com/download/8718267/ConsoleApplicationBilanganPrima.rar.html
ConsoleApplicationBilanganPrima.rar
http://www.ziddu.com/download/8717967/ConsoleApplicationBilanganPrima.rar.html
ConsoleApplicationBasisBilangan.rar
http://www.ziddu.com/download/8717939/ConsoleApplicationBasisBilangan.rar.html
ConsoleApplicationApplicationLooping.rar
http://www.ziddu.com/download/8717525/ConsoleApplicationApplicationLooping.rar.html
ConsoleApplicationAnagram.rar
http://www.ziddu.com/download/8717521/ConsoleApplicationAnagram.rar.html
ConsoleApplicationAnaGeuis.rar
http://www.ziddu.com/download/8717504/ConsoleApplicationAnaGeuis.rar.html
Rekursif
Rekursion Dalam struktur data adalah suatu proses berupa pemanggilan diri berupa pernyataan perulangan.
Proses Rekursif dalam struktur data ini juga memungkinkan terjadinya komputasi yang tidak berkesudahan sampai memori yang di gunakan tidak dapat menampung lagi.
Sehingga perlu di perhatikan akan adanya kondisi untuk menghentikan proses eksekusi program.
Sebagai implementasi dari proses rekursi ini antara lain:
1. Proses menghitung nilai faktorial dari bilangan bulat positif.
2. mencari deret fibonnaci dari suatu bilangan bulat.
3. permainan menara hanoi dan lain sebagainya.
Implementasi Rekursi dalam program
Beberapa contoh:
ConsoleApplicationFaktorialIteratifRekursif.rar
http://www.ziddu.com/download/8718486/ConsoleApplicationFaktorialIteratifRekursif.rar.html
Proses Rekursif dalam struktur data ini juga memungkinkan terjadinya komputasi yang tidak berkesudahan sampai memori yang di gunakan tidak dapat menampung lagi.
Sehingga perlu di perhatikan akan adanya kondisi untuk menghentikan proses eksekusi program.
Sebagai implementasi dari proses rekursi ini antara lain:
1. Proses menghitung nilai faktorial dari bilangan bulat positif.
2. mencari deret fibonnaci dari suatu bilangan bulat.
3. permainan menara hanoi dan lain sebagainya.
Implementasi Rekursi dalam program
Beberapa contoh:
ConsoleApplicationFaktorialIteratifRekursif.rar
http://www.ziddu.com/download/8718486/ConsoleApplicationFaktorialIteratifRekursif.rar.html
Graf
Graf digunakan untuk merepresentasikan objek-objek diskrit
dan hubungan antara objek-objek tersebut.
Jenis-Jenis Graf
Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf,
maka graf digolongkan menjadi dua jenis:
1. Graf sederhana (simple graph).
Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan
graf sederhana.
2. Graf tak-sederhana (unsimple-graph).
Graf yang mengandung sisi ganda atau gelang dinamakan graf
tak-sederhana (unsimple graph).
•Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf
dapat digolongkan menjadi dua jenis:
1. Graf berhingga (limited graph)
adalah sebuah graf yang jumlah simpulnya, n, berhingga.
2. Graf tak-berhingga (unlimited graph)
Graf yang jumlah simpulnya, n, tidak berhingga banyaknya
disebut graf tak-berhingga.
•Berdasarkan orientasi arah pada sisi, maka secara umum graf di
bedakan atas 2 jenis:
1. Graf tak-berarah (undirected graph)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf
tak-berarah.
2. Graf berarah (directed graph atau digraph)
Graf yang setiap sisinya diberikan orientasi arah disebut se-
bagai graf berarah.
Contoh
Graf dalam penerapannya :
Rangkaian listrik, Isomer senyawa kimia karbon dll.
Implementasi graf dalam program
Beberapa contoh:
ConsoleApplicationGraph_DIJKSTRA.rar
http://www.ziddu.com/download/8718528/ConsoleApplicationGraph_DIJKSTRA.rar.html
ConsoleApplicationGRAPH.rar
http://www.ziddu.com/download/8718517/ConsoleApplicationGRAPH.rar.html
dan hubungan antara objek-objek tersebut.
Jenis-Jenis Graf
Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf,
maka graf digolongkan menjadi dua jenis:
1. Graf sederhana (simple graph).
Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan
graf sederhana.
2. Graf tak-sederhana (unsimple-graph).
Graf yang mengandung sisi ganda atau gelang dinamakan graf
tak-sederhana (unsimple graph).
•Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf
dapat digolongkan menjadi dua jenis:
1. Graf berhingga (limited graph)
adalah sebuah graf yang jumlah simpulnya, n, berhingga.
2. Graf tak-berhingga (unlimited graph)
Graf yang jumlah simpulnya, n, tidak berhingga banyaknya
disebut graf tak-berhingga.
•Berdasarkan orientasi arah pada sisi, maka secara umum graf di
bedakan atas 2 jenis:
1. Graf tak-berarah (undirected graph)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf
tak-berarah.
2. Graf berarah (directed graph atau digraph)
Graf yang setiap sisinya diberikan orientasi arah disebut se-
bagai graf berarah.
Contoh
Graf dalam penerapannya :
Rangkaian listrik, Isomer senyawa kimia karbon dll.
Implementasi graf dalam program
Beberapa contoh:
ConsoleApplicationGraph_DIJKSTRA.rar
http://www.ziddu.com/download/8718528/ConsoleApplicationGraph_DIJKSTRA.rar.html
ConsoleApplicationGRAPH.rar
http://www.ziddu.com/download/8718517/ConsoleApplicationGRAPH.rar.html
Searching
Searching adalah suatu metoda pencarian dalam struktur data. Pencarian di dalam struktur data merupakan suatu pekerjaan pemograman yang paling mendasar.
Sequential searching adalah Metoda pencarian linier secara berurutan.Metode pencarian linier cukup mudah untuk di implementasikan di dalam penulisan sebuah program.Metoda ini menggunakan cara dengan diawali dari ujung sebelah kiri lalu melakukan perbandingan masing masing dari elemen yang ada dengan elemen pencarian. jika sudah ditemukan, maka pencarian segera berakhir dan fungsi akan menghasilkan nilai True.Sementara jika elemen yang dicari tidak ditemukan hingga akhir dari suatu larik maka pencarian akan berakhir dengan tidak adanya elemen dalam larik tersebut dan fungsi akan menghasilkan nilai False.Dalam melakukan pencarian dalam metoda ini larik atau deretan nilai harus diurutkan terlebih dahulu.Karena telah terurut maka kita tahu bahwa elemen yang kita cari nilainya sudah lebih besar dari elemen pada array list yang ditunjuk oleh index.kita tidak perlu melakukan pencarian lebih lanjut karena elemen yang kita cari pasti tidak akan kita temukan di bagian sisa array yang ada.Ini memungkinkan pencarian berlangsung secara lebih cepat saat elemen yang kita cari berada di bagian depan array list yang ada.tentu saja berlawanan yaitu jika elemen yang dicari berada dai ujung bagian array list.
Binary SearchAdalah suatu metoda dalam Searching dengan cara konvensional yaitu pencarian selalu mulai dari ujung kiri larik dimana hal itu di tunjukan oleh inisiasi objek index dengan nilai 0. Selanjutnya kita lakukan penelusuran larik untuk melakukan pencarian larik hingga ke ujung larik tercapai. Untuk memahami bagaimana Binary Search bekerja, bayangkan saat kita mencoba menebak bilangan diantara rentang 1 – 100 secara terurut yang diberikan salah seorang teman kepada kita.misalkan untuk setiap tebakan yang kita buat, teman kita akan mengatakan tebakan kita benar,terlalu kecil atau terlalu besar.tebakan terbaik saat awal tentu nya 50 jika tebakan tersebut terlalu tinggi selanjutnya kita sebaiknya menebak 25 , sementara jika terlalu besar tebakan kita selanjutnya 75. Setiap kali menebak kita selalu memilih di tengah tengah dengan menyesuaikan batas bawah dan batas atas bilangan.
Implementasi Searching dalam program
Beberapa contohnya:
ConsoleApplicationSearching.rar
http://www.ziddu.com/download/8718817/ConsoleApplicationSearching.rar.html
ConsoleApplicationSort_and_Search_Default.rar
http://www.ziddu.com/download/8718964/ConsoleApplicationSort_and_Search_Default.rar.html
Sequential searching adalah Metoda pencarian linier secara berurutan.Metode pencarian linier cukup mudah untuk di implementasikan di dalam penulisan sebuah program.Metoda ini menggunakan cara dengan diawali dari ujung sebelah kiri lalu melakukan perbandingan masing masing dari elemen yang ada dengan elemen pencarian. jika sudah ditemukan, maka pencarian segera berakhir dan fungsi akan menghasilkan nilai True.Sementara jika elemen yang dicari tidak ditemukan hingga akhir dari suatu larik maka pencarian akan berakhir dengan tidak adanya elemen dalam larik tersebut dan fungsi akan menghasilkan nilai False.Dalam melakukan pencarian dalam metoda ini larik atau deretan nilai harus diurutkan terlebih dahulu.Karena telah terurut maka kita tahu bahwa elemen yang kita cari nilainya sudah lebih besar dari elemen pada array list yang ditunjuk oleh index.kita tidak perlu melakukan pencarian lebih lanjut karena elemen yang kita cari pasti tidak akan kita temukan di bagian sisa array yang ada.Ini memungkinkan pencarian berlangsung secara lebih cepat saat elemen yang kita cari berada di bagian depan array list yang ada.tentu saja berlawanan yaitu jika elemen yang dicari berada dai ujung bagian array list.
Binary SearchAdalah suatu metoda dalam Searching dengan cara konvensional yaitu pencarian selalu mulai dari ujung kiri larik dimana hal itu di tunjukan oleh inisiasi objek index dengan nilai 0. Selanjutnya kita lakukan penelusuran larik untuk melakukan pencarian larik hingga ke ujung larik tercapai. Untuk memahami bagaimana Binary Search bekerja, bayangkan saat kita mencoba menebak bilangan diantara rentang 1 – 100 secara terurut yang diberikan salah seorang teman kepada kita.misalkan untuk setiap tebakan yang kita buat, teman kita akan mengatakan tebakan kita benar,terlalu kecil atau terlalu besar.tebakan terbaik saat awal tentu nya 50 jika tebakan tersebut terlalu tinggi selanjutnya kita sebaiknya menebak 25 , sementara jika terlalu besar tebakan kita selanjutnya 75. Setiap kali menebak kita selalu memilih di tengah tengah dengan menyesuaikan batas bawah dan batas atas bilangan.
Implementasi Searching dalam program
Beberapa contohnya:
ConsoleApplicationSearching.rar
http://www.ziddu.com/download/8718817/ConsoleApplicationSearching.rar.html
ConsoleApplicationSort_and_Search_Default.rar
http://www.ziddu.com/download/8718964/ConsoleApplicationSort_and_Search_Default.rar.html
Sort
Sort adalah proses pengurutan data yang sebelumnya disusun secara acak sehingga menjadi tersusun secara teratur menurut suatu aturan tertentu.
Pada umumnya terdapat 2 jenis Sort/ pengurutan :
. Ascending (Naik)
. Descending (Turun)
Pengurutan Data Contohnya :
. Data Acak : 5 6 8 1 3 25 10
. Terurut Ascending : 1 3 5 6 8 10 25
. Terurut Descending : 25 10 8 6 5 3 1
Metode Sort/Pengurutan Data
Untuk melakukan proses pengurutan tersebut dapat digunakan berbagai macam cara /
metoda. Beberapa metoda diantaranya :
. Buble / Exchange Sort
. Selection Sort
. Insertion Sort
. Quick Sort
Bubble / Exchange Sort
Memindahkan elemen yang sekarang dengan elemen yang berikutnya, jika elemen sekarang Lebih besar( > ) dari elemen berikutnya, maka tukar Proses Pengurutan Data paling akhir dibandingkan dengan data di depannya, jika ternyata lebih kecil maka tukar. Dan pengecekan yang sama dilakukan terhadap data yang selanjutnya sampai dengan data yang paling awal.
Selection Sort
Membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari elemen sekarang maka dicatat posisinya dan kemudian ditukar. Dan begitu seterusnya.
Insertion Sort
Pengurutan dilakukan dengan cara membandingkan data ke-1(dimana 1 dimulai dari data ke-2 sampai dengan data terakhir) dengan data berikutnya. Jika ditemukan data yang lebih kecil maka data tersebut disisipkan ke depan sesuai posisi yang seharusnya.
Quick Sort
Membandingkan suatu elemen (disebut pivot) dengan elemen yang lain dan menyusunnya sedemikian rupa sehingga elemen-elemen lain yang lebih kecil daripada pivot tersebut terletak di sebelah kirinya dan elemen-elemen lain yang lebih besar daripada pivot tersebut terletak di sebelah kanannya. Sehingga dengan demikian telah terbentuk dua sublist, yang terletak di sebelah kiri dan kanan dari pivot.Lalu pada sublist kiri dan sublist kanan kita anggap sebuah list baru dan kita kerjakan proses yang sama seperti sebelumnya. Demikian seterusnya sampai tidak terdapat sublist lagi.
Sehingga didalamnya telah terjadi proses Rekursif.
Sort di implementasikan dalam program.
Beberapa contohnya:
ConsoleApplicationSort_and_Search_Default.rar
http://www.ziddu.com/download/8718856/ConsoleApplicationSort_and_Search_Default.rar.html
ConsoleApplicationSort_and_Search_Default.rar
http://www.ziddu.com/download/8718850/ConsoleApplicationSort_and_Search_Default.rar.html
ConsoleApplicationQuickSort_for_TelpNumber.rar
http://www.ziddu.com/download/8718790/ConsoleApplicationQuickSort_for_TelpNumber.rar.html
ConsoleApplicationQuickSort.rar
http://www.ziddu.com/download/8718783/ConsoleApplicationQuickSort.rar.html
ConsoleApplicationMergeSort.rar
http://www.ziddu.com/download/8718674/ConsoleApplicationMergeSort.rar.html
ConsoleApplicationBubbleSort.rar
http://www.ziddu.com/download/8718318/ConsoleApplicationBubbleSort.rar.html
ConsoleApplicationInsertionSort.rar
http://www.ziddu.com/download/8718591/ConsoleApplicationInsertionSort.rar.html
Pada umumnya terdapat 2 jenis Sort/ pengurutan :
. Ascending (Naik)
. Descending (Turun)
Pengurutan Data Contohnya :
. Data Acak : 5 6 8 1 3 25 10
. Terurut Ascending : 1 3 5 6 8 10 25
. Terurut Descending : 25 10 8 6 5 3 1
Metode Sort/Pengurutan Data
Untuk melakukan proses pengurutan tersebut dapat digunakan berbagai macam cara /
metoda. Beberapa metoda diantaranya :
. Buble / Exchange Sort
. Selection Sort
. Insertion Sort
. Quick Sort
Bubble / Exchange Sort
Memindahkan elemen yang sekarang dengan elemen yang berikutnya, jika elemen sekarang Lebih besar( > ) dari elemen berikutnya, maka tukar Proses Pengurutan Data paling akhir dibandingkan dengan data di depannya, jika ternyata lebih kecil maka tukar. Dan pengecekan yang sama dilakukan terhadap data yang selanjutnya sampai dengan data yang paling awal.
Selection Sort
Membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari elemen sekarang maka dicatat posisinya dan kemudian ditukar. Dan begitu seterusnya.
Insertion Sort
Pengurutan dilakukan dengan cara membandingkan data ke-1(dimana 1 dimulai dari data ke-2 sampai dengan data terakhir) dengan data berikutnya. Jika ditemukan data yang lebih kecil maka data tersebut disisipkan ke depan sesuai posisi yang seharusnya.
Quick Sort
Membandingkan suatu elemen (disebut pivot) dengan elemen yang lain dan menyusunnya sedemikian rupa sehingga elemen-elemen lain yang lebih kecil daripada pivot tersebut terletak di sebelah kirinya dan elemen-elemen lain yang lebih besar daripada pivot tersebut terletak di sebelah kanannya. Sehingga dengan demikian telah terbentuk dua sublist, yang terletak di sebelah kiri dan kanan dari pivot.Lalu pada sublist kiri dan sublist kanan kita anggap sebuah list baru dan kita kerjakan proses yang sama seperti sebelumnya. Demikian seterusnya sampai tidak terdapat sublist lagi.
Sehingga didalamnya telah terjadi proses Rekursif.
Sort di implementasikan dalam program.
Beberapa contohnya:
ConsoleApplicationSort_and_Search_Default.rar
http://www.ziddu.com/download/8718856/ConsoleApplicationSort_and_Search_Default.rar.html
ConsoleApplicationSort_and_Search_Default.rar
http://www.ziddu.com/download/8718850/ConsoleApplicationSort_and_Search_Default.rar.html
ConsoleApplicationQuickSort_for_TelpNumber.rar
http://www.ziddu.com/download/8718790/ConsoleApplicationQuickSort_for_TelpNumber.rar.html
ConsoleApplicationQuickSort.rar
http://www.ziddu.com/download/8718783/ConsoleApplicationQuickSort.rar.html
ConsoleApplicationMergeSort.rar
http://www.ziddu.com/download/8718674/ConsoleApplicationMergeSort.rar.html
ConsoleApplicationBubbleSort.rar
http://www.ziddu.com/download/8718318/ConsoleApplicationBubbleSort.rar.html
ConsoleApplicationInsertionSort.rar
http://www.ziddu.com/download/8718591/ConsoleApplicationInsertionSort.rar.html
Tree
Dalam Struktur Data ,Tree adalah salah satu struktur data yang berbentuk menyerupai sebuah pohon, yang terdiri dari serangkaian node (simpul) yang saling berhubungan.
Node-node tersebut dihubungkan oleh sebuah vektor. Setiap node dapat memiliki 0 atau
lebih node anak(child). Sebuah node yang memiliki node anak disebut node induk(parent). Sebuah node anak hanya memiliki satu node induk. Sesuai konvensi ilmu komputer,Tree bertumbuhke bawah, tidak seperti pohon di dunia nyata yang tumbuh ke atas. Dengan demikian node anak akan digambarkan berada di bawah node induknya. Node yang berada di pangkal tree disebut node root(akar), sedangkan node yang berada paling ujung pada piramida tree disebutnode leaf (daun).
Binary Tree (Pohon Biner)
Dalam mata kuliah struktur data, secara khusus akan dipelajari mengenai pohon biner. Pohon biner adalah sebuah tree yang masing-masing simpulnya hanya dapat memiliki maksimum 2 (dua) simpul anak Tidak boleh lebih.Pada pohon biner, umumnya kedua node anak disebut dengan posisinya, yaitu kiri dan kanan.
Beberapa istilah pada pohon biner:
- Size(ukuran): jumlah total node yang ada pada pohon biner.
- Depth (kedalaman): panjang jalur yang menghubungkan sebuah
node sampai ke node anaknya yang paling ujung (leaf).
Depth biasa juga disebut height.Full Binary Tree(Pohon Biner Penuh)
adalah pohon biner yang setiap nodenya memiliki 0 atau 2 node anak.
Perfect Binary Tree
(Pohon Biner Sempurna) adalah pohon biner yang semua node leafnya
berada pada kedalaman yang samadari node root. Juga disebut
sebagai Complete Binary Tree (Pohon Biner Lengkap)
Almost Complete Binary Tree
(Pohon Biner Hampir Lengkap)adalah pohon biner yang setiap nodenyadapat memiliki 0 node anak, atau memiliki kiri, atau jika memiliki kanan harus memiliki kiri.Tidak boleh memiliki kanan saja.Implementasi dalam pemrograman, dalam pokok bahasan ini akan dibicarakan untuk pohon biner saja. Asumsi awal adalah data yang hendak dimasukkan kedalam node, bertipe data integer.
Tree di implementasikan dalam program
Beberapa contohnya:
ConsoleApplicationBinaryTree.rar
http://www.ziddu.com/download/8718281/ConsoleApplicationBinaryTree.rar.html
ConsoleApplicationBinaryTree.rar
http://www.ziddu.com/download/8190514/ConsoleApplicationBinaryTree.rar.html
TreePresentasi.rar
http://www.ziddu.com/download/8190480/TreePresentasi.rar.html
Node-node tersebut dihubungkan oleh sebuah vektor. Setiap node dapat memiliki 0 atau
lebih node anak(child). Sebuah node yang memiliki node anak disebut node induk(parent). Sebuah node anak hanya memiliki satu node induk. Sesuai konvensi ilmu komputer,Tree bertumbuhke bawah, tidak seperti pohon di dunia nyata yang tumbuh ke atas. Dengan demikian node anak akan digambarkan berada di bawah node induknya. Node yang berada di pangkal tree disebut node root(akar), sedangkan node yang berada paling ujung pada piramida tree disebutnode leaf (daun).
Binary Tree (Pohon Biner)
Dalam mata kuliah struktur data, secara khusus akan dipelajari mengenai pohon biner. Pohon biner adalah sebuah tree yang masing-masing simpulnya hanya dapat memiliki maksimum 2 (dua) simpul anak Tidak boleh lebih.Pada pohon biner, umumnya kedua node anak disebut dengan posisinya, yaitu kiri dan kanan.
Beberapa istilah pada pohon biner:
- Size(ukuran): jumlah total node yang ada pada pohon biner.
- Depth (kedalaman): panjang jalur yang menghubungkan sebuah
node sampai ke node anaknya yang paling ujung (leaf).
Depth biasa juga disebut height.Full Binary Tree(Pohon Biner Penuh)
adalah pohon biner yang setiap nodenya memiliki 0 atau 2 node anak.
Perfect Binary Tree
(Pohon Biner Sempurna) adalah pohon biner yang semua node leafnya
berada pada kedalaman yang samadari node root. Juga disebut
sebagai Complete Binary Tree (Pohon Biner Lengkap)
Almost Complete Binary Tree
(Pohon Biner Hampir Lengkap)adalah pohon biner yang setiap nodenyadapat memiliki 0 node anak, atau memiliki kiri, atau jika memiliki kanan harus memiliki kiri.Tidak boleh memiliki kanan saja.Implementasi dalam pemrograman, dalam pokok bahasan ini akan dibicarakan untuk pohon biner saja. Asumsi awal adalah data yang hendak dimasukkan kedalam node, bertipe data integer.
Tree di implementasikan dalam program
Beberapa contohnya:
ConsoleApplicationBinaryTree.rar
http://www.ziddu.com/download/8718281/ConsoleApplicationBinaryTree.rar.html
ConsoleApplicationBinaryTree.rar
http://www.ziddu.com/download/8190514/ConsoleApplicationBinaryTree.rar.html
TreePresentasi.rar
http://www.ziddu.com/download/8190480/TreePresentasi.rar.html
Stack
Stack atau Tumpukan adalah suatu Struktur Data yang seolah-olah terlihat seperti data yang tersusun secara ‘menumpuk’, dimana ada data yang terletak diatas data yang lainnya.Stack Tumpukan atau susunannya bersifat LIFO (Last In First Out), berarti data yang masuk terakhir akan keluar pertama.
contohnya dalam kehidupan sehari hari antara lain:Tumpukan buku, tumpukan koin dll.
Ada dua Operasi dasar yang di gunakan pada Stack :
Push berfungsi menambah data pada STACK pada tumpukan paling atas
Pop berfungsi mengambil data pada STACK pada tumpukan paling atas
Stack di Implementasikan dalam program
Berikut ini beberapa contohnya:
ConsoleApplicationStackDefault.rar
http://www.ziddu.com/download/8718928/ConsoleApplicationStackDefault.rar.html
ConsoleApplicationStackDefault.rar
http://www.ziddu.com/download/8718882/ConsoleApplicationStackDefault.rar.html
ConsoleApplicationIteration_for_Stack.rar
http://www.ziddu.com/download/8718598/ConsoleApplicationIteration_for_Stack.rar
.html
ConsoleApplicationIteration_for_Stack.rar
http://www.ziddu.com/download/8718598/ConsoleApplicationIteration_for_Stack.rar.html
Stack.rar
http://www.ziddu.com/download/8190571/Stack.rar.html
contohnya dalam kehidupan sehari hari antara lain:Tumpukan buku, tumpukan koin dll.
Ada dua Operasi dasar yang di gunakan pada Stack :
Push berfungsi menambah data pada STACK pada tumpukan paling atas
Pop berfungsi mengambil data pada STACK pada tumpukan paling atas
Stack di Implementasikan dalam program
Berikut ini beberapa contohnya:
ConsoleApplicationStackDefault.rar
http://www.ziddu.com/download/8718928/ConsoleApplicationStackDefault.rar.html
ConsoleApplicationStackDefault.rar
http://www.ziddu.com/download/8718882/ConsoleApplicationStackDefault.rar.html
ConsoleApplicationIteration_for_Stack.rar
http://www.ziddu.com/download/8718598/ConsoleApplicationIteration_for_Stack.rar
.html
ConsoleApplicationIteration_for_Stack.rar
http://www.ziddu.com/download/8718598/ConsoleApplicationIteration_for_Stack.rar.html
Stack.rar
http://www.ziddu.com/download/8190571/Stack.rar.html
Linked List
Senarai Berantai atau Linked List adalah salah satu bentuk Struktur data,berisi kumpulan data (node) yang tersusun secara sambung menyambung, dinamis dan terbatas.Linked List saling terhubung dengan bantuan variabel pointerMasing-masing data dalam Linked List disebut dengan node (simpul)
yang menempati alokasi memori secara dinamis dan biasanya berupa struct yang terdiri dari beberapa field. Linked List atau Senarai berantai dapat di ilustrasikan sepertisatu kesatuan rangkaian kereta api. Kereta api terdiri dari beberapa gerbong, masing-masing dari gerbong itulah yang disebut tipe data bentukan(struct). Agar gerbong-gerbong tersebut dapat saling bertaut dibutuhkan minimal sebuah kait yang dinamakan sebagai pointer.
Setelah mendeklarasikan tipe data dan pointer pada list, selanjutnya kita akan mencoba membuat senarai (linked list) tunggal tidak berputar atau sebuah gerbong. Ada beberapa operasi yang dapat kita buat pada senarai tersebut, diantaranya: tambah, hapus dan edit dari gerbong tersebut.
Inti dari Linked list adalah proses (tambah, edit, hapus) dari gerbong / node dan bagaimana menyambungkan antar gerbong /node tersebut.....
Linked List dalam implementasi program
Beberapa contoh:
ConsoleApplicationDoublyLinkedList.rar
http://www.ziddu.com/download/8718348/ConsoleApplicationDoublyLinkedList.rar.html
ConsoleApplicationCircularlyLinkedList.rar
http://www.ziddu.com/download/8718334/ConsoleApplicationCircularlyLinkedList.rar.html
yang menempati alokasi memori secara dinamis dan biasanya berupa struct yang terdiri dari beberapa field. Linked List atau Senarai berantai dapat di ilustrasikan sepertisatu kesatuan rangkaian kereta api. Kereta api terdiri dari beberapa gerbong, masing-masing dari gerbong itulah yang disebut tipe data bentukan(struct). Agar gerbong-gerbong tersebut dapat saling bertaut dibutuhkan minimal sebuah kait yang dinamakan sebagai pointer.
Setelah mendeklarasikan tipe data dan pointer pada list, selanjutnya kita akan mencoba membuat senarai (linked list) tunggal tidak berputar atau sebuah gerbong. Ada beberapa operasi yang dapat kita buat pada senarai tersebut, diantaranya: tambah, hapus dan edit dari gerbong tersebut.
Inti dari Linked list adalah proses (tambah, edit, hapus) dari gerbong / node dan bagaimana menyambungkan antar gerbong /node tersebut.....
Linked List dalam implementasi program
Beberapa contoh:
ConsoleApplicationDoublyLinkedList.rar
http://www.ziddu.com/download/8718348/ConsoleApplicationDoublyLinkedList.rar.html
ConsoleApplicationCircularlyLinkedList.rar
http://www.ziddu.com/download/8718334/ConsoleApplicationCircularlyLinkedList.rar.html
Array
Array adalah sebuah struktur data yang terdiri atas banyak variabel dengan tipe data sama, dimana masing-masing elemen variabel mempunyai nilai indek. Setiap elemen array mampu untuk menyimpan satu jenis data.
Array adalah suatu tipe data terstruktur yang berupa sejumlah data sejenis(bertipe data sama) yang jumlahnya tetap dan diberi suatu nama tertentu.
Array dapat berupa array 1 dimensi, 2 dimensi, bahkan n-dimensi. Array merupakan struktur data yang statis, yaitu jumlah elemen yang harus ditentukan terlebih dahulu, tak bisa di ubah saat program berjalan. Untuk menyatakan array dalam PASCAL kita harus terlebih dahulu: Mendefinisikan jumlah elemen array.
Array Satu Dimensi Pendefinisian array Satu Dimensi secara umum adalah sebagai berikut: array dengan tipe/jenis yang sama yang memiliki satu index saja yaitu baris saja atau kolom saja.
Array MultidimensiArray multidimensi terdiri atas dimensi satu, dimensi dua, dimensi tiga dan seterusnya. Indek pertama dapat berupa baris dan yang kedua dapat berupa kolom dan yang ketiga berupa isi atau lainnya.
Record
Sebuah record rekaman disusun oleh beberapa field. Tiap field berisi data dari tipe dasar / bentukan tertentu. Record mempunyai kelebihan untuk menyimpan suatu sekumpulan elemen data yang berbeda-beda tipenya (di banding array).
Implementasi Array dalam program
Beberapa contohnya:
ConsoleApplicationBitArray.rar
http://www.ziddu.com/download/8718294/ConsoleApplicationBitArray.rar.html
ConsoleApplicationArrayList_for_String.rar
http://www.ziddu.com/download/8717675/ConsoleApplicationArrayList_for_String.rar.html
ConsoleApplicationArray.rar
http://www.ziddu.com/download/8717545/ConsoleApplicationArray.rar.html
ConsoleApplicationArray.rar
http://www.ziddu.com/download/8717352/ConsoleApplicationArray.rar.html
Array.rar
http://www.ziddu.com/download/7844295/Array.rar.html
ConsoleApplicationMatriks.rar
http://www.ziddu.com/download/8718665/ConsoleApplicationMatriks.rar.html
ConsoleApplicationArrayList.rar
http://www.ziddu.com/download/8717664/ConsoleApplicationArrayList.rar.html
Array adalah suatu tipe data terstruktur yang berupa sejumlah data sejenis(bertipe data sama) yang jumlahnya tetap dan diberi suatu nama tertentu.
Array dapat berupa array 1 dimensi, 2 dimensi, bahkan n-dimensi. Array merupakan struktur data yang statis, yaitu jumlah elemen yang harus ditentukan terlebih dahulu, tak bisa di ubah saat program berjalan. Untuk menyatakan array dalam PASCAL kita harus terlebih dahulu: Mendefinisikan jumlah elemen array.
Array Satu Dimensi Pendefinisian array Satu Dimensi secara umum adalah sebagai berikut: array dengan tipe/jenis yang sama yang memiliki satu index saja yaitu baris saja atau kolom saja.
Array MultidimensiArray multidimensi terdiri atas dimensi satu, dimensi dua, dimensi tiga dan seterusnya. Indek pertama dapat berupa baris dan yang kedua dapat berupa kolom dan yang ketiga berupa isi atau lainnya.
Record
Sebuah record rekaman disusun oleh beberapa field. Tiap field berisi data dari tipe dasar / bentukan tertentu. Record mempunyai kelebihan untuk menyimpan suatu sekumpulan elemen data yang berbeda-beda tipenya (di banding array).
Implementasi Array dalam program
Beberapa contohnya:
ConsoleApplicationBitArray.rar
http://www.ziddu.com/download/8718294/ConsoleApplicationBitArray.rar.html
ConsoleApplicationArrayList_for_String.rar
http://www.ziddu.com/download/8717675/ConsoleApplicationArrayList_for_String.rar.html
ConsoleApplicationArray.rar
http://www.ziddu.com/download/8717545/ConsoleApplicationArray.rar.html
ConsoleApplicationArray.rar
http://www.ziddu.com/download/8717352/ConsoleApplicationArray.rar.html
Array.rar
http://www.ziddu.com/download/7844295/Array.rar.html
ConsoleApplicationMatriks.rar
http://www.ziddu.com/download/8718665/ConsoleApplicationMatriks.rar.html
ConsoleApplicationArrayList.rar
http://www.ziddu.com/download/8717664/ConsoleApplicationArrayList.rar.html
String
Array adalah sebuah struktur data yang terdiri atas banyak variabel dengan tipe data sama, dimana masing-masing elemen variabel mempunyai nilai indek. Setiap elemen array mampu untuk menyimpan satu jenis data. Array adalah suatu tipe data terstruktur yang berupa sejumlah data sejenis(bertipe data sama) yang jumlahnya tetap dan diberi suatu nama tertentu. Array dapat berupa array 1 dimensi, 2 dimensi, bahkan n-dimensi. Array merupakan struktur data yang statis, yaitu jumlah elemen yang harus ditentukan terlebih dahulu, tak bisa di ubah saat program berjalan. Untuk menyatakan array dalam PASCAL kita harus terlebih dahulu: Mendefinisikan jumlah elemen array.
Array Satu Dimensi Pendefinisian array Satu Dimensi secara umum adalah sebagai berikut: array dengan tipe/jenis yang sama yang memiliki satu index saja yaitu baris saja atau kolom saja.
Array MultidimensiArray multidimensi terdiri atas dimensi satu, dimensi dua, dimensi tiga dan seterusnya. Indek pertama dapat berupa baris dan yang kedua dapat berupa kolom dan yang ketiga berupa isi atau lainnya.
Record
Sebuah record rekaman disusun oleh beberapa field. Tiap field berisi data dari tipe dasar / bentukan tertentu. Record mempunyai kelebihan untuk menyimpan suatu sekumpulan elemen data yang berbeda-beda tipenya (di banding array).
ConsoleApplicationBitArray.rar
http://www.ziddu.com/download/8718294/ConsoleApplicationBitArray.rar.html ConsoleApplicationArrayList_for_String.rar
http://www.ziddu.com/download/8717675/ConsoleApplicationArrayList_for_String.ra
r.html
ConsoleApplicationArray.rar
http://www.ziddu.com/download/8717545/ConsoleApplicationArray.rar.html
ConsoleApplicationArray.rar
http://www.ziddu.com/download/8717352/ConsoleApplicationArray.rar.html
Array.rar
http://www.ziddu.com/download/7844295/Array.rar.html
ConsoleApplicationMatriks.rar
http://www.ziddu.com/download/8718665/ConsoleApplicationMatriks.rar.html
ConsoleApplicationArrayList.rar
http://www.ziddu.com/download/8717664/ConsoleApplicationArrayList.rar.html
Array Satu Dimensi Pendefinisian array Satu Dimensi secara umum adalah sebagai berikut: array dengan tipe/jenis yang sama yang memiliki satu index saja yaitu baris saja atau kolom saja.
Array MultidimensiArray multidimensi terdiri atas dimensi satu, dimensi dua, dimensi tiga dan seterusnya. Indek pertama dapat berupa baris dan yang kedua dapat berupa kolom dan yang ketiga berupa isi atau lainnya.
Record
Sebuah record rekaman disusun oleh beberapa field. Tiap field berisi data dari tipe dasar / bentukan tertentu. Record mempunyai kelebihan untuk menyimpan suatu sekumpulan elemen data yang berbeda-beda tipenya (di banding array).
ConsoleApplicationBitArray.rar
http://www.ziddu.com/download/8718294/ConsoleApplicationBitArray.rar.html ConsoleApplicationArrayList_for_String.rar
http://www.ziddu.com/download/8717675/ConsoleApplicationArrayList_for_String.ra
r.html
ConsoleApplicationArray.rar
http://www.ziddu.com/download/8717545/ConsoleApplicationArray.rar.html
ConsoleApplicationArray.rar
http://www.ziddu.com/download/8717352/ConsoleApplicationArray.rar.html
Array.rar
http://www.ziddu.com/download/7844295/Array.rar.html
ConsoleApplicationMatriks.rar
http://www.ziddu.com/download/8718665/ConsoleApplicationMatriks.rar.html
ConsoleApplicationArrayList.rar
http://www.ziddu.com/download/8717664/ConsoleApplicationArrayList.rar.html
Salam perkenalan
Salam Bahagia untuk kita semua.
Puji syukur saya ucapkan kepada yang maha kuasa yang telah memberikan berkahnya kepada saya sehingga saya dapat menyelesaikan Blog Struktur Data Dalam Implementasi Program.Blog ini saya buat sebagai kumpulan dari materi Struktur data dan Algoritma yang saya dapatkan dari berbagai sumber.
Semoga dengan kehadiran blog ini didalam dunia Maya dapat menambah perbendaharaan materi Struktur Data.
Akhir kata semoga kehadiran Blog ini dapat menambah materi untuk pembelajaran bagi kita semua.
Puji syukur saya ucapkan kepada yang maha kuasa yang telah memberikan berkahnya kepada saya sehingga saya dapat menyelesaikan Blog Struktur Data Dalam Implementasi Program.Blog ini saya buat sebagai kumpulan dari materi Struktur data dan Algoritma yang saya dapatkan dari berbagai sumber.
Semoga dengan kehadiran blog ini didalam dunia Maya dapat menambah perbendaharaan materi Struktur Data.
Akhir kata semoga kehadiran Blog ini dapat menambah materi untuk pembelajaran bagi kita semua.
Subscribe to:
Posts (Atom)
Info Gadget Terbaru
*****
*****
*****
