---
title: Tugas Pendahuluan - Heap Sort
---

# Tugas Pendahuluan - Heap Sort

### Pembuat Soal: GI

Nama  : Danish Al Fayyadh Sunarta
NPM   : 2406416951

## Teori

### Batas Bawah Teoretis

#### 1. Jelaskan apa yang dimaksud dengan batas bawah teoretis Ω(n log n) untuk algoritma sorting berbasis perbandingan.

**Jawaban:**

Batas bawah teoretis Ω(n log n) diperoleh dengan memodelkan setiap algoritma perbandingan sebagai decision tree biner. setiap perbandingan antara dua elemen merupakan cabang (ya/tidak). Karena ada n! permutasi input yang berbeda dan setiap daun harus mewakili sebuah urutan hasil, decision tree harus memiliki setidaknya n! daun. Tinggi pohon (jumlah perbandingan dalam kasus terburuk) h memenuhi 2^h >= n!, sehingga h >= log(n!). dengan menggunakan Stirling Approximation, diperoleh log(n!) = Θ(n log n). oleh karena itu, setiap algoritma berbasis perbandingan butuh Ω(n log n) perbandingan dalam kasus terburuk.

**Referensi:**
- T. Roughgarden, "CS161 Design and Analysis of Algorithms, Lecture 7: Lower Bounds for Sorting and Selection," Stanfor University, 2016. [Online]. Available: https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture7.pdf
[Accessed: 28 Sept, 2025].
- enjoy algorithms, "What is the Lower Bound of Comparison Sort?," enjoyalgorithms.com, 2023. [Online]. Available: https://www.enjoyalgorithms.com/blog/lower-bound-of-comparison-sorting [Accessed: 28 Sept, 2025].

---

#### 2. Mengapa algoritma seperti Merge Sort, Quick Sort, dan Heap Sort tidak bisa lebih cepat dari batas ini pada kasus terburuk?

**Jawaban:**

Merge Sort, Quick Sort, dan Heap Sort merupakan algoritma berbasis perbandingan comparison based yang hanya mengubah urutan melalui perbandingan antar elemen. Karena batas bawah Ω(n log n) berlaku untuk semua algoritma perbandingan, maka tidak mungkin sebuah algoritma perbandingan umum untuk lebih cepat dari Ω(n log n) pada semua input.

**Referensi:**
- T. Roughgarden, "CS161 Design and Analysis of Algorithms, Lecture 7: Lower Bounds for Sorting and Selection," Stanfor University, 2016. [Online]. Available: https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture7.pdf
[Accessed: 28 Sept, 2025].
- enjoy algorithms, "What is the Lower Bound of Comparison Sort?," enjoyalgorithms.com, 2023. [Online]. Available: https://www.enjoyalgorithms.com/blog/lower-bound-of-comparison-sorting [Accessed: 28 Sept, 2025].

---

### Sorting Non-Comparison

#### 3. Jelaskan secara singkat konsep di balik Radix Sort.

**Jawaban:**

berbeda dari kebanyakan algoritma sorting yang merupakan comparison based, Radix sort merupakan algoritma distribution based yang mengurutkan keys dengan memproses setiap digitnya. Biasanya menggunakan stable subroutine seperti Counting Sort untuk mengurutkan elemen berdasarkan satu digit pada setiap pass.

**Referensi:**
- Geeksforgeeks, “Radix Sort,” geeksforgeeks.org, 24 Aug, 2025. [Online]. Available:https://www.geeksforgeeks.org/dsa/radix-sort/ [Accessed: 28 Sept, 2025].
- W3schools, “DSA Radix Sort,” w3schools.com, 2025. [Online]. Available:https://www.w3schools.com/dsa/dsa_algo_radixsort.php

---

#### 4. Mengapa Radix Sort dapat "melanggar" batas bawah Ω(n log n) dan mencapai kompleksitas linear O(n) pada kondisi tertentu?

**Jawaban:**

Batas Ω(n log n) hanya berlaku pada algoritma berbasis perbandingan. Radix Sort tidak berbasis pada perbandingan, melainkan memanfaatkan operasi indexing/bucketing berdasarkan digit. Jika panjang kunci w adalah konstan, maka kompleksitasnya menjadi O(w.n)=O(n).

**Referensi:**
- Geeksforgeeks, “Radix Sort,” geeksforgeeks.org, 24 Aug, 2025. [Online]. Available:https://www.geeksforgeeks.org/dsa/radix-sort/ [Accessed: 28 Sept, 2025].
- W3schools, “DSA Radix Sort,” w3schools.com, 2025. [Online]. Available:https://www.w3schools.com/dsa/dsa_algo_radixsort.php

---

### Functor vs Lambda

#### 5. Dalam C++, kita bisa membuat objek yang perilakunya seperti fungsi. Jelaskan apa itu Functor (Function Object) dan Lambda Expression.

**Jawaban:**

- Functor (Function Object) merupakan sebuah objek class/struct yang dapat dipanggil layaknya function. functor meng-override fungction call operator() sehingga instance-nya dapat dipanggil layaknya function.

- Lambda Expression merupakan expression (sintaks singkat) untuk membuat objek yang dapat dipanggil secara anonim (functors).

**Referensi:**
- Programiz, “C++ Functors,” programiz.com, 2025. [Online]. Available:https://www.programiz.com/cpp-programming/functors [Accessed: 28 Sept, 2025].
- Programiz, “C++ Lambda,” programiz.com, 2025. [Online]. Available:https://www.programiz.com/cpp-programming/lambda-expression [Accessed: 28 Sept, 2025].

---

