# Tugas Pendahuluan - Modul 2 (Algoritma & Sorting)

Nama : Eugenia Huwaida Imtinan
NPM : 2406421384

## 1. (Tanpa Referensi) Coba jelaskan saja menurut Anda. Mengapa modul ini bernama "Algoritma & Sorting". Bukan sekedar "Sorting" saja. (15 Poin)

Jawaban :
* Sorting hanyalah aplikasi. Sorting memang penting, tapi itu hanyalah salah satu contoh penerapan algoritma.
* Algoritma sebagai fondasi. Sebelum belajar sorting, perlu memahami konsep algoritma: langkah-langkah logis, efisiensi, kompleksitas waktu dan ruang.
* Sorting sering dipakai untuk memperkenalkan analisis algoritma karena banyak variasi (Bubble Sort, Insertion Sort, Quick Sort, Heap Sort). Setiap algoritma punya karakteristik best case, worst case, dan average case yang baik untuk melatih pemahaman.

## 2. Apakah C++ sudah mempunyai method/function untuk sorting? Jika ada tolong buatkan satu program sederhana yang mengurutkan angka `6,9,4,2,0` dari terkecil ke terbesar (20 Poin)

Jawaban :
Ya, untuk sorting di C++, kita dapat menggunakan `<algorithm>`. Sorting dapat digunakan dengan memakai function `sort()`.

#include <iostream>
#include <algorithm>

int main() {
    int arr[] = {6, 9, 4, 2, 0};
    int n = sizeof(arr) / sizeof(arr[0]); // size arraynya

    std::cout << "Sebelum sorting: ";
    for(int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    } 
    std::cout << "\n";

    std::sort(arr, arr + n);
    std::cout << "Setelah sorting: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
}

**Referensi:**
- [1]“W3Schools.com,” W3schools.com, 2024. https://www.w3schools.com/cpp/cpp_ref_algorithm.asp (accessed Sep. 15, 2025)
- [2]“C++ algorithm std::sort,” TutorialKart, Jan. 21, 2025. https://www.tutorialkart.com/cpp/cpp-algorithm-sort/ (accessed Sep. 15, 2025).
‌
## 3. Berkaitan dengan nomor-nomor sebelumnya. Coba jelaskan algoritma yang dipakai oleh sorting dalam library C. Kemudian sebutkan minimal 3 algoritma lain dalam sorting beserta `best use case` dan `worst case` nya (15 Poin)

Jawaban :
Function sort mengimplementasikan 3 standar dalam sorting algorithm yaitu insertion sort, quick sort, dan heap sort.

**a. Insertion Sort**
Insertion sort bekerja dengan cara melihat elemen satu per satu dari kiri ke kanan, lalu menaruh elemen itu di posisi yang tepat di bagian kiri yang sudah rapi. Jadi bagian kiri selalu dalam keadaan terurut, sedangkan elemen baru akan dimasukkan ke tempat yang pas.

**b. Heap Sort**
Heap sort bekerja dengan cara membentuk struktur data bernama heap, di mana elemen terbesar selalu ada di posisi paling atas. Setelah itu elemen terbesar dipindah ke posisi akhir, ukuran heap diperkecil, lalu susunan heap dibetulkan lagi. Proses ini diulang sampai semua elemen berada di urutan yang benar.

**c. Quick Sort**
Quick sort bekerja dengan cara memilih satu nilai acuan yang disebut pivot, kemudian memisahkan data menjadi dua bagian: yang lebih kecil dari pivot di kiri dan yang lebih besar di kanan. Setelah itu, proses yang sama dilakukan lagi pada bagian kiri dan kanan sampai semuanya rapi.

**Referensi:**
- [3]GeeksforGeeks, “Insertion Sort Algorithm,” GeeksforGeeks, Mar. 07, 2013. https://www.geeksforgeeks.org/dsa/insertion-sort-algorithm/
- [4]GeeksforGeeks, “C++ Program for Quick Sort,” GeeksforGeeks, Jan. 07, 2014. https://www.geeksforgeeks.org/cpp/cpp-program-for-quicksort/
- [5]GeeksforGeeks, “Heap Sort Data Structures and Algorithms Tutorials,” GeeksforGeeks, Mar. 16, 2013. https://www.geeksforgeeks.org/dsa/heap-sort/
‌
## 4. Buat program yang dapat mengcompare kecepatan antara : `Bubble Sort`, `Selection Short`, dan `Insertion Short` di mana Anda wajib mengimplementasikan for loop dan algoritma yang sesuai sendiri tanpa sort dari library standard. Gunakan GDB Online Compiler agar perbedaan kecepatan runtime lebih terlihat. (25 Poin)

#include <iostream>
#include <ctime>

using namespace std;

