# Tugas Pendahuluan - Heap Sort

### Pembuat Soal: GI

Nama  : Eugenia Huwaida Imtinan
NPM   : 2406421384

## Teori

### Batas Bawah Teoretis

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

Setiap algoritma sorting yang hanya bekerja dengan cara membandingkan elemen (contohnya quicksort, mergesort, heapsort, insertion sort, dll) pasti membutuhkan paling sedikit sebesar n log n langkah perbandingan dalam kasus terburuk. karena, untuk mengurutkan n elemen ada n! susunan (permutasi) yang mungkin. Supaya algoritma bisa selalu membedakan semua kemungkinan itu, ia harus melakukan paling tidak sebanyak log(n!) perbandingan.

### Referensi

- [1]Kiran Chhablani, “O(n log n) — The Secret Behind Efficient Sorting Algorithms 🔄✨,” Medium, Feb. 23, 2025. https://medium.com/@kiran_c/o-n-log-n-the-secret-behind-efficient-sorting-algorithms-2e9d33ea4161 (accessed Sep. 28, 2025).
- [2]GeeksforGeeks, “Lower bound for comparison based sorting algorithms,” GeeksforGeeks, Mar. 02, 2011. https://www.geeksforgeeks.org/dsa/lower-bound-on-comparison-based-sorting-algorithms/ (accessed Sep. 28, 2025).

---

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

Kalau kita pakai algoritma sorting yang hanya mengandalkan perbandingan antar elemen (seperti mergesort, quicksort, heapsort, insertion sort, dll), maka kita bisa membayangkan prosesnya sebagai sebuah pohon keputusan (decision tree)

Berikut merupakan turunan rumus O(n log n) yang membuktikan mengapa setidaknya membutuhkan n log n langkah perbandingan dalam worst case:

Pohon biner dengan tinggi h maksimal hanya bisa punya 2^h daun. Jadi, untuk menutupi semua n!, kemungkinan input, berlaku:

Kalau dalam kasus terburuk:
Artinya kedalaman pohon (banyaknya perbandingan dalam kasus terburuk) minimal sebesar log(n!).

Dengan rumus Stirling hasilnya menjadi:
dan disederhanakan menjadi:

Maka, secara umum tidak ada yang lebih cepat dari O(n log n)

### Referensi

- [3]GeeksforGeeks, “Lower bound for comparison based sorting algorithms,” GeeksforGeeks, Mar. 02, 2011. https://www.geeksforgeeks.org/dsa/lower-bound-on-comparison-based-sorting-algorithms/ (accessed Sep. 28, 2025).
- [4]Kiran Chhablani, “O(n log n) — The Secret Behind Efficient Sorting Algorithms 🔄✨,” Medium, Feb. 23, 2025. https://medium.com/@kiran_c/o-n-log-n-the-secret-behind-efficient-sorting-algorithms-2e9d33ea4161 (accessed Sep. 28, 2025).

---

### Sorting Non-Comparison

#### 3. Jelaskan secara singkat konsep di balik Radix Sort.
Radix Sort mengurutkan berdasarkan digit per digit (mis. satuan → puluhan → ratusan) menggunakan stable sort (biasanya Counting Sort) pada setiap digit. Karena tiap langkah hanya memindahkan elemen menurut digit tertentu dan mempertahankan urutan relatif dari digit sama, setelah semua digit diproses, array akan terurut secara keseluruhan.

**Contoh:**
array: `[170, 45, 75, 90, 802, 24, 2, 66]`

Pass 1:
Dilihat digit satuannya saja, lalu diurutkan. Maka masing-masing digit satuannya yaitu:
`0, 5, 5, 0, 2, 4, 2, 6`
Setelah diurutkan menjadi:
`0, 0, 2, 2, 4, 5, 5, 6` -> `170, 90, 802, 2, 24, 45, 75, 66`

Pass 2:
Dilihat digit puluhannya saja, lalu diurutkan. Maka masing-masing digit satuannya yaitu:
`7, 9, 0, 0, 2, 4, 7, 6`
Setelah diurutkan menjadi:
`0, 0, 2, 4, 6, 7, 7, 9` -> `802, 2, 24, 45, 66, 170, 75, 90`

