Anak Males – Artikel ini akan memberikan cara untuk membuat sebuah program dengan bahasa C++ yang mengaplikasikan pengurutan Heap sort.
Pengurutan data merupakan salah satu proses yang penting dalam dunia pemrograman. Salah satu algoritma pengurutan yang efisien dan banyak digunakan adalah Heap Sort.
Algoritma ini menggunakan struktur data heap untuk mengurutkan elemen dari suatu array.
Dalam artikel ini, kita akan mengulas bagaimana algoritma Heap Sort bekerja, kelebihan dan kekurangan dari algoritma ini, serta implementasi Heap Sort dengan menggunakan bahasa pemrograman C++.
Apa yang akan Anda dapatkan setelah membaca artikel ini adalah pemahaman yang lebih baik tentang cara kerja algoritma Heap Sort, serta bagaimana mengaplikasikannya dalam pemrograman.
Baca : Latihan C++ #23 : Program C++ Pembalik Angka Rekursif
Algoritma Heap Sort
Heap sort adalah algoritma pengurutan yang menggunakan struktur data heap untuk mengurutkan elemen dari suatu array.
Proses pengurutan dengan heap sort dilakukan dengan membangun heap dari elemen array, kemudian mengambil elemen teratas (atau elemen dengan nilai terbesar atau terkecil) secara berulang-ulang hingga semua elemen terurut.
Algoritma ini mengkombinasikan konsep dari dua jenis heap, yaitu max heap dan min heap, untuk mengurutkan elemen dari array.
Heap sort efisien dalam hal waktu eksekusi dan memiliki kompleksitas waktu O(n log n), membuatnya menjadi salah satu pilihan utama dalam pengurutan data.
Baca : Latihan C++ #27 : Program C++ Mencari Nilai Rata Rata
Kelebihan Heap Sort
Beberapa kelebihan dari algoritma heap sort adalah:
- Memiliki kompleksitas waktu yang baik, O(n log n)
- Memerlukan sedikit memori ekstra untuk menyimpan heap.
- Dapat digunakan dalam situasi ketika memori yang tersedia terbatas.
- Dapat digunakan untuk mengurutkan elemen dari data yang sangat besar.
- Dapat digunakan untuk menyelesaikan beberapa masalah yang terkait dengan pengurutan, seperti mencari elemen terbesar / terkecil k-th dari suatu array.
Kekurangan Heap Sort
Beberapa kekurangan dari algoritma heap sort adalah:
- Memerlukan banyak memori untuk menyimpan heap.
- Memerlukan banyak operasi pergeseran elemen saat membangun heap dan mengekstrak elemen teratas.
- Tidak stabil, artinya tidak mempertahankan urutan elemen yang memiliki nilai yang sama.
- Lebih lambat dibandingkan dengan algoritma pengurutan lain seperti quicksort atau mergesort dalam beberapa kasus khusus.
Meskipun memiliki beberapa kekurangan, heap sort tetap menjadi pilihan yang baik untuk digunakan dalam beberapa situasi tertentu, terutama ketika memerlukan waktu eksekusi yang cepat dan memori yang terbatas.
Baca : Latihan C++ #43: Membuat Selection Sort
Program C++ Membuat Heap Sort
Berikut ini adalah contoh program heap sort menggunakan bahasa C++ dengan inputan dari pengguna:
#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i)
{
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i)
{
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i=n-1; i>=0; i--)
{
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
int main()
{
int n;
cout << "Masukkan jumlah elemen: ";
cin >> n;
int arr[n];
cout << "Masukkan elemen: ";
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
heapSort(arr, n);
cout << "Array setelah diurutkan: ";
for (int i=0; i<n; ++i)
cout << arr[i] << " ";
return 0;
}
Berikut adalah penjelasan dari setiap bagian dari program heap sort di C++ :
#include <iostream>
using namespace std;
Memasukkan library iostream yang digunakan untuk input/output dan mendeklarasikan namespace std yang digunakan untuk menggunakan fungsi-fungsi dari iostream.
void heapify(int arr[], int n, int i)
{
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i)
{
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
Fungsi heapify digunakan untuk membuat suatu array menjadi heap. Fungsi ini menerima 3 parameter yaitu array, ukuran array, dan indeks.
Dalam fungsi ini, digunakan variabel lokal largest untuk menyimpan indeks dari elemen terbesar dari array, l untuk menyimpan indeks dari left child dari elemen saat ini, dan r untuk menyimpan indeks dari right child dari elemen saat ini.
Kemudian, dibandingkan indeks left child dan right child dengan indeks saat ini. Jika salah satu dari left atau right child lebih besar dari indeks saat ini, maka largest diisi dengan indeks tersebut.
Jika largest tidak sama dengan i, maka dilakukan swap antara i dan largest, dan kemudian memanggil heapify lagi dengan largest sebagai indeks baru.
Baca : Latihan C++ #42: Membuat Insertion Sort
void heapSort(int arr[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i=n-1; i>=0; i--)
{
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
Fungsi heapSort digunakan untuk mengurutkan elemen-elemen dari array menggunakan algoritma heap sort. Fungsi ini menerima 2 parameter yaitu array dan ukuran array.
Dalam fungsi ini, dilakukan loop untuk mengeksekusi heapify dari n/2-1 sampai 0. Kemudian, dilakukan loop lagi untuk mengekstrak elemen teratas dari heap dengan menukar elemen pertama dengan elemen terakhir, dan mengurangi ukuran heap. Setelah itu,memanggil heapify dari elemen pertama.
int main()
{
int n;
cout << "Masukkan jumlah elemen: ";
cin >> n;
int arr[n];
cout << "Masukkan elemen: ";
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
heapSort(arr, n);
cout << "Array setelah diurutkan: ";
for (int i=0; i<n; ++i)
cout << arr[i] << " ";
return 0;
}
Fungsi utama dari program. Dalam fungsi ini, meminta input jumlah elemen dari pengguna dan menyimpan dalam variabel n.
Kemudian, meminta input elemen-elemen dari pengguna dan menyimpannya dalam array. Setelah itu, memanggil fungsi heapSort dengan parameter array dan ukuran array yang diinputkan.
Kemudian, menampilkan hasil akhir dari pengurutan dengan loop dan mengembalikan nilai 0.
Program ini akan menerima input dari pengguna, yaitu jumlah elemen yang akan diurutkan dan elemen-elemen tersebut.
Kemudian program akan menjalankan algoritma heap sort untuk mengurutkan elemen-elemen tersebut dan menampilkan hasil akhir dari pengurutan.
Fungsi heapify digunakan untuk membuat array menjadi heap. Fungsi heapSort digunakan untuk mengurutkan array menggunakan algoritma heap sort, dengan memanggil fungsi heapify dan melakukan ekstraksi elemen teratas dari heap.
Program ini menggunakan cara bottom-up untuk membuat heap dari array yang diinputkan, kemudian mengekstrak elemen teratas dari heap secara berulang-ulang hingga seluruh elemen terurut.
Baca : Belajar C++ #13 : Memahami Konsep Sorting Data di C++
Output Program C++ Membuat Heap Sort
Contoh output dari program heap sort di C++ yang menerima inputan dari user akan terlihat seperti ini :
Masukkan jumlah elemen: 5
Masukkan elemen: 5 2 7 1 3
Array setelah diurutkan: 1 2 3 5 7
Dalam contoh ini, pengguna diminta untuk memasukkan jumlah elemen yang akan diurutkan (5), kemudian memasukkan elemen-elemen yang akan diurutkan (5, 2, 7, 1, 3). Setelah program dijalankan, output akan menampilkan array yang telah diurutkan (1, 2, 3, 5, 7) sesuai dengan algoritma heap sort.
Baca : Latihan C++ #41: Membuat Deret Angka
Penutup
Dalam artikel ini, kita telah membahas tentang algoritma heap sort dan implementasinya menggunakan bahasa pemrograman C++.
Kita telah melihat bagaimana algoritma ini bekerja dengan membuat heap dari elemen array dan mengambil elemen teratas secara berulang-ulang hingga semua elemen terurut. Kita juga telah melihat kelebihan dan kekurangan dari algoritma ini.
Heap sort merupakan salah satu algoritma pengurutan yang efisien dan banyak digunakan dalam berbagai situasi. Implementasi dari heap sort ini dapat digunakan untuk berbagai keperluan seperti mencari elemen terbesar atau terkecil dari suatu array, atau digunakan sebagai proses dalam memecahkan masalah yang terkait dengan pengurutan.
Sekian untuk tutorial C++ kali ini, sampai jumpa di tutorial C++ lainnya.