Desain Dan Analisis Algoritma Heap Sort [Makalah]
DESAIN DAN ANALISIS ALGORITMA
“HEAP SORT”
Oleh:
NAMA KELOMPOK
Dewa Ketut Satriawan Suditresna Jaya ( 1615051046 )
Ryan Ardiansyah Putra ( 1615051112 )
Komang Eric Widhi Antara ( 1615051019 )
KELAS : 3B
PENDIDIKAN TEKNIK INFORMATIKA
FAKULTAS TEKNIK DAN KEJURUAN
UNIVERSITAS PENDIDIKAN GANESHA
2017
KATA PENGANTAR
Syukur alhamdulillah, merupakan satu kata yang sangat pantas kami ucapkan kepada Allah SWT, Tuha Yang Maha Esa, yang alasannya yaitu bimbingannyalah maka kami bisa menuntaskan sebuah makalah yang .berjudul “PENJELASAN TENTANG HEAP SORT“
Kami menyadari bahwa masih sangat banyak kekurangan yang fundamental pada makalah ini. Oleh karna itu kami mengundang pembaca untuk menawarkan kritik dan saran yang bersifat membangun semoga bisa lebih baik lagi di waktu yang akan datang. Terimakasih, dan semoga makalah ini bisa menawarkan sumbangsih nyata bagi kita semua.
Singaraja,13 Desember 2017
Penyusun
DAFTAR ISI
BAB I
PENDAHULUAN
Pengurutan data (data sorting) merupakan bab dari pengolahan data informasi. Dari data-data yang telah didapat, ada kalanya data tersebut harus diurutkan terlebih dahulu menurut hukum yang lebih dulu ditentukan. Berdasarkan nilai maupun alphabet misalnya. Metode-metode pengurutan data pun ada banyak sekali jenis. Mulai dari binary sort, insertion sort, merge sort, heap sort dll. Penggunaan metode mana yang akan digunakan nantinya tergantung dari jenis maupun kuantitas data yang diolah.
Heap sort, algoritma pengurutan, merupakan salah satu metode pengurutan yang sering digunakan. Melalui jurnal ini akan dibahas teknik pencarian ini beserta kelebihan dan kekurangannya. Oleh alasannya yaitu itu, teknik untuk menentukan algoritma pengurutan yang tepat, sesuai dengan kebutuhan, dan mangkus sangat dibutuhkan alasannya yaitu masing-masing algoritma pengurutan mempunyai karakteristik yang berbedabeda. Heap sort merupakan salah satu referensi algoritma pengurutan yang mempunyai kompleksitas waktu asimptotik terbaik serta menerapkan teknik yang unik/khas di dalam memecahkan dilema pengurutan, yaitu dengan memakai heap tree.
1.2 Rumusan Masalah
1. Apa pengertian dari heap sort ?
2. Apa saja Aturan-aturan , kelebihan dan kelemahan dalam heap sort .?
3. Bagaimana menerapkan Algoritma Pengurutan Heap Sort?
1.2 Tujuan Penulisan
Tujuan penulisan makalah ini tidak lain yaitu untuk memahami apa itu heap sort, Aturan , kelebihan dan kelemahan dalam heap sort ., dan bagaimana menerapkan algoritma pengurutan heap sort. Hal ini juga bertujuan semoga kita semua bisa menambah wawasan tentang pengurutan data .
BAB II
PEMBAHASAN
2.1 Pengertian Heap Sort
Pohon heap yaitu struktur data yang berbentuk pohon yang memenuhi sifat-sifat heap yaitu bila B yaitu anak dari A, maka nilai yang tersimpan di simpul A lebih besar atau sama dengan nilai yang tersimpan di simpul B. Hal ini menyebabkan 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 yaitu min heap). Karena itulah, heap biasa digunakan untuk mengimplementasikan priority queue. Operasi-operasi yang digunakan untuk heap yaitu :
1. Delete-max atau delete-min: menghapus simpul akar dari sebuah max- atau minheap.
2. Increase-key atau decrease-key : mengubah nilai yang tersimpan di suatu simpul.
3. Insert: menambahkan sebuah nilai ke dalam heap.
4. Merge: menggabungkan dua heap untuk membentuk sebuah heap gres yang berisi semua elemen pembentuk heap tersebut.
Jenis-jenis Heap :
1. Binary heap : Binary heap yaitu heap yang dibentuk dengan memakai pohon biner.
2. Binomial heap : Binomial heap yaitu heap yang dibentuk dengan memakai pohon binomial. Pohon binomial bila didefinisikan secara rekursif adalah:
3. Sebuah pohon binomial dengan tinggi 0 yaitu simpul tunggal
Sebuah pohon binomial dengan tinggi k mempunyai sebuah simpul akar yang anak-anaknya yaitu akar-akar pohonpohon binomial dengan tinggi k-1,k- 2,…,2,1,0.
4. Fibonacci Heap
Fibonacci heap yaitu kumpulan pohon yang membentuk minimum heap. Pohon dalam struktur data ini tidak mempunyai bentuk yang tertentu dan pada kasus yang ekstrim heap ini mempunyai semua elemen dalam pohon yang berbeda atau sebuah pohon tunggal dengan tinggi n. Keunggulan dari Fibonacci heap yaitu saat menggabungkan heap cukup dengan menggabungkan dua list pohon
Metode heap sort yaitu metode dari pengembangan tree. Metode sorting ini mengurutkan data menurut perbandingan, dan merupakan salah satu algoritma pengurutan tercepat alasannya yaitu bisa mengurutkan data yang sangat banyak dengan waktu yang cepat. Algoritma Heap Sort mempunyai kompleksitas yang besar dalam pembuatan kodenya. Programmer sering memakai ini saat berhadapan dengan array yang jumlahnya sangat besar. Algoritma ini bekerja dengan menentukan elemen terbesar (atau terkecil) dari sebuah daftar elemen, dan diletakkan pada final (atau awal) dari daftar tersebut. Heap sort menuntaskan sebuah pengurutan memakai struktur data yang disebut heap. Algoritma ini dimulai dengan membangun sebuah array heap dengan membangun tumpukan dari kumpulan data, kemudian memindahkan data terbesar ke bab belakang dari sebuah tabel hasil. Setelah itu, array heap dibangun kembali, kemudian mengambil elemen terbesar untuk diletakkan di sebelah item yang telah dipindahkan tadi. Hal ini diulang hingga array heap habis.
Jadi secara umum, algoritma ini memerlukan dua buah tabel; satu tabel untuk menyimpan heap, dan satu tabel lainnya untuk menyimpan hasil. Walaupun lebih lambat dari Merge Sort atau Quick Sort, algoritma ini cocok untuk digunakan pada data yang berukuran besar.
2.2 Aturan , Kelebihan dan Kelemahan Dalam Heap Sort
v Beberapa hukum dalam Heap Sort sebagai berikut :
· Untuk mengisikan heap dimulai dari level 1 hingga ke level dibawahnya, bila dalam level yang sama semua kunci heap belum terisi maka dilarang mengisi dibawahnya.
· Heap dalam kondisi terurut apabila left child <> parent.
· Penambahan kunci diletakkan pada posisi terakhir dari level dan disebelah kanan child yg terakhir, kemudian diurutkan dengan cara upheap.
· Bila menghapus heap dengan mengambil kunci pada parent di level 1 kemudian digantikan posisi kunci terakhir, selanjutnya disort kembali metode downheap.
· Dalam langkah-langkahnya heap sort terbagi menjadi 2 langkah yaitu insert_heap dan build_heap.
v Kelebihan Heap Sort
· Algoritma Heap Sort banyak digunakan alasannya yaitu efisiensi waktunya.
· Penggunaan memori yang sedikit.
v Kekurangan Heap Sort
· Heap Sort membutuhkan banyak ruang memori untuk proses pengurutan.
· Algoritmanya yang memilki kompleksitas yang besar.
2.3 Penerapan Algoritma Pengurutan Heap Sort
Penjelasan :
Kita punya 7 data yang masih acak-acakan dan tidak teratur, kini kita akan mengurutkannya dengan metode Heap sort. Sebelum kita urutkan secara ascending, terlebih dahulu kita memasukkannya ke heap mode.
1. Pertama kita masukkan rangkaian data ke heap tree. Masukkan data pertama yaitu 7 menjadi parent.
2. Masukkan data berikutnya yaitu 1 menjadi child dari 7. Masukkan ke bab kiri terlebih dahulu.
3. Masukkan data berikutnya yaitu 3 ke child bab kanan.
4. Masukkan data berikutnya yaitu 15 menjadi child dari 1. Masukkan data berikutnya yaitu 4 menjadi child dari 1 di bab kanan.
5. Masukkan data berikutnya yaitu 9 menjadi child dari 3. Masukkan data berikutnya yaitu 11 menjadi child dari 3 di bab kanan.
6. Lalu bandingkan tree bab yang paling ujung yaitu tree dengan data parent 3, yang mempunyai child kiri dan kanan yaitu data 9 dan 11. Karna parent dari pohon ini masih lebih kecil dari childnya maka datanya akan ditukar dengan nilai yang lebih besar di bab child yang dimilikinya dalam hal ini terjadi penukaran data 11 dengan data 3 sehingga data 11 kini menjadi parent dari child 9 dan 3. (lihat langkah 1 dan 2 pada gambar bandingkanperubahan yang terjadi).
7. Setelah itu bandingkan data parent tree dibagian kanan yakni data parent 1 yang mempunyai anak data 15 dan 4, kembali langi menyerupai langkah sebelumnya yakni bandingkan data parent pada tree tersebut dengan anak data dibawahnya bila ada data yang lebih besar dari data parentnya maka tukarkan, dalam hal ini data 1 ditukarkan dengan anak data 15 sehingga 15 menjadi parent di pohonnya tersebut. (lihat langkah 2 dan 3 pada gambar bandingkanperubahan yang terjadi).
8. Selanjutnya sesudah selesai mengcompare data pada masing masing pohon dibawah maka kita lanjut untuk mengcompare data pada parent utama yang kini telah mempunyai anak data 15 dan 11, menyerupai langkah sebelumnya yakni bila ada data yang lebih besar dari parentnya maka parent akan digantikan dengan angka yang tersebsar tersebut. Dalam hal ini kita menukarkan data 7 dengan data 15. Sehingga urutan datanya kini yaitu 15, 7, 11, 1, 4, 9, 3 data ini masih belum terurut dari kecil ke besar. (lihat langkah 4 pada gambar).
9. Karna data parent utama yakni data 15 sudah merupakan data terbesar maka proses selanjutnya yaitu menukar parent utama tersebut dengan data terakhir yaitu 3. (lihat langkah 4 dan 5 pada gambar)
10. Karna nilai 15 yang telah ditukarkan tadi sudah menjadi nilai terbesar maka beliau akan tetap berada pada urutan final dan tidak lagi mendapat proses apa-apa lagi angka 15 sudah keluar dari heap. Sehingga untuk menunjukan bahwa angka 15 sudah tidak diproses lagi (untuk mempermudah) maka angka 15 dicoret. (lihat langkah 5 pada gambar). Sehingga urutan datanya kini yaitu 3, 7, 11, 1, 4, 9, 15 dengan angka 15 terakhir sudah ditemukan dan merupakan angka terbesar sehingga akan tetap berada di posisi akhir.
11. Kembali lagi menyerupai langkah 6, yaitu membandingkan nilai data pada masing masing parent namun bedanya angka 15 yang tercoret itu tidak di lakukan proses compare lagi. Setelah menemukan nilai data terbesar dan berada pada posisi parent utama , kembali lagi menyerupai langkah sebelumnya yaitu menukarkannya dengan nilai data terakhir. Begitu seterusnya hingga data terurut (lihat langkah 6 pada gambar dan seterusnya) sehingga data kesudahannya yaitu 1, 3, 4, 7, 9, 11, 15
Mengapa kita harus mencari nilai terbesar menjadi parent dan menukarkan nilai terbesar tersebut pada nilai data terakhir?
Karena kita ingin mengurutkan data secara ascending, maka yang kita lakukkan pada tree yaitu melakukkan descending yaitu kebalikannya begitu juga sebaliknya bila kita menginginkan pengurutan secara descending maka yang kita lakukan pada tree yaitu melaksanakan ascending. Karena kini nilai terbesar yaitu 15 sudah pada posisi parent kita keluarkan dari heap dan letakkan ke paling kanan baris dan sudah terhitung fully sorted (sudah tersusun) begitu seterusnya.
BAB III
PENUTUP
A. Kesimpulan
Dari pembagian terstruktur mengenai di atas, kami sanggup menyimpulkan bahwa Heap Sort merupakan salah satu dari 6 jenis metode sort atau sorting (melakukkan pengurutan). Heap sort ini memakai teknik sorting dengan memakai teknik heap. Teknik tersebut tersebut merupakan teknik pengelolaan data yang memakai binary tree. Data yang dikelola maksudnya yaitu bagaimana data yang sudah terstruktur akan di organisir kembali bila kita memasukkan data gres atau meng-insert data baru, atau pula menghapus data. Teknik itulah yang diterapkan di metode heap sort. Inti dari pengurutan secara heap yaitu pengerjaannya yang dilakukkan dengan pengurutan ascending dan descending, jadi ada dua kali pengurutan.
Keunggulan algoritma pengurutan heap sort terletak pada kompleksitas waktu asimptotiknya yang sangat baik.
Meskipun lebih lambat dari algoritma pengurutan data yang lain, algoritma heap sort mempunyai kelebihan saat menangani data dalam skala yang besar/massive. Karena algoritma ini mempunyai kelebihan tidak memakai banyak tabel, tetapi hanya satu tabel yang digunakan untuk menyimpan hasil dari pengurutan tersebut.
B. Saran
Dalam pengurutan data yang mempunyai skala tidak terlalu besar sebaiknya tidak memakai metode ini karna membutuhkan banyak ruang memori, namun bila jumlah data tersebut besar atau dalam skala besar dengan metode pengurutan heap sort ini lebih dianjurkan.
DAFTAR PUSTAKA
Nur Wahyudi, Wahyudi. Januari 2009, "Algoritma Sederhana dalam Memahami Proses Pengurutan Data". Jurnal Teknologi Informasi DINAMIK. Volume XIV, No.1.
Fathoni, Saniman dan Muhaammad. Januari 2010. "Konsep Sorting Dalam Pemrograman". Jurnal SAINTIKOM. Volume VIII, No.1.
CONTOH ALGORITMA HEAP SORT PADA BAHASA C