Pass 3:
Dilihat digit ratusannya saja, lalu diurutkan. Maka masing-masing digit satuannya yaitu:
`8, 0, 0, 0, 0, 1, 0, 0`
Setelah diurutkan menjadi:
`0, 0, 0, 0, 0, 0, 1, 8` -> `2, 24, 45, 66, 75, 90, 170, 802`

### Referensi

- [5]GeeksforGeeks, “Radix Sort,” GeeksforGeeks, Sep. 02, 2013. https://www.geeksforgeeks.org/dsa/radix-sort (accessed Sep. 28, 2025).
- [6]GeeksforGeeks, “C++ Program For Radix Sort,” GeeksforGeeks, Oct. 25, 2023. https://www.geeksforgeeks.org/cpp/cpp-program-for-radix-sort/ (accessed Sep. 28, 2025).
- [7]V. Kumar, “Radix Sort in C++ - CodeSpeedy,” CodeSpeedy, Jun. 19, 2019. https://www.codespeedy.com/radix-sort-in-cpp/ (accessed Sep. 28, 2025).

---

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

Batas bawah Ω(𝑛 log 𝑛) hanya berlaku untuk algoritma sorting berbasis perbandingan (comparison-based sorting). Artinya, setiap algoritma yang menentukan urutan dengan cara membandingkan elemen satu per satu (seperti Merge Sort, Quick Sort, Heap Sort) tidak bisa lebih cepat dari
nlogn pada kasus umum.

Radix Sort berbeda karena merupakan non-comparison sort: ia tidak menyortir dengan membandingkan elemen secara langsung, tetapi dengan memproses digit demi digit menggunakan algoritma seperti Counting Sort. Karena itu, ia tidak mengikuti aturan pada batas bawah Ω(nlogn) yang hanya berlaku untuk model berbasis perbandingan.

Pada kondisi tertentu, misalnya ketika jumlah digit (d) relatif kecil dan basis bilangan (radix, k) terbatas, kompleksitas Radix Sort menjadi O(n), lebih cepat daripada algoritma comparison-based terbaik.

### Referensi

- [8]“Comparison Based Sorting Lower Bound Proof,” Byteplus.com, 2025. https://www.byteplus.com/en/topic/501153?title=understanding-comparison-based-sorting-lower-bound-proof (accessed Sep. 28, 2025).
- [9]“Investigating Radix Sort,” Probably Dance, Dec. 02, 2016. https://probablydance.com/2016/12/02/investigating-radix-sort/ (accessed Sep. 28, 2025).
- [10]“Radix Sort Revisited,” Codercorner.com, 2025. https://codercorner.com/RadixSortRevisited.htm (accessed Sep. 28, 2025).

---

### Functor vs Lambda

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

### Function Object
function object adalah objek apa pun yang mendefinisikan operator panggilan fungsi (operator()). Dengan demikian, objek tersebut bisa “dipanggil” seperti fungsi biasa. Karena functor adalah objek, ia dapat menyimpan state (data anggota) yang dipakai dalam pemanggilan fungsi. (Misalnya, konstruktornya bisa menginisialisasi data, lalu operator() menggunakan data tersebut).

Contoh pada operasi aritmatika:

#include <iostream>
using namespace std;

// Functor untuk menambahkan angka
struct Add {
    int value;
    Add(int v) : value(v) {}  // constructor
    int operator()(int x) const {
        return x + value; // nambahin value ke x
    }
};

int main() {
    Add add5(5);  // buat functor dengan value = 5
    cout << add5(10) << endl; // 10 + 5 = 15
    cout << add5(20) << endl; // 20 + 5 = 25
}

Contoh penggunaan pada string:

#include <iostream>
using namespace std;

struct Print {
    void operator()(string msg) const {
        cout << msg << endl;
    }
};

int main() {
    Print p;
    p("Hello World from functor!");
}

### Lambda Expression
lambda expressions memungkinkan kita bisa menulis fungsi pendek secara inline, tanpa memberi nama. Ini memudahkan untuk callback atau fungsi kecil yang tidak akan digunakan ulang banyak kali. lambda expression menghasilkan objek closure (tipe anonim) yang memiliki operator() otomatis. Dengan kata lain, lambda adalah functor anonim.

Syntax:

