# Tugas Pendahuluan - Heap Sort

### Pembuat Soal: GI

Nama  : Alwahib Raffi Raihan
NPM   : 2406397630

## Teori

### Batas Bawah Teoretis

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

Maksudnya adalah algoritma hanya boleh menentukan urutan dengan embbandigkan dua elemen dalam bentuk kondisi seperti (`A[i] > A[j]`) dimana setiap perbandingan dianggap sebagai node dalam decision tree dan tidak dapat lebih cepat dari n log n dalam kasus terburuk maupun rata-rata.
Batas bawah diperoleh dari analisis decision tree dimana sorting dengan perbandingan dimodelkan seperti biner decision tree, setiap simpul dalam pohon adalah satu perbandingan, pengurutan n elemn ada n! kemungkinan urutan dan decision tree harus memiliki n! daun untuk semua kemungkinan dengan tingginya minimal `log₂(n!)` yang diturunkan menjadi `Ω(n log n)`.

### Referensi
- [1] GeeksforGeeks, "Time Complexities of all Sorting Algorithms," GeeksforGeeks, 2024. [Online]. Available: https://www.geeksforgeeks.org/dsa/time-complexities-of-all-sorting-algorithms/. [Diakses: 29-Sep-2025]
- [2] GeeksforGeeks, "Can run time complexity of a comparison based sorting algorithm be less than nlogn?," GeeksforGeeks, 2024. [Online]. Available: https://www.geeksforgeeks.org/dsa/can-run-time-complexity-of-a-comparison-based-sorting-algorithm-be-less-than-n-logn/. [Diakses: 29-Sep-2025]
- [3] GeeksforGeeks, "lower_bound in C++," GeeksforGeeks, 2024. [Online]. Available: https://www.geeksforgeeks.org/cpp/lower_bound-in-cpp/. [Diakses: 29-Sep-2025]

---

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

Karena algoritmanya menggunakan perbandingan (comparison-based sorting) yang tunduk dengan batas bawah.

Alasannya berupa:
- bergantung dengan perbandingan elemen, semua algoritma bekerja dengan menentukan urutan dari hasil perbandingan antar elemen
- Decision Tree, dimana process sorting di desain dengan decision tree dan tinggi minimal pohonnya `Ω(n log n)` (turunan dari perbandingan minimum yang dibutuhkan untuk membedakan semua kemungkinan urutan)
- Worst case yang tidak bisa dihindari dimana Quick sort bisa mencapai `O(n²)` lalu Merge Sort dan Heap Sort stabil karena terjamin O(n log n) di kasus terburuk, tetapi tidak dapat lebih cepat.

### Referensi
- [1] GeeksforGeeks, "Lower Bound on Comparison based Sorting Algorithms," GeeksforGeeks, 2024. [Online]. Available: https://www.geeksforgeeks.org/dsa/lower-bound-on-comparison-based-sorting-algorithms/. [Diakses: 29-Sep-2025]
- [2] W3Schools, "Radix Sort Algorithm," W3Schools, 2024. [Online]. Available: https://www.w3schools.com/dsa/dsa_algo_radixsort.php. [Diakses: 29-Sep-2025]

---

### Sorting Non-Comparison

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

Radix Sort tidak bekerja dengan perbandingan (non-comparison sorting) tetapi bekerja dengan cara memproses elemen dari digit digitnya. Dilaksanakan dari digit terendah (Least Significant Sigit) ke tertinggi (Most Significant Digit) dan sebaliknya. Pada setiap langkah menggunakan algortima stable sort untuk mengurutkan elemen sesuai digit yang diproses.

Contohnya:
`Array [10,20,30,40,50]`
urutkan berdasarkan digit satuan (hasil sementara)
urutkan berdasarkan digit puluhan (hasil lebih teratur)
urutkan berdasarkan digit ratusan (hasil akhir)

### Referensi
- [1] GeeksforGeeks, "Radix Sort," GeeksforGeeks. [Online]. Available: https://www.geeksforgeeks.org/radix-sort/. [Diakses: 29-Sep-2025]
- [2] Programiz, "Radix Sort Algorithm," Programiz. [Online]. Available: https://www.programiz.com/dsa/radix-sort. [Diakses: 29-Sep-2025]

---

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

Karena Batas bawah `Ω(n log n)` berlaku pada sorting dengan perbandingan dan Radix Sort tidak menggunakan perbandingan tetapi dengan struktur digit.
Kompleksitas Radix Sort:
`O(d⋅(n+k))`
d = jumlah digit yang diproses
n = jumlah elemen
k = rentang nilai tiap digit

Dengan d dianggap konstan (misalnya NIM) dan k relatif lebih kecil dari n maka kommpleksitasnya dapat mencapai `O(n)` dalam kondisi tertentu

### Referensi
- [1] GeeksforGeeks, "Radix Sort," GeeksforGeeks. [Online]. Available: https://www.geeksforgeeks.org/radix-sort/. [Diakses: 29-Sep-2025]
- [2] Programiz, "Radix Sort Algorithm," Programiz. [Online]. Available: https://www.programiz.com/dsa/radix-sort. [Diakses: 29-Sep-2025]

---

### Functor vs Lambda

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