#### 6. Apa keuntungan menggunakan keduanya, terutama sebagai custom comparator untuk struktur data STL?

**Jawaban:**

- Memberikan fleksibilitas tinggi dalam menentukan aturan custom comparator untuk struktur data STL sehingga urutan elemen dapat disesuaikan dengan kebutuhan.
- Custom comparator yang sudah dibuat dapat digunakan ulang

**Referensi:**
- GeeksforGeeks — Custom Comparator in C++. https://www.geeksforgeeks.org/cpp/comparator-in-cpp/
- Programiz, “C++ Functors,” programiz.com, 2025. [Online]. Available:https://www.programiz.com/cpp-programming/functors [Accessed: 28 Sept, 2025].
- Programiz, “C++ Lambda,” programiz.com, 2025. [Online]. Available:https://www.programiz.com/cpp-programming/lambda-expression [Accessed: 28 Sept, 2025].

---

## Pemrograman

Di bagian ini, kalian akan mengimplementasikan TIGA komponen utama yang akan digunakan kembali pada Case Study.

---

#### 7. Implementasi Manual Algoritma Heap Sort (40 Poin)

Lengkapi kerangka kode di bawah ini untuk membuat algoritma Heap Sort yang fungsional dari awal.

#include <iostream>
#include <vector>
#include <algorithm> // std::swap
#include <string>

using namespace std;

// Fungsi utilitas untuk mencetak vector
void printVector(const std::string& label, const std::vector<int>& vec);

/// TODO 1: Implementasikan fungsi siftdown.
// Fungsi ini harus memperbaiki properti Max-Heap dari sebuah subtree.
void siftdown(std::vector<int>& H, int start_index, int heap_size) {
    int root = start_index;
    bool swapped;

    do {
        swapped = false;
        int left = 2 * root + 1;
        if (left >= heap_size) break;

        int right = left + 1;
        int swap_index = root;

        if (H[swap_index] < H[left]) swap_index = left;
        if (right < heap_size && H[swap_index] < H[right]) swap_index = right;

        if (swap_index != root) {
            swap(H[root], H[swap_index]);
            root = swap_index;
            swapped = true;
        }

    } while (swapped);
}

// TODO 2: Implementasikan fungsi makeheap.
// Fungsi ini mengubah seluruh array menjadi Max-Heap menggunakan pendekatan Bottom-Up.
void makeheap(std::vector<int>& H) {
    int n = static_cast<int>(H.size());
    for (int i = (n / 2) - 1; i >= 0; --i) {
        siftdown(H, i, n);
    }
}

// TODO 3: Implementasikan fungsi heapsort.
// Fungsi ini menggabungkan makeheap dan fase sorting untuk mengurutkan array secara in-place.
void heapsort(std::vector<int>& H) {
    int n = static_cast<int>(H.size());
    if (n <= 1) return;

    makeheap(H);

    for (int heap_size = n; heap_size > 1; --heap_size) {
        swap(H[0], H[heap_size - 1]); 
        siftdown(H, 0, heap_size - 1);    
    }
}

int main() {
    std::vector<int> data = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
    printVector("Data awal:", data);
    heapsort(data);
    printVector("Data terurut:", data);
    return 0;
}

// Implementasi printVector
void printVector(const std::string& label, const std::vector<int>& vec) {
    std::cout << label << "\t";
    for (int val : vec) { std::cout << val << " "; }
    std::cout << std::endl;
}

---

#### 8. Implementasi Priority Queue dengan Custom Comparator (30 Poin)

Lengkapi kerangka kode di bawah ini untuk mengelola sebuah priority_queue dari objek kustom menggunakan Functor.

#include <iostream>
#include <vector>
#include <queue>
#include <string>

// Struktur data kustom
struct Patient {
    std::string name;
    int triage_level; // Level 1 (prioritas tertinggi) ... Level 5 (terendah)
};

// TODO 4: Buat sebuah Functor sebagai custom comparator.
// Functor ini akan digunakan oleh std::priority_queue untuk mengurutkan Patient.
// Ingat, std::priority_queue adalah Max-Heap secara default. Untuk membuatnya
// berperilaku seperti Min-Heap (mengeluarkan prioritas terkecil, yaitu level 1),
// operator() harus mengembalikan 'true' jika prioritas 'a' LEBIH RENDAH dari 'b'.
struct ComparePatients {
    bool operator()(const Patient& a, const Patient& b) const {
        // Tulis logika perbandingan di sini
        if(a.triage_level > b.triage_level){
            return true;
        } else{
            return false;
        }
    }
};

int main() {
    // Membuat priority queue menggunakan Functor yang kalian buat
    std::priority_queue<Patient, std::vector<Patient>, ComparePatients> er_queue;

    // TODO 5: Tambahkan beberapa pasien ke dalam queue.
    // Gunakan er_queue.push(...)
    er_queue.push(Patient{"Alfa", 3});
    er_queue.push(Patient{"Beta", 1});
    er_queue.push(Patient{"Cahyo", 2});
    er_queue.push(Patient{"Delta", 5});
    er_queue.push(Patient{"Epsilon", 4});

    std::cout << "Urutan pasien di Ruang Gawat Darurat (dari prioritas tertinggi):" << std::endl;
    while (!er_queue.empty()) {
        // TODO 6: Ambil pasien dengan prioritas tertinggi, cetak namanya, dan hapus dari queue.
        // Gunakan er_queue.top() dan er_queue.pop()
        Patient p = er_queue.top();
        cout << "Nama: " << p.name << " | level: " << p.triage_level << endl;
        er_queue.pop();
    }

    return 0;
}