UTS Analisis dan Strategi Algoritma 2025

Pilih cabang sesuai digit akhir NIM: 1,3,5 untuk min-max; 0,4,6,8 untuk merge sort; 2,7,9 untuk quicksort. Soal 2 bergantung tugas pribadi, sehingga contoh di bawah adalah ilustrasi, bukan klaim isi tugas mahasiswa.

1. Cabang min-max

Brute force. Asumsikan $n\ge1$: inisialisasi min=max=A[1]; periksa setiap A[2..n] terhadap min dan max, lalu perbarui jika perlu. Jumlah perbandingan nilai tepat $2(n-1)$ dan waktu $T(n)=\Theta(n)$.

Divide and conquer. Bagi larik di tengah; selesaikan min dan max kedua bagian, lalu gabungkan dengan min(minKiri,minKanan) dan max(maxKiri,maxKanan). Satu elemen adalah basis. Dengan basis dua elemen satu perbandingan dan $n$ pangkat dua, $T(n)=2T(n/2)+2$, $T(2)=1$, sehingga $T(n)=3n/2-2$ perbandingan dan $O(n)$ waktu; stack $O(\log n)$. Contoh [8,3,6,1] terbagi menjadi [8,3] menghasilkan (3,8) dan [6,1] menghasilkan (1,6), digabung menjadi (1,8).

1. Cabang pengurutan

Brute force. Bandingkan setiap pasangan $i<j$ dan tukar bila A[i]>A[j]. Ini menempatkan nilai terkecil tersisa di posisi i; jumlah perbandingan $\sum_{i=1}^{n-1}(n-i)=n(n-1)/2$, jadi $\Theta(n^2)$.

Merge sort untuk kelompok 0,4,6,8: pisah dua, urutkan masing-masing, lalu gabungkan secara terurut. $T(n)=2T(n/2)+\Theta(n)=\Theta(n\log n)$; ruang bantu $O(n)$. [8,3,6,1] → [8,3] | [6,1] → [3,8] | [1,6] → [1,3,6,8].

Quicksort untuk kelompok 2,7,9: pilih pivot, partisi lebih kecil dan lebih besar, urutkan kedua bagian secara rekursif. Pada partisi seimbang $T(n)=2T(n/2)+\Theta(n)=\Theta(n\log n)$; terburuk $T(n)=T(n-1)+\Theta(n)=\Theta(n^2)$. Contoh pivot 8 pada [8,3,6,1] menghasilkan [3,6,1] | 8, kemudian pivot 3 menghasilkan [1] | 3 | [6], sehingga [1,3,6,8]. Insertion sort dan selection sort yang disebut dalam soal adalah alternatif, tetapi keduanya biasanya diklasifikasikan decrease-and-conquer, bukan divide-and-conquer.

2. Contoh studi kasus rekursif

Contoh terpisah dari tugas pribadi: menghitung jumlah elemen array dengan membagi dua dan menjumlah hasil kedua bagian. Basis satu elemen mengembalikan elemen tersebut. Rekurens $T(n)=2T(n/2)+\Theta(1)$; $a=2,b=2$, sehingga $n^{\log_b a}=n$ dan Teorema Master kasus 1 memberi $\Theta(n)$. Ganti contoh ini dengan kasus tugas ketiga sendiri bila diminta secara personal.