Pencarian & Pengurutan Data
Pencarian [Searching]
Searching [Pencarian Data] sering juga disebut table look-up atau storage and retrieval information adalah suatu proses untuk mengumpulkan sejumlah informasi di dalam pengingat komputer dan kemudian mencari kembali informasi yang diperlukan secepat mungkin.
Dalam kehidupan sehari-hari sebenarnya kita sering melakukan pencarian data. Sebagai contoh, jika kita menggunakan Kamus untuk mencari kata-kata dalam Bahasa Inggris yang belum diketahui terjemahannya dalam Bahasa Indonesia. Contoh lain saat kita menggunakan buku telepon untuk mencari nomor telepon teman atau kenalan dan masih banyak contoh yang lain.
Pencarian data sering juga disebut table look-up atau storage and retrieval information adalah suatu proses untuk mengumpulkan sejumlah informasi di dalam pengingat komputer dan kemudian mencari kembali informasi yang diperlukan secepat mungkin.
Algoritma pencarian [searching algorithm] adalah algoritma yang menerima sebuah argumen kunci dan dengan langkah-langkah tertentu akan mencari rekaman dengan kunci tersebut. Setelah proses pencarian dilaksanakan, akan diperoleh salah satu dari dua kemungkinan, yaitu data yang dicari ditemukan [successful] atau tidak ditemukan [unsuccessful].
Metode pencarian data dapat dilakukan dengan dua cara yaitu pencarian internal [internal searching] dan pencarian eksternal [external searching]. Pada pencarian internal, semua rekaman yang diketahui berada dalam pengingat komputer sedangakan pada pencarian eksternal, tidak semua rekaman yang diketahui berada dalam pengingat komputer, tetapi ada sejumlah rekaman yang tersimpan dalam penyimpan luar misalnya pita atau cakram magnetis.
Selain itu metode pencarian data juga dapat dikelompokan menjadi pencarian statis [static searching] dan pencarian dinamis [dynamic searching]. Pada pencarian statis, banyaknya rekaman yang diketahui dianggap tetap, pada pencarian dinamis, banyaknya rekaman yang diketahui bisa berubah-ubah yang disebabkan oleh penambahan atau penghapusan suatu rekaman.
Ada macammacam teknik pencarian yaitu pencarian sekuensial dan pencarian biner. Perbedaan dari dua teknik ini terletak pada keadaan data. Pencarian sekuensial digunakan apabila data dalam keadaan acak atau tidak terurut. Sebaliknya, pencarian biner digunakan pada data yang sudah dalam keadaan urut dan tambahannya yaitu Pencarian Beruntun dengan Sentinel jika pencarian bertujuan untuk menambahkan elemen baru setelah elemen terakhir larik, maka terdapat sebuah varian dari metode pencarian beruntun yang mangkus
- Pencarian Linear atau sekuensial
Pencarian berurutan sering disebut pencarian linear merupakan metode pencarian yang paling sederhana. Pencarian berurutan menggunakan prinsip sebagai berikut : data yang ada dibandingkan satu per satu secara berurutan dengan yang dicari sampai data tersebut ditemukan atau tidak ditemukan.
Pada dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai dengan jumlah data. Pada setiap pengulangan, dibandingkan data ke-i dengan yang dicari. Apabila sama, berarti data telah ditemukan. Sebaliknya apabila sampai akhir pengulangan tidak ada data yang sama, berarti data tidak ada. Pada kasus yang paling buruk, untuk N elemen data harus dilakukan pencarian sebanyak N kali pula.
- Pencarian Biner [Binary Search]
Salah satu syarat agar pencarian biner dapat dilakukan adalah data sudah dalam keadaan urut. Dengan kata lain, apabila data belum dalam keadaan urut, pencarian biner tidak dapat dilakukan. Dalam kehidupan sehari-hari, sebenarnya kita juga sering menggunakan pencarian biner. Misalnya saat ingin mencari suatu kata dalam kamus.
Prinsip dari pencarian biner dapat dijelaskan sebagai berikut : mula-mula diambil posisi awal 0 dan posisi akhir = N – 1, kemudian dicari posisi data tengah dengan rumus [posisi awal + posisi akhir] / 2. Kemudian data yang dicari dibandingkan dengan data tengah. Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah –1. Jika lebih besar, porses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah + 1. Demikian seterusnya sampai data tengah sama dengan yang dicari.
Untuk lebih jelasnya perhatikan contoh berikut. Misalnya ingin mencari data 17 pada sekumpulan data berikut :
3 9 11 12 15 17 20 23 31 35
awal tengah akhir
Mula-mula dicari data tengah, dengan rumus [0 + 9] / 2 = 4. Berarti data tengah adalah data ke-4, yaitu 15. Data yang dicari, yaitu 17, dibandingkan dengan data tengah ini. Karena 17 > 15, berarti proses dilanjutkan tetapi kali ini posisi awal dianggap sama dengan posisi tengah + 1 atau 5.
3 9 11 12 15 17 20 23 31 35
awal tengah akhir
Data tengah yang baru didapat dengan rumus [5 + 9] / 2 = 7. Berarti data tengah yang baru adalah data ke-7, yaitu 23. Data yang dicari yaitu 17 dibandingkan dengan data tenah ini. Karena 17 < 23, berarti proses dilanjukkan tetapi kali ini posisi akhir dianggap sama dengan posisi tengah – 1 atau 6.
3 9 11 12 15 17 20 23 31 35
awal=tengah akhir
Data tengah yang baru didapat dengan rumus [5 + 6] / 2 = 5. Berarti data tengah yang baru adalah data ke-5, yaitu 17. data yang dicari dibandingkan dengan data tengah ini dan ternyata sama. Jadi data ditemukan pada indeks ke-5.
Pencarian biner ini akan berakhir jika data ditemukan atau posisi awal lebih besar daripada posisi akhir. Jika posisi sudah lebih besar daripada posisi akhir berarti data tidak ditemukan.
Untuk lebih jelasnya perhatikan contoh pencarian data 16 pada data diatas. Prosesnya hampir sama dengan pencarian data 17. Tetapi setelah posisi awal 5 dan posisi akhir 6, data tidak ditemukan dan 16 < 17, maka posisi akhir menjadi posisi tengah – 1 atau = 4 sedangkan posisi awal = 5.
3 9 11 12 15 17 20 23 31 35
akhir awal
Disini dapat dilihat bahwa posisi awal lebih besar daripada posisi akhir, yang artinya data tidak ditemukan.
- Pencarian Beruntun dengan Sentinel
Jika pencarian bertujuan untuk menambahkan elemen baru setelah elemen terakhir larik, maka terdapat sebuah varian dari metode pencarian beruntun yang mangkus. Nilai x yang akan dicari sengaja ditambahkan terlebih dahulu. Data yang ditambahkan setelah elemen terakhir larik ini disebut sentinel.
Perhatikan array data berikut ini:
0 1 2 3 4 5 6 indeks
ffea ffeb ffec ffed ffef fffa fffb alamat
Penjelasannya :
Terdapat 6 buah data dalam array [dari indeks 0 s/d 5] dan terdapat 1 indeks array tambahan [indeks ke 6] yang belum berisi data [disebut sentinel]
Array pada indeks ke 6 berguna untuk menjaga agar indeks data berada pada indeks 0 s/d 5 saja. Bila pencarian data sudah mencapai array indeks yang ke-6 maka berarti data TIDAK ADA, sedangkan jika pencarian tidak mencapai indeks ke-6, maka data ADA.
Pengurutan [Sorting]
Sorting berarti proses pengurutan. Sorting atau pengurutan data adalah proses yang sering
harus dilakukan dalam pengolahan data. Sort dalam hal ini diartikan mengurutkan data yang berada dalam suatu tempat penyimpanan, dengan urutan tertentu baik urut menaik [ascending] dari nilai terkecil sampai dengan nilai terbesar, atau urut menurun [descending] dari nilai terbesar sampai dengan nilai terkecil.
Metode Sorting
Berikut adalah beberapa jenis dari metode sorting, antara lain:
- Bubble Sort atau Exchange Sort
Ide dari Bubble sort adalah gelembung air yang akan “mengapung” untuk table yang terurut menaik [ascending]. Elemen bernilai kecil akan “diapungkan” [ke indeks terkecil], artinya diangkat ke “atas” [indeks terkecil] melalui pertukaran. Karena algoritma ini melakukan pengurutan dengan cara membandingkan elemen-elemen data satu sama lain, maka bubble sort termasuk ke dalam jenis algoritma comparison-based sorting.
Metode gelembung [bubble sort] sering juga disebut dengan metode penukaran [exchange sort] adalah metode yang mengurutkan data dengan cara membandingkan masing-masing elemen, kemudian melakukan penukaran bila perlu. Metode ini mudah dipahami dan diprogram, tetapi bila dibandingkan dengan metode lain yang kita pelajari, metode ini merupakan metode yang paling tidak efisien.
Proses dalam Bubble sort dilakukan sebanyak N-1 langkah [pass] dengan N adalah ukuran array. Pada akhir setiap langkah ke – I , array L[0..N] akan terdiri atas dua bagian, yaitu bagian yang sudah terurut L[0..I] dan bagian yang belum terurut L[I+1..N-1]. Setelah langkah terakhir, diperoleh array L[0..N-1] yang terurut menaik.
algoritmanya dapat ditulis secara global sebagai berikut :
Untuk setiap pass ke – I = 0,1,………., N-2 , lakukan :
Mulai dari elemen J = N-1, N-2,….., I + 1, lakukan :
- Bandingkan L[J-1] dengan L[J]
- Pertukarkan L[J-1] dengan L[J] jika L[J-1] > L[J]
Rincian setiap pass adalah sebagai berikut :
Pass 1: I = 0. Mulai dari elemen J = N-1,N–2,…,1, bandingkan L[J-1] dengan L[J]. Jika L[J-1] > L[J], pertukarkan L[J-1] dengan L[J]. Pada akhir langkah 1, elemen L[0] berisi harga minimum pertama.
Pass 2: I = 1. Mulai dari elemen J = N-1,N–2,…,2, bandingkan L[J-1] dengan L[J]. Jika L[J-1] > L[J], pertukarkan L[J-1] dengan L[J]. Pada akhir langkah 2, elemen L[1] berisi harga minimum kedua dan array L[0..1] terurut, sedangkan L[2..[N-1]] belum terurut.
Pass 3: I = 2. Mulai dari elemen J = N-1,N–2,…,3, bandingkan L[J-1] dengan L[J]. Jika L[J-1] > L[J], pertukarkan L[J-1] dengan L[J]. Pada akhir langkah 3, elemen L[2] berisi harga minimum ketiga dan array L[0..2] terurut, sedangkan L[3..[N-1]] belum terurut.
………
Pass N-1: Mulai dari elemen J = N-1, bandingkan L[J-1] dengan L[J]. Jika L[J-1] > L[J], pertukarkan L[J-1] dengan L[J].
Pada akhir langkah N-2, elemen L[N-2] berisi nilai minimun ke [N-2] dan array L[0..N-2] terurut menaik [elemen yang tersisa adalah L[N-1], tidak perlu diurut karena hanya satu-satunya].
Misal array L dengan N = 5 buah elemen yang belum terurut. Array akan diurutkan secara ascending [menaik].
0 1 2 3 4
Pass 1 :
I = 0 ;J= N-1= 4 8 9 7 1 6
J = 3 8 9 1 7 6
J = 2 8 1 9 7 6
J = 1 1 8 9 7 6
Hasil akhir langkah 1 :
0 1 2 3 4
Pass 2 :
I = 1 ;J= N-1= 4 1 8 9 6 7
J = 3 1 8 6 9 7
J = 2 1 6 8 9 7
Hasil akhir langkah 2 :
0 1 2 3 4
Pass 3 :
I = 2 ;J= N-1= 4 1 6 8 7 9
J = 3 1 6 7 8 9
Hasil akhir langkah 3 :
0 1 2 3 4
Pass 4 :
I = 3 ;J= N-1= 4 1 6 7 8 9
Hasil akhir langkah 4 :
0 1 2 3 4
Selesai. Array L sudah terurut !!
Algoritma Selection sort memilih elemen maksimum atau minimum array, lalu menempatkan elemen maksimum atau minimum itu pada awal atau akhir array [tergantung pada urutannya ascending atau descending]. Selanjutnya elemen tersebut tidak disertakan pada proses selanjutnya. Karena setiap kali selection sort harus membandingkan elemen-elemen data, algoritma ini termasuk dalam comparison-based sorting.
Terdapat dua pendekatan dalam metode pengurutan dengan Selection Sort :
- Algoritma pengurutan maksimum [maximum selection sort], yaitu memilih elemen maksimum sebagai basis pengurutan.
- Algoritma pengurutan minimum [minimum selection sort], yaitu memilih elemen minimum sebagai basis pengurutan.
Rincian setiap pass adalah sebagai berikut :
Langkah 1 : Cari elemen maksimum di dalam L[0..[N-1]]
Pertukarkan elemen maksimum dengan elemen L[N-1]
Langkah 2 : Cari elemen maksimum di dalam L[0..N-2]
Pertukarkan elemen maksimum dengan elemen L[N-2]
Langkah 3 : Cari elemen maksimum di dalam L[0..N-3]
Pertukarkan elemen maksimum dengan elemen L[N-3]
…………..
Langkah N-1 : Tentukan elemen maksimum di dalam L[0..1]
Pertukarkan elemen maksimum dengan elemen L[0]
[elemen yang tersisa adalah L[0], tidak perlu diurut karena hanya satu-satunya].
Jadi , pada setiap pass pengurutan terdapat proses mencari harga maksimum dan proses pertukaran dua buah elemen array.
Misal, terdapat array L dengan N = 5 buah elemen yang belum terurut. Array akan diurutkan secara Ascending [menaik], dengan algoritma maximum selection sort.
Pass 1 :
Ÿ Cari elemen maksimum di dalam array L[0..4]. Maks=L[2]=12
Ÿ Tukar Maks dengan L[4], diperoleh :
Pass 2 :
[berdasarkan susunan array pada Pass 1]
Ÿ Cari elemen maksimum di dalam array L[0..3]. Maks=L[0]=9
Ÿ Tukar Maks dengan L[3], diperoleh :
Pass 3:
[berdasarkan susunan array pada Pass 2]
Ÿ Cari elemen maksimum di dalam array L[0..2]. Maks=L[1]=7
Ÿ Tukar Maks dengan L[2], diperoleh :
Pass 4 :
[berdasarkan susunan array pada Pass 3]
Ÿ Cari elemen maksimum di dalam array L[0..1]. Maks=L[0]=6
Ÿ Tukar Maks dengan L[1], diperoleh :
Selesai, array L sudah terurut secara Ascending.
Insertion sort adalah sebuah algoritma pengurutan yang membandingkan dua elemen data pertama, mengurutkannya, kemudian mengecek elemen data berikutnya satu persatu dan membandingkannya dengan elemen data yang telah diurutkan. Karena algoritma ini bekerja dengan membandingkan elemen-elemen data yang akan diurutkan, algoritma ini termasuk pula dalam comparison-based sort
Ide dasar dari algoritma Insertion Sort ini adalah mencari tempat yang “tepat” untuk setiap elemen array, dengan cara sequential search. Proses ini kemudian menyisipkan sebuah elemen array yang diproses ke tempatnya yang seharusnya. Proses dilakukan sebanyak N-1 tahapan [dalam sorting disebut sebagai “pass“]
Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan dan yang sudah diurutkan. Elemen pertama diambil dari bagian array yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.
Tahapan Insertion Sort:
- Dimulai dari L[1] : Simpan nilai L[1] ke variabel X.
[Pass-1] Geser masing-masing satu langkah ke kanan semua nilai yang ada disebelah kiri L[1] satu persatu apabila nilai tersebut lebih besar dari X.
Setelah itu insert-kan [sisipkan] X di bekas tempat nilai yang terakhir digeser.
- Dilanjutkan ke L[2]: Simpan nilai L[2] ke variabel X
[Pass-2] Geser masing-masing satu langkah ke kanan semua nilai yang ada disebelah kiri L[2] satu persatu apabila nilai tersebut lebih besar dari X.
Setelah itu insert-kan [sisipkan] X di bekas tempat nilai yang terakhir di geser.
- Demikian seterusnya untuk L[3], L[4],L[5], dan terakhir L[6] bila n = 7. Sehingga untuk n = 7 ada 6 pass proses pengurutan.
Berikut ilustrasi dari 6 pass tersebut:
| Data awal: | 15 | 10 | 7 | 22 | 17 | 5 | 12 | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||
| Pass-1: | 15 | 10 | 7 | 22 | 17 | 5 | 12 | 10 | ||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | X | |||
Pass 1 dimulai dari kolom L[1], X=L[1]=10
15 lebih besar dari 10, maka geser 15 ke kanan. Proses selesai karena sudah sampai kolom 1. Kemudian insert X menggantikan 15.
| 15 | 15 | 7 | 22 | 17 | 5 | 12 | ||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||||||||
| 10 | 15 | 7 | 22 | 17 | 5 | 12 | ||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||||||||
| Hasil Pass 1: | 10 | 15 | 7 | 22 | 17 | 5 | 12 | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||
| Pass-2: | 10 | 15 | 7 | 22 | 17 | 5 | 12 | 7 | ||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | X | |||
Pass 2 dimulai dari L[2], X=L[2]=7.
15 lebih besar dari 7, maka geser 15 ke kanan. 10 lebih besar dari 7, maka geser 10 ke kanan. Proses selesai karena sudah sampai kolom 1. Kemudian insert X menggantikan 10.
| 15 | 15 | 22 | 17 | 5 | 12 | |||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||||||||
| 10 | 10 | 15 | 22 | 17 | 5 | 12 | ||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||||||||
| 7 | 10 | 15 | 22 | 17 | 5 | 12 | ||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||||||||
| Hasil Pass 2: | 7 | 10 | 15 | 22 | 17 | 5 | 12 | |||||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||||||||||||
| Pass-3: | 7 | 10 | 15 | 22 | 17 | 5 | 12 | 22 | ||||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | X | |||||||||||
Pass 3 dimulai dari L[3], X=L[3]=22.
15 tidak lebih besar dari 22, maka proses selesai. Kemudian insert X menggantikan 22.
Proses berlanjut sampai Pass 6. Hasil tiap pass dapat digambarkan sebagai berikut:
| Data awal: | 15 | 10 | 7 | 22 | 17 | 5 | 12 | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||
| Pass 1: | 10 | 15 | 7 | 22 | 17 | 5 | 12 | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||
| Pass 2: | 7 | 10 | 15 | 22 | 17 | 5 | 12 | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||
| Pass 3: | 7 | 10 | 15 | 22 | 17 | 5 | 12 | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||
| Pass 4: | 7 | 10 | 15 | 17 | 22 | 5 | 12 | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||
| Pass 5: | 5 | 7 | 10 | 15 | 17 | 22 | 12 | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||
| Pass 6: | 5 | 7 | 10 | 12 | 15 | 17 | 22 | |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||
Selesai array L sudah terurut secara Ascending [menaik]
Metode Quick sering disebut juga metode partisi [partition exchange sort]. Metode ini diperkenalkan pertama kali oleh C.A.R. Hoare pada tahun 1962. Untuk mempertinggi efektifitas dari metode ini, digunakan teknik menukarkan dua elemen dengan jarak yang cukup besar.
Dasar strateginya adalah “memecah dan menguasai”. Quick sort dimulai dengan menscan daftar yang disortir untuk nilai median. Nilai ini, yang disebut tumpuan [pivot], kemudian dipindahkan ke satu sisi pada daftar dan butir-butir yang nilainya lebih besar dari tumpuan di pindahkan ke sisi lain.
Pertama-tama x = j. Pada keadaan seperti ini nilai balik subrutin partisi berupa j.
|
|
Metode heap sort adalah metode dari pengembangan tree. Heap sort melakukan suatu pengurutan menggunakan suatu struktur data yang di sebut heap. Heap memiliki kompleksitas yang besar dalam pembuatan kodenya, tetapi heap sort mampu mengurutkan data-data yang sangat banyak dengan waktu yang cepat.
Dalam sorting biasanya mempunyai sebuah aturan, berikut adalah aturan dari heap sort :
a. Untuk mengisikan heap dimulai dari level 1 sampai ke level dibawahnya, bila dalam level yang sama semua kunci heap belum terisi maka tidak boleh mengisi dibawahnya.
b. Heap dlm kondisi terurut apabila left child parent.
c. Penambahan kunci diletakkan pada posisi terakhir dari level dan disebelah kanan child yg terakhir, kemudian diurutkan dengan cara upheap.
d. Bila menghapus heap dengan mengambil kunci pada parent di level 1 kemudian digantikan posisi kunci terakhir, selanjutnya disort kembali metode downheap.
Berikut adalah langkah-langkahnya dari metode heap sort :
Dalam langkah-langkahnya heap sort terbagi menjadi 2 langkah yaitu insert_heap dan build_heap
Pada bagian ini bertujuan untuk penghapusan suatu simpul pada heap tree. Pemilihan sebuah simpul untuk ditempatkan di posisi yang lebih atas, dan menjaga tree tersebut tetap sebuah heaptree.
Berikut langkahnya :
- Setiap simpul yang dihapus[low] dicari anaknya yang memiliki kunci terbesar/terkecil.
- Anak dengan kunci yang lebih besar dipromosikan ke tempat simpul yang di hapus.
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.
Pada bagian ini kita akan merapikan data-data yang telah acak tadi, sehingga membentuk heap yang sempurna. kita dapat menggunakan fungsi insert_heap untuk memasukkan setiap masukan ke bagian heap yang terdiri dari semua masukan yang masuk. Sehingga jadilah heap yang sempurna.
Contoh :
Misalkan terdapat suatu array bilangan bulat yang terdiri dari sepuluh buah anggota dengan nilai data 11, 9, 8, 27, 16, 25, 12, 13, 34, dan 43. Kita akan mengurutkan data diatas dengan menggunakan heapsort. Pertama-tama, array di atas dapat dipandang sebagai suatu Complete Binary Tree [CBT] sebagai berikut:
Selanjutnya algoritma metoda heapify dilakukan dengan iterasi dari subtree node ke-4, ke-3, dan seterusnya berturut-turut hingga mencapai root [akar]. Iterasi dilakukan mulai dari node ke-4 karena N/2 dalam contoh di atas adalah 5. Dan elemen kelima dari array memiliki nilai indeks 4 sebab indeks array biasanya diawali dari 0. Penerapan algoritma metoda heapify terhadap Complete Binary Tree [CBT] pada contoh di atas menghasilkan operasi-operasi pertukaran sebagai berikut:
- Subtree node ke-4: pertukaran 16 dengan 43
- Subtree node ke-3: pertukaran 27 dengan 34
- Subtree node ke-2: pertukaran 8 dengan 25
- Subtree node ke-1: pertukaran 9 dengan 43, lalu pertukaran 9 dengan 16
- Subtree node ke-0: pertukaran 11 dengan 43, lalu pertukaran 11 dengan 34, serta akhirnya pertukaran 11 dengan 27 Perubahan-perubahan [pertukaran] tersebut dapat digambarkan sebagai berikut:
Semua perubahan di atas terjadi dalam array yang bersangkutan, sehingga pada akhirnya diperoleh tree terakhir yang merupakan heap tree. Sementara itu, dalam iterasi yang melakukan/menerapkan algoritma metoda remove[ ] dan algoritma metoda reheapify[] akan terjadi pemrosesan berikut:
- Setelah 43 di-remove dan 9 menggantikan posisi yang ditinggalkan oleh 43, maka terjadi reheapify: penukaran 9 dengan 34, 9 dengan 27, dan 9 dengan 13.
Dan data yang telah terurut adalah 43
- Setelah 34 di-remove dan 11 menggantikan posisi yang ditinggalkan oleh 34, maka terjadi reheapify: penukaran 11 dengan 27, dan 11 dengan 16.
Dan data yang telah terurut adalah 34, 43
- Setelah 27 di-remove dan 9 menggantikan posisi yang ditinggalkan oleh 27, maka terjadi reheapify: penukaran 9 dengan 25, dan 9 dengan 12
Dan data yang telah terurut adalah 27, 34, 43
Demikian seterusnya dilakukan algoritma metoda remove dan algoritma metoda reheapify hingga tidak ada lagi node yang tersisa. Dan pada akhirnya akan didapatkan hasil data yang telah terurut adalah 8, 9, 11, 12, 13, 16, 25, 27, 34, 43.
Daftar Pustaka
file:///E:/kelas%20XI/PD/bahan%20pd/Cahya_%20pengurutan%20dan%20pencarian%20%28pemprograman%20terstruktur%29.html
file:///E:/kelas%20XI/PD/bahan%20pd/Tugas%20Kuliah_%20SEKILAS%20TENTANG%20METODE-METODE%20SORTING.html
| //upload.wikimedia.org/wikipedia/commons/4/4d/Heapsort-example.gif |