int main() {
    int arr[] = {6, 9, 4, 2, 0};
    int n = 5;
    const int REPEAT = 1000;
    
    clock_t start = clock();
    for(int r = 0; r < REPEAT; r++) {
        int bubble[n];
        for(int i = 0; i < n; i++) bubble[i] = arr[i];
        
        for(int i = 0; i < n-1; i++) {
            for(int j = 0; j < n-i-1; j++) {
                if(bubble[j] > bubble[j+1]) {
                    int temp = bubble[j];
                    bubble[j] = bubble[j+1];
                    bubble[j+1] = temp;
                }
            }
        }
    }
    double bubbleTime = (double)(clock() - start) * 1000 / CLOCKS_PER_SEC / REPEAT;
    
    start = clock();
    for(int r = 0; r < REPEAT; r++) {
        int select[n];
        for(int i = 0; i < n; i++) select[i] = arr[i];
        
        for(int i = 0; i < n-1; i++) {
            int min = i;
            for(int j = i+1; j < n; j++) {
                if(select[j] < select[min]) min = j;
            }
            int temp = select[i];
            select[i] = select[min];
            select[min] = temp;
        }
    }
    double selTime = (double)(clock() - start) * 1000 / CLOCKS_PER_SEC / REPEAT;
    
    start = clock();
    for(int r = 0; r < REPEAT; r++) {
        int ins[n];
        for(int i = 0; i < n; i++) ins[i] = arr[i];
        
        for(int i = 1; i < n; i++) {
            int key = ins[i];
            int j = i-1;
            while(j >= 0 && ins[j] > key) {
                ins[j+1] = ins[j];
                j--;
            }
            ins[j+1] = key;
        }
    }
    double insTime = (double)(clock() - start) * 1000 / CLOCKS_PER_SEC / REPEAT;
    
    cout.precision(6);
    cout << fixed;
    cout << "Waktu rata-rata per sorting:" << endl;
    cout << "Bubble:    " << bubbleTime << " milidetik" << endl;
    cout << "Selection: " << selTime << " milidetik" << endl;
    cout << "Insertion: " << insTime << " milidetik" << endl;
    
    return 0;
}


**Referensi:**
- [6]“W3Schools.com,” W3schools.com, 2025. https://www.w3schools.com/cpp/ref_ctime_clock.asp
- [7]“C++ ctime() - C++ Standard Library,” www.programiz.com. https://www.programiz.com/cpp-programming/library-function/ctime/ctime

‌

## 5. Coba jelaskan apa itu `std::vector` dan apa yang membedakannya dengan `array` yang kalian sering gunakan di C. Kemudian buat juga contoh program untuk men-showcase perbedaan implementasinya (mulai dari akses index, penambahan, pengurangan, dll.) (25 Poin)

Jawaban:
std::vector adalah container di C++ yang menyimpan elemen secara berurutan dan dapat mengubah ukuran secara dinamis, memungkinkan penambahan atau penghapusan elemen. Berbeda dengan array di C, yang memiliki ukuran tetap dan tidak bisa diubah setelah deklarasi, std::vector dapat mudah mengubah & menghapus dengan fungsi-fungsi seperti push_back() untuk menambah elemen dan size() untuk mengetahui jumlah elemen. Selain itu, std::vector juga menyediakan akses elemen yang lebih aman dengan metode seperti at() yang memeriksa batas, sementara array lebih sederhana namun terbatas pada ukuran tetap dan kurang aman karena tidak ada pemeriksaan batas secara otomatis.

| Aspek | Array | Vector |
| -------- | -------- | -------- |
| Ukuran | Fixed | Dynamic|
| Memory Management| Manual | Otomatis|
| Penambahan Elemen | Tidak bisa | push_back()|
| Penghapusan Elemen | Tidak bisa | pop_back()|

**Contoh code menggunakan vector:**

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

int main() {
    vector<int> arr = {6, 9, 4, 2, 0};

    // isi array awal
    cout << "Isi array awal: ";
    for(int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    // Akses pake index
    cout << "\nakses elemen berdasarkan index:" << endl;
    cout << "arr[0] = " << arr[0] << endl;
    cout << "arr[1] = " << arr[1] << endl;
    cout << "arr[2] = " << arr[2] << endl;

    // Menambah elemen
    cout << "\nmenambah elemen 7 dan 3" << endl;
    arr.push_back(7);
    arr.push_back(3);

    cout << "setelah push_back: ";
    for(int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    cout << "\nngapus elemen terakhir" << endl;
    arr.pop_back();

    // menghapus
    cout << "isi array final: ";
    for(int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

**Contoh code menggunakan array:**

#include <iostream>
using namespace std;

int main() {
    int arr[5] = {6, 9, 4, 2, 0};
    
    // akses index
    cout << "   arr[0] = " << arr[0] << endl;
    cout << "   arr[2] = " << arr[2] << endl;
    cout << "   arr[4] = " << arr[4] << endl;

    // mengubah nilai
    cout << "   Sebelum: arr[1] = " << arr[1] << endl;
    arr[1] = 99;
    cout << "   Sesudah: arr[1] = " << arr[1] << endl;


    return 0;
}