for (i in 1:10) {
print(i)
}[1] 1
[1] 2
[1] 3
[1] 4
[1] 5
[1] 6
[1] 7
[1] 8
[1] 9
[1] 10Praktikum Pemrograman Statistika
Trace It Till You Make It: Dry Running & Iterasi di R
Mengapa Perlu Menelusuri Algoritma?
Algoritma adalah urutan langkah logis dan terbatas yang dirancang untuk menyelesaikan suatu masalah. Pada dunia pemrograman, algoritma menjadi inti dari proses berpikir komputasional, yaitu mengubah pernyataan-pernyataan solusi menjadi instruksi yang bisa dijalankan oleh komputer. Namun, agar sebuah algoritma benar-benar dapat diandalkan, kita perlu memahami tidak hanya hasil akhirnya, tetapi juga bagaimana proses di dalamnya bekerja.
Salah satu teknik dasar yang digunakan untuk memahami alur kerja algoritma adalah dry running. Dry running adalah proses menelusuri algoritma secara manual, langkah demi langkah, sambil mencatat perubahan nilai setiap variabel yang terlibat. Teknik ini sangat bermanfaat untuk mengecek apakah logika program sudah sesuai, apakah hasil yang diperoleh akurat, serta untuk mengidentifikasi dan memperbaiki potensi kesalahan sebelum program dijalankan pada data yang lebih besar.
Untuk membantu proses penelusuran, digunakan trace table, yaitu tabel sederhana yang mencatat nilai-nilai variabel utama di setiap iterasi atau tahap eksekusi. Trace table memungkinkan kita melihat bagaimana suatu algoritma memproses input secara bertahap menuju output, sehingga sangat efektif digunakan dalam proses debugging dan pembelajaran.
Untuk melihat bagaimana logika perbandingan bekerja, kita dapat menelusuri iterasi demi iterasi menggunakan trace table seperti berikut:
Sumber: OTDCS – Algorithms
Trace table ini membantu kita memahami bagaimana nilai maksimum diperbarui secara bertahap. Ini adalah praktik yang sangat penting dalam debugging dan mengembangkan algoritma.
Struktur Iterasi dalam Pemrograman
Dalam pemrograman, banyak masalah diselesaikan dengan pendekatan berulang (iteratif), yaitu proses yang dilakukan berulang-ulang hingga kondisi tertentu terpenuhi. Bahasa R menyediakan dua struktur utama untuk melakukan iterasi:
for loop
Digunakan ketika jumlah iterasi telah diketahui sebelumnya, misalnya menjelajah vektor dari indeks 1 sampai 10. Contohnya untuk membuat loop untuk mencetak angka 1 sampai 10. Variabel i akan mengambil nilai dari 1 hingga 10 secara berurutan.
while loop
Digunakan ketika jumlah iterasi belum tentu diketahui, dan proses hanya akan berlanjut selama suatu kondisi terpenuhi. Contohnya untuk membuat loop yang juga mencetak angka 1 sampai 10, tetapi proses berhenti hanya jika kondisi i <= 10 tidak lagi dipenuhi.
i <- 1
while (i <= 10) {
print(i)
i <- i + 1
}[1] 1
[1] 2
[1] 3
[1] 4
[1] 5
[1] 6
[1] 7
[1] 8
[1] 9
[1] 10Contoh Kasus: Mencari Nilai Maksimum dari Vektor
Sekarang kita terapkan iterasi dalam bentuk lebih aplikatif: mencari nilai maksimum dari sebuah vektor numerik. Misalnya, kita punya vektor:
x <- c(15, 18, 10, 8, 20)Kita perlu untuk mencari elemen terbesar dalam vektor x hanya dengan menggunakan logika for loop dan perbandingan, tanpa max().
x <- c(15, 18, 10, 8, 20)
max_val <- x[1]
for (i in 2:length(x)) {
if (x[i] > max_val) {
max_val <- x[i]
}
}
max_val[1] 20Kode di atas bekerja dengan menyimpan nilai awal x[1] sebagai kandidat maksimum (max_val), lalu membandingkan satu per satu elemen berikutnya. Jika ada elemen yang lebih besar, maka max_val diganti dengan nilai tersebut.
Untuk memahami bagaimana kode tersebut bekerja secara bertahap, kita bisa membuat trace table. Ini adalah tabel yang mencatat nilai variabel penting di setiap iterasi loop.
| Iterasi | i |
x[i] |
max_val (sebelum) |
Apakah x[i] > max_val? |
max_val (setelah) |
|---|---|---|---|---|---|
| 1 | 2 | 18 | 15 | Ya | 18 |
| 2 | 3 | 10 | 18 | Tidak | 18 |
| 3 | 4 | 8 | 18 | Tidak | 18 |
| 4 | 5 | 20 | 18 | Ya | 20 |
Dari trace table ini terlihat bahwa nilai maksimum berhasil diperbarui dua kali: dari 15 → 18, dan 18 → 20.
Setelah memahami cara kerja iterasi dan membuat trace table untuk melacak alur program, kini saatnya menerapkan logika tersebut dalam bentuk fungsi. Dengan membuat fungsi sendiri, kita belajar bagaimana menyusun blok kode yang bisa digunakan kembali dan dieksekusi secara modular. Kita akan membuat sebuah fungsi bernama my_max() yang menerima sebuah vektor numerik sebagai input dan mengembalikan elemen terbesar dari vektor tersebut. Fungsi ini menggunakan pendekatan iteratif (dengan for loop) dan logika perbandingan untuk menentukan nilai maksimum—mirip seperti yang kita lakukan secara manual sebelumnya.
my_max <- function(x) {
max_val <- x[1]
for (i in 2:length(x)) {
if (x[i] > max_val) {
max_val <- x[i]
}
}
return(max_val)
}Fungsi ini akan bekerja pada vektor yang tidak kosong dan memiliki panjang minimal satu elemen. Ia memulai dengan menjadikan elemen pertama sebagai kandidat maksimum, kemudian memeriksa elemen lain satu per satu, memperbarui max_val jika ditemukan nilai yang lebih besar.
Langkah selanjutnya adalah membandingkan hasil dari fungsi my_max() dengan fungsi bawaan R yaitu max() untuk memastikan bahwa hasil keduanya sama.
x <- c(15, 18, 10, 8, 20)
my_max(x) # 20[1] 20max(x) # 20[1] 20# Verifikasi kesamaan
my_max(x) == max(x)[1] TRUEBenchmarking: Mengukur Performa Fungsi
Mengetahui bahwa dua fungsi menghasilkan output yang sama bukan akhir dari cerita. Dalam praktik pemrograman nyata, performa juga sangat penting, terutama saat berhadapan dengan data berukuran besar.
Untuk itu, kita gunakan package microbenchmark dari R untuk mengukur dan membandingkan kecepatan eksekusi my_max() dengan max(). Hasil dari microbenchmark akan menunjukkan statistik waktu eksekusi seperti mean, median, dan minimum untuk masing-masing fungsi.
library(microbenchmark)microbenchmark(
custom = my_max(x),
builtin = max(x)
)Hasil benchmarking biasanya menunjukkan bahwa fungsi max() jauh lebih cepat dibandingkan my_max() yang kita buat sendiri. Hal ini wajar karena max() merupakan fungsi internal yang telah dioptimasi dalam level bahasa C di balik layar R. Namun, membuat fungsi seperti my_max() tetap merupakan latihan penting karena:
- Melatih pemahaman terhadap logika iterasi dan perbandingan.
- Mengajarkan dasar pengembangan fungsi.
- Menjadi pijakan untuk memahami topik efisiensi algoritma dan kompleksitas waktu (time complexity).
Mengenal Algoritma Sorting
Sorting atau pengurutan adalah salah satu proses dasar dalam pemrograman, yang digunakan untuk menyusun elemen data dalam urutan tertentu—biasanya menaik (ascending) atau menurun (descending). Operasi sorting sangat penting karena menjadi fondasi bagi banyak algoritma lain (pencarian, klasifikasi, dll.).
Beberapa algoritma sorting dasar antara lain:
- Bubble Sort: membandingkan elemen bersebelahan dan menukar jika tidak sesuai urutan.
- Selection Sort: mencari elemen terkecil dan menempatkannya di posisi awal.
- Insertion Sort: menyisipkan elemen ke posisi yang tepat dalam bagian array yang telah terurut.
- Merge Sort: pendekatan divide-and-conquer, membagi array menjadi bagian kecil, mengurutkan masing-masing, lalu menggabungkan.
- Quick Sort: membagi array berdasarkan pivot, lalu mengurutkan bagian kiri dan kanan secara rekursif.
Referensi lanjutan: Sumber: GeeksForGeeks – Sorting Algorithms
Menyusun Algoritma Sorting Sendiri di R
Untuk memahami bagaimana algoritma sorting bekerja, kita bisa mencoba mengimplementasikannya sendiri dari nol. Salah satu algoritma paling sederhana untuk ini adalah Bubble Sort.
Prinsip dari Bubble Sort adalah membandingkan pasangan elemen yang berdekatan dalam array, lalu menukarnya jika tidak berada dalam urutan yang benar (misalnya jika ingin menaik, maka jika elemen kiri lebih besar dari kanan). Proses ini diulang terus menerus sehingga elemen terbesar “menggelembung” ke posisi paling akhir, lalu proses diulangi pada sisa elemen.
Mari kita terapkan Bubble Sort untuk menyusun vektor berikut:
x <- c(3, 1, 4, 1, 5, 9, 2, 6, 5)Untuk melakukan pengurutan, iterasi yang akan digunakan terdiri dari dua tingkat:
Iterasi luar (loop pertama) berfungsi untuk memastikan semua elemen diperiksa sebanyak
n-1kali (dengannadalah panjang vektor).Iterasi dalam (loop kedua) digunakan untuk membandingkan dan menukar pasangan elemen dalam jangkauan tertentu.
Uniknya, pada setiap putaran iterasi luar, elemen terbesar di bagian yang sedang diproses akan terdorong ke posisi paling belakang. Artinya, pada putaran berikutnya, elemen terakhir sudah dalam posisi yang benar dan tidak perlu dibandingkan lagi. Oleh karena itu, jumlah langkah pada iterasi dalam akan berkurang seiring meningkatnya iterasi luar (pada kasus ini diakomodir dengan n_x - i).
Simulasi Proses Awal Bubble Sort:
- Putaran pertama:
- Bandingkan 3 dan 1 → 1 lebih kecil → tukar →
[1, 3, 4, 1, 5, 9, 2, 6, 5] - Bandingkan 3 dan 4 → sudah urut → tidak ditukar
- Bandingkan 4 dan 1 → tukar →
[1, 3, 1, 4, 5, 9, 2, 6, 5] - Bandingkan 4 dan 5 → sudah urut → tidak ditukar
- Bandingkan 5 dan 9 → sudah urut → tidak ditukar
- Bandingkan 9 dan 2 → tukar →
[1, 3, 1, 4, 5, 2, 9, 6, 5] - Bandingkan 9 dan 6 → tukar →
[1, 3, 1, 4, 5, 2, 6, 9, 5] - Bandingkan 9 dan 5 → tukar →
[1, 3, 1, 4, 5, 2, 6, 5, 9]
- Bandingkan 3 dan 1 → 1 lebih kecil → tukar →
Hasil akhir dari putaran pertama: elemen terbesar (9) sudah berada di posisi terakhir.
- Putaran kedua:
- Sekarang kita cukup memeriksa hingga elemen ke-8 saja (karena 9 sudah berada di tempat yang tepat).
- Proses yang sama dilakukan untuk membawa elemen terbesar berikutnya ke posisi ke-8.
Proses ini diulang hingga tidak ada lagi pasangan yang perlu ditukar. Karena setiap putaran memastikan satu elemen “terbesar” berpindah ke posisi yang benar, jumlah elemen yang harus diperiksa akan berkurang satu demi satu di setiap putaran.
Berikut implementasi dari algoritma Bubble Sort pada R.
x[1] 3 1 4 1 5 9 2 6 5# Salin ke objek baru untuk diurutkan
x_sort <- x
n_x <- length(x_sort)
# Bubble Sort: dua tingkat iterasi
for(i in 1:(n_x - 1)) {
for(j in 1:(n_x - i)) {
if(x_sort[j + 1] < x_sort[j]) {
# Penukaran elemen
tmp <- x_sort[j]
x_sort[j] <- x_sort[j + 1]
x_sort[j + 1] <- tmp
}
}
}
x_sort[1] 1 1 2 3 4 5 5 6 9Iterasi i |
Iterasi j |
Pasangan Dibandingkan | Apakah Tukar? | Vektor Setelah Pertukaran |
|---|---|---|---|---|
| 1 | 1 | 3 vs 1 | Ya | 1 3 4 1 5 9 2 6 5 |
| 1 | 2 | 3 vs 4 | Tidak | 1 3 4 1 5 9 2 6 5 |
| 1 | 3 | 4 vs 1 | Ya | 1 3 1 4 5 9 2 6 5 |
| 1 | 4 | 4 vs 5 | Tidak | 1 3 1 4 5 9 2 6 5 |
| 1 | 5 | 5 vs 9 | Tidak | 1 3 1 4 5 9 2 6 5 |
| 1 | 6 | 9 vs 2 | Ya | 1 3 1 4 5 2 9 6 5 |
| 1 | 7 | 9 vs 6 | Ya | 1 3 1 4 5 2 6 9 5 |
| 1 | 8 | 9 vs 5 | Ya | 1 3 1 4 5 2 6 5 9 |
| 2 | 1 | 1 vs 3 | Tidak | 1 3 1 4 5 2 6 5 9 |
| 2 | 2 | 3 vs 1 | Ya | 1 1 3 4 5 2 6 5 9 |
| 2 | 3 | 3 vs 4 | Tidak | 1 1 3 4 5 2 6 5 9 |
| 2 | 4 | 4 vs 5 | Tidak | 1 1 3 4 5 2 6 5 9 |
| 2 | 5 | 5 vs 2 | Ya | 1 1 3 4 2 5 6 5 9 |
| 2 | 6 | 5 vs 6 | Tidak | 1 1 3 4 2 5 6 5 9 |
| 2 | 7 | 6 vs 5 | Ya | 1 1 3 4 2 5 5 6 9 |
| 3 | 1 | 1 vs 1 | Tidak | 1 1 3 4 2 5 5 6 9 |
| 3 | 2 | 1 vs 3 | Tidak | 1 1 3 4 2 5 5 6 9 |
| 3 | 3 | 3 vs 4 | Tidak | 1 1 3 4 2 5 5 6 9 |
| 3 | 4 | 4 vs 2 | Ya | 1 1 3 2 4 5 5 6 9 |
| 3 | 5 | 4 vs 5 | Tidak | 1 1 3 2 4 5 5 6 9 |
| 3 | 6 | 5 vs 5 | Tidak | 1 1 3 2 4 5 5 6 9 |
| 4 | 1 | 1 vs 1 | Tidak | 1 1 3 2 4 5 5 6 9 |
| 4 | 2 | 1 vs 3 | Tidak | 1 1 3 2 4 5 5 6 9 |
| 4 | 3 | 3 vs 2 | Ya | 1 1 2 3 4 5 5 6 9 |
| 4 | 4 | 3 vs 4 | Tidak | 1 1 2 3 4 5 5 6 9 |
| 4 | 5 | 5 vs 5 | Tidak | 1 1 2 3 4 5 5 6 9 |
| 5 | 1 | 1 vs 1 | Tidak | 1 1 2 3 4 5 5 6 9 |
| 5 | 2 | 1 vs 2 | Tidak | 1 1 2 3 4 5 5 6 9 |
| 5 | 3 | 2 vs 3 | Tidak | 1 1 2 3 4 5 5 6 9 |
| 5 | 4 | 3 vs 4 | Tidak | 1 1 2 3 4 5 5 6 9 |
| 6 | 1 | 1 vs 1 | Tidak | 1 1 2 3 4 5 5 6 9 |
| 6 | 2 | 1 vs 2 | Tidak | 1 1 2 3 4 5 5 6 9 |
| 6 | 3 | 2 vs 3 | Tidak | 1 1 2 3 4 5 5 6 9 |
| 7 | 1 | 1 vs 1 | Tidak | 1 1 2 3 4 5 5 6 9 |
| 7 | 2 | 1 vs 2 | Tidak | 1 1 2 3 4 5 5 6 9 |
| 8 | 1 | 1 vs 1 | Tidak | 1 1 2 3 4 5 5 6 9 |
Agar kode lebih terstruktur dan dapat digunakan kembali, kita bisa mengemas logika Bubble Sort ke dalam sebuah fungsi bernama bubble_sort(). Fungsi ini menerima sebuah vektor sebagai input, melakukan pengurutan, dan mengembalikan hasilnya.
bubble_sort <- function(vec) {
n <- length(vec)
for(i in 1:(n - 1)) {
for(j in 1:(n - i)) {
if(vec[j + 1] < vec[j]) {
tmp <- vec[j]
vec[j] <- vec[j + 1]
vec[j + 1] <- tmp
}
}
}
return(vec)
}benchmark_result <- microbenchmark(
bubble_sort = bubble_sort(x),
sort_builtin = sort(x)
)
benchmark_resultMenelusuri Deret Tak Hingga dengan Iterasi
Dalam dunia komputasi numerik, banyak permasalahan matematika tidak dapat diselesaikan dengan satu langkah tertutup (closed-form solution), melainkan melalui pendekatan bertahap hingga mencapai konvergensi. Salah satu contoh klasiknya adalah penjumlahan deret tak hingga (infinite series). Kita akan belajar bagaimana menuliskan rumus deret dalam bentuk fungsi matematis, kemudian menelusurinya menggunakan iterasi while di R hingga mencapai hasil yang stabil (perubahan nilai antar iterasi sangat kecil).
Memahami Bentuk Deret
Perhatikan deret berikut:
\[ z = 2 - \frac{6}{5} + \frac{8}{10} - \frac{10}{17} + \frac{12}{26} - \dots \]
Jika diperhatikan, setiap suku memiliki pola pada pembilang dan penyebutnya, serta tanda yang berganti-ganti (+ dan –). Untuk menemukan formula umum deret ini, kita amati:
| n | Tanda | Pembilang | Penyebut |
|---|---|---|---|
| 1 | + | 2 | 1² + 1 = 2 |
| 2 | − | 6 | 2² + 1 = 5 |
| 3 | + | 8 | 3² + 1 = 10 |
| 4 | − | 10 | 4² + 1 = 17 |
| 5 | + | 12 | 5² + 1 = 26 |
Maka pola umum suku ke-n dapat ditulis sebagai:
\[ z_n = (-1)^{n+1} \cdot \frac{2n + 2}{n^2 + 1} \]
Sehingga deret tak hingga dapat dinyatakan dengan notasi sigma:
\[ z = \sum_{n=1}^{\infty} (-1)^{n+1} \cdot \frac{2n + 2}{n^2 + 1} \]
Menyusun Fungsi Matematis dalam R
Sekarang kita tuliskan fungsi R untuk menghitung suku ke-n dari deret tersebut.
# Fungsi untuk menghitung suku ke-n dari deret
fz <- function(n) {
(-1)^(n + 1) * (2 * n + 2) / (n^2 + 1)
}Kita bisa menguji hasilnya untuk beberapa nilai n pertama:
fz(1)[1] 2fz(2)[1] -1.2fz(3)[1] 0.8fz(4)[1] -0.5882353fz(5)[1] 0.4615385Menjumlahkan Deret dengan Iterasi while
Karena ini deret tak hingga, kita tidak bisa langsung menjumlahkan seluruh suku. Sebaliknya, kita akan menambahkan suku satu per satu hingga perbedaan antara dua hasil penjumlahan berturut-turut sangat kecil — misalnya, kurang dari \(10^{-5}\).
Kita gunakan variabel z0 untuk menyimpan jumlah sebelumnya dan z1 untuk jumlah baru di setiap iterasi. Kode berikut menjumlahkan deret secara bertahap hingga hasilnya stabil (konvergen).
# Inisialisasi variabel
e <- 10 # selisih awal yang besar agar loop berjalan
z0 <- 0 # jumlah awal
n <- 1 # penghitung iterasi
# Iterasi while hingga konvergen
while (e > 10^(-5)) {
z1 <- z0 + fz(n)
e <- abs(z1 - z0) # selisih antara dua hasil terakhir
z0 <- z1
n <- n + 1
}
z1[1] 1.267197n[1] 200002Membuat Fungsi Umum Penjumlah Deret Tak Hingga
Pada contoh sebelumnya, kita telah membuat fungsi fz() untuk menghitung suku ke-n dari deret tertentu, lalu menjumlahkannya menggunakan iterasi while.
Namun, agar lebih fleksibel dan dapat digunakan untuk berbagai bentuk deret, kita dapat membuat fungsi umum yang menerima fungsi deret (term_function) sebagai argumen.
Fungsi ini akan:
- Melakukan penjumlahan suku demi suku hingga hasilnya konvergen (selisih perubahan <
tolerance). - Menghentikan proses jika sudah mencapai jumlah iterasi maksimum (
max_iter). - Mengembalikan hasil akhir, jumlah iterasi, dan status konvergensi.
# Fungsi umum untuk menjumlahkan deret tak hingga
sum_infinite_series <- function(term_function, tolerance = 1e-5, max_iter = 1e10) {
e <- 10 # selisih awal
z0 <- 0 # jumlah awal
n <- 1 # penghitung iterasi
# iterasi while hingga konvergen atau mencapai batas iterasi
while (e > tolerance && n <= max_iter) {
z1 <- z0 + term_function(n)
e <- abs(z1 - z0)
z0 <- z1
n <- n + 1
}
# keluaran berupa nilai akhir, jumlah iterasi, dan status konvergensi
result <- list(
sum = z0,
iterations = n - 1,
converged = e <= tolerance
)
return(result)
}Kita bisa memanggil fungsi umum ini menggunakan fz() yang sudah kita buat sebelumnya. Hasil keluaran akan berupa daftar (list) berisi nilai hasil penjumlahan, jumlah iterasi yang dilakukan, dan status apakah deret telah mencapai konvergensi.
sum_infinite_series(fz)$sum
[1] 1.267197
$iterations
[1] 200001
$converged
[1] TRUEParameter tolerance dan max_iter memengaruhi bagaimana algoritma iteratif mendekati hasil konvergen.
tolerancemenentukan seberapa kecil perbedaan antara dua iterasi terakhir agar dianggap stabil.
Semakin keciltolerance, semakin tinggi presisi hasil, tetapi iterasi akan berlangsung lebih lama.max_iteradalah batas maksimum iterasi untuk mencegah loop tak berujung.
Jika deret tidak mencapai konvergensi sebelum batas ini, algoritma akan berhenti otomatis dengan statusconverged = FALSE.