**Functor (Function Object)**, class atau struct yang mengoverload operator `()`. Object hasil instansiasi functor dipanggil seperti fungsi. Functor dapat mengimpan state internal dan perilaku dipengaruhi nilai yang di dalam objek. contoh kodenya:

#include <iostream>
using namespace std;

struct MultiplyBy {
    int factor;
    MultiplyBy(int f) : factor(f) {}
    int operator()(int x) const {
        return x * factor;
    }
};

int main() {
    MultiplyBy times3(3);   // buat functor dengan factor = 3
    cout << times3(5);      // Output: 15
    return 0;
}

**Lambda Expression** fungsi anonim yang dapai ditulis secara lanngsung (inline), dapat menangkap variabel dari scope di luar lambda dengan copy `[=]` atau reference `[&]` dan lebih ringkas dari functor, dengan syntax `[] (parameter) { body }`

#include <iostream>
using namespace std;

int main() {
    auto times3 = [](int x) { return x * 3; };  // lambda expression
    cout << times3(5);  // Output: 15
    return 0;
}

### Referensi
- [1] GeeksforGeeks, “Functors in C++,” GeeksforGeeks. [Online]. Available: https://www.geeksforgeeks.org/functors-in-cpp/. [Diakses: 29-Sep-2025]
- [2] GeeksforGeeks, “Lambda Expressions in C++,” GeeksforGeeks. [Online]. Available: https://www.geeksforgeeks.org/lambda-expression-in-c/. [Diakses: 29-Sep-2025]

---

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

Keuntungan Functor:
- Menyimpan state internal dimana comparator bisa bergantung pada parameter yang disimpan dalam functor.
- Fleksibel sehingga cocok dengan case kompleks seperti comparator yang banyak logika.
- Kompatibel dengan STL lampau tepatnya sebelum C++11 dimana pembuatan comparator custom enggunakan functor.
Keuntungan Lambda:
- Ringkas dimana comparator dapat ditulis langsung di lokasi tanpa definisi class tambahan.
- Mudah dibaca karena lebih ringkas dan cukup untuk comparator sederhana.
- Efisien dimana compiler dapat melakukan inlining dan optimasi lebih mudah.
- Sama sama fleksibel dalam penggunaan STL

### Referensi

- [1] GeeksforGeeks, “Comparator Class in C++ with Examples,” GeeksforGeeks. [Online]. Available: https://www.geeksforgeeks.org/comparator-class-in-c-with-examples/. [Diakses: 29-Sep-2025]
- [2] cppreference.com, “std::sort,” cppreference. [Online]. Available: https://en.cppreference.com/w/cpp/algorithm/sort. [Diakses: 29-Sep-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> // Untuk std::swap
#include <string>

// 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) {
    // Tulis kode kalian di sini
}

// TODO 2: Implementasikan fungsi makeheap.
// Fungsi ini mengubah seluruh array menjadi Max-Heap menggunakan pendekatan Bottom-Up.
void makeheap(std::vector<int>& H) {
    // Tulis kode kalian di sini
}

// TODO 3: Implementasikan fungsi heapsort.
// Fungsi ini menggabungkan makeheap dan fase sorting untuk mengurutkan array secara in-place.
void heapsort(std::vector<int>& H) {
    // Tulis kode kalian di sini
}

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;
}

**Kode:**

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

// 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 largest = start_index;
    int left = 2 * start_index + 1;
    int right = 2 * start_index + 2;

    // Cari anak kiri dan kanan, pilih yang terbesar
    if (left < heap_size && H[left] > H[largest]) {
        largest = left;
    }
    if (right < heap_size && H[right] > H[largest]) {
        largest = right;
    }

    // Jika root bukan yang terbesar, swap dan lanjutkan rekursif
    if (largest != start_index) {
        std::swap(H[start_index], H[largest]);
        siftdown(H, largest, heap_size);
    }
}

// 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 = 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 = H.size();
    makeheap(H);

    for (int i = n - 1; i > 0; i--) {
        std::swap(H[0], H[i]);   // pindahkan root (maksimum) ke akhir
        siftdown(H, 0, i);       // perbaiki heap pada elemen tersisa
    }
}

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 (prioritas 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) {
        // Tulis logika perbandingan di sini
        return /* ... */; 
    }
};

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(...)
    
    std::cout << "Urutan pasien di Ruang Gawat Darurat:" << 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()
    }

    return 0;
}

**Kode:**

#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 (prioritas terendah)
};

// TODO 4: Buat sebuah Functor sebagai custom comparator.
struct ComparePatients {
    bool operator()(const Patient& a, const Patient& b) {
        // pasien dengan triage_level lebih kecil punya prioritas lebih tinggi
        return a.triage_level > b.triage_level;
    }
};

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.
    er_queue.push({"Alice", 3});
    er_queue.push({"Bob", 1});
    er_queue.push({"Charlie", 2});
    er_queue.push({"Diana", 5});
    er_queue.push({"Eve", 4});

    std::cout << "Urutan pasien di Ruang Gawat Darurat:" << std::endl;
    while (!er_queue.empty()) {
        // TODO 6: Ambil pasien dengan prioritas tertinggi
        Patient p = er_queue.top();
        std::cout << p.name << " (Level " << p.triage_level << ")" << std::endl;
        er_queue.pop();
    }

    return 0;
}