Tugas Mandiri 2: Analisis Kinerja dan Benchmarking Algoritma Sorting Lanjutan

Tugas 3: Analisis Komparasi Kinerja Algoritma Pengurutan Lanjutan (Advanced Sorting)

Kajian eksperimental komparasi efisiensi waktu eksekusi dan konsumsi memori algoritma pengurutan tingkat lanjut: Merge Sort, Quick Sort, dan Shell Sort terhadap variasi ukuran dataset dan kondisi awal data (terurut acak, terurut terbalik, dan hampir terurut).

1. Landasan Teori dan Analisis Asimptotik

Algoritma pengurutan lanjutan memanfaatkan strategi divide and conquer atau reduksi gap inkremental untuk melampaui batas bawah $\mathcal{O}(n^2)$ algoritma sederhana:

• Merge Sort: Membagi array secara rekursif menjadi dua sub-array berukuran sama, mengurutkannya, lalu menggabungkannya (merge). Kompleksitas waktu stabil:

• Quick Sort: Memilih elemen pivot, mempartisi array ke dalam sub-array elemen yang lebih kecil dan lebih besar dari pivot, lalu mengurutkan sub-array secara rekursif:

• Shell Sort: Generalisasi Insertion Sort dengan membandingkan elemen yang terpisah oleh jarak gap tertentu yang menyusut secara bertahap hingga bernilai 1.

2. Hasil Eksperimen dan Metrik Waktu

Eksperimen dilakukan pada dataset numerik mulai dari $n = 1.000$ hingga $n = 50.000$ elemen. Hasil menunjukkan Quick Sort memiliki koefisien konstanta waktu terkecil pada data terdistribusi acak seragam, sedangkan Merge Sort unggul dalam kestabilan urutan elemen duplikat (stable sort).

3. Berkas Tugas Terlampir

• Berkas presentasi hasil eksperimen: TUGAS_ASD_Pertemuan9.pptx yang memuat visualisasi grafik perbandingan milidetik eksekusi, analisis memory overhead, dan rekomendasi pemilihan algoritma pada sistem produksi.