Analisis Komparatif Algoritma Pengurutan Data (Sorting 1 & Sorting 2)

Analisis Komparatif Algoritma Pengurutan Data: Teori, Kompleksitas, dan Stabilitas

Kajian analitis mendalam mengenai algoritma pengurutan data internal (internal sorting), perbandingan kompleksitas waktu kasus terbaik, rata-rata, dan terburuk, serta konsep stabilitas (sorting stability).

1. Klasifikasi Algoritma Berdasarkan Pendekatan Paradigma

1. Pendekatan Komparasi Sederhana ($O(n^2)$):
   • Bubble Sort: Menukarkan pasangan elemen bertetangga yang tidak berurutan secara berulang hingga seluruh larik terurut.
   • Selection Sort: Mencari nilai minimum dari bagian larik yang belum terurut dan menukarnya dengan elemen pada posisi aktif.
   • Insertion Sort: Mengambil satu elemen pada setiap iterasi dan menyisipkannya pada posisi yang tepat di subarray terurut. Sangat efisien untuk data yang hampir terurut (adaptive).
2. Pendekatan Divide and Conquer ($O(n \log n)$):
   • Merge Sort: Membagi array menjadi dua sub-bagian secara rekursif, mengurutkan masing-masing sub-bagian, lalu menggabungkannya (merge) dengan jaminan stabilitas.
   • Quick Sort: Memilih elemen poros (pivot), mempartisi elemen ke dalam sub-array yang lebih kecil atau lebih besar dari pivot, lalu menyelesaikannya secara rekursif.

2. Kriteria Evaluasi: Waktu, Memori, dan Stabilitas

• Stabilitas (Stability): Algoritma dikatakan stabil jika urutan relatif dari elemen-elemen yang memiliki kunci identik tidak berubah setelah pengurutan (contoh: Merge Sort stabil, sedangkan Quick Sort tidak stabil).
• Memori Tambahan (In-Place): Algoritma in-place hanya membutuhkan memori tambahan $O(1)$ di luar array masukan (contoh: Heap Sort, Quick Sort).

3. Berkas Terlampir

• Slide materi dasar pengurutan: Sorting 1.pptx.
• Slide materi pengurutan lanjutan: Sorting 2.pptx.