[capture](parameter list) -> return_type {
  // body
};

Contoh penggunaan pada operasi aritmatika:

#include <iostream>
using namespace std;

int main() {
    int add_value = 5;

    // Lambda untuk nambahin angka
    auto add = [add_value](int x) {
        return x + add_value;
    };

    cout << add(10) << endl; // 10 + 5 = 15
    cout << add(20) << endl; // 20 + 5 = 25
}

Contoh penggnaan pada string:

#include <iostream>
using namespace std;

int main() {
    auto print = [](string msg) {
        cout << msg << endl;
    };

    print("Hello World from Lambda!");
}

### Referensi

- [11]“Function objects - cppreference.com,” Cppreference.com, 2025. https://en.cppreference.com/w/cpp/utility/functional.html (accessed Sep. 28, 2025).
- [12]GeeksforGeeks, “Lambda Expression in C++,” GeeksforGeeks, Feb. 10, 2016. https://www.geeksforgeeks.org/cpp/lambda-expression-in-c/ (accessed Sep. 28, 2025).
- [13]GeeksforGeeks, “When to Use Lambda Expressions Instead of Functions in C++?,” GeeksforGeeks, Mar. 17, 2024. https://www.geeksforgeeks.org/cpp/when-to-use-lambda-expressions-instead-of-functions-in-cpp/
‌

---

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

### Keuntungan Functor
1. Menyimpan state: Functor bisa punya data anggota (misal parameter perbandingan) yang dipakai tiap kali dipanggil.
1. Contoh: sorting berdasarkan batas tertentu, atau urutan khusus yang berubah-ubah.
1. Reusable: Karena functor adalah class/struct, bisa dipakai berulang di banyak tempat tanpa menulis ulang kode.
1. Integrasi dengan STL: Banyak algoritma STL (sort, priority_queue, set, map) menerima objek functor sebagai comparator.

Contoh:

struct Compare {
    bool operator()(int a, int b) { return a > b; }  // descending
};

vector<int> v = {3,1,4};
sort(v.begin(), v.end(), Compare()); // pakai functor sebagai custom comparator

### Keuntungan Lambda Expression
1. Ringkas / inline: Tidak perlu bikin class baru, definisi fungsi bisa ditulis langsung di tempat pemakaian.
1. Capture variabel luar: Bisa menggunakan variabel lokal di scope luar tanpa deklarasi global atau parameter tambahan.
1. Sekali pakai / cepat dicoba: Ideal untuk comparator yang spesifik sekali atau tidak dipakai lagi.

Contoh:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3,1,4,2};
    int offset = 1;

    sort(v.begin(), v.end(), [offset](int a, int b) {
        return (a + offset) > (b + offset);  // descending dengan offset
    });

    for(int x : v) cout << x << " "; 
    // outputnya: 4 3 2 1
}

### Referensi

- [14]“Function objects - cppreference.com,” Cppreference.com, 2025. https://en.cppreference.com/w/cpp/utility/functional.html (accessed Sep. 28, 2025).
- [15]GeeksforGeeks, “Lambda Expression in C++,” GeeksforGeeks, Feb. 10, 2016. https://www.geeksforgeeks.org/cpp/lambda-expression-in-c/ (accessed Sep. 28, 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) {
    std::cout << label << "\t";
    for (int val : vec) { std::cout << val << " "; }
    std::cout << std::endl;
}

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

        if (left < heap_size && H[left] > H[largest]) {
            largest = left;
        }

        if (right < heap_size && H[right] > H[largest]) {
            largest = right;
        }

        if (largest == root) {
            break;
        }

        std::swap(H[root], H[largest]);
        root = largest;
    } while (root * 2 + 1 < 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]);
        siftdown(H, 0, i);
    }
}

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

---

#### 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 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.
    // Gunakan er_queue.push(...)
    er_queue.push({"Eugenia", 3});
    er_queue.push({"Huwaida", 1});
    er_queue.push({"Imtinan", 4});
    er_queue.push({"Famima", 2});
    er_queue.push({"Jembong", 5});

    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()
        Patient next = er_queue.top();
        std::cout << "Pasien: " << next.name << ", Level: " << next.triage_level << std::endl;
        er_queue.pop();
    }

    return 0;
}