# 1. Latihan 1 no 1
nilai <- c(40, 96, 57, 52, 84, 72, 60, 85, 86, 73, 81, 78, 89, 54, 62)
n <- length(nilai)
rata <- sum(nilai) / n
jumlah_kuadrat <- 0
for (x in nilai) {
jumlah_kuadrat <- jumlah_kuadrat + (x - rata)^2
}
s <- sqrt(jumlah_kuadrat / (n - 1))
print(s)
## [1] 16.25892
#Latihan 1 no 2
cari_indeks_maks_terakhir <- function(L) {
imaks <- 1
if (length(L) > 1) {
for (i in 2:length(L)) {
if (L[i] >= L[imaks]) {
imaks <- i
}
}
}
imaks
}
cat("Indeks maksimum terakhir:",
cari_indeks_maks_terakhir(c(4, 9, 2, 9, 1)), "\n")
## Indeks maksimum terakhir: 4
# latihan 1 no 3
maks_min_sekaligus <- function(L) {
stopifnot(length(L) > 0)
maks <- L[1]
min <- L[1]
if (length(L) > 1) {
for (i in 2:length(L)) {
if (L[i] > maks) maks <- L[i]
if (L[i] < min) min <- L[i]
}
}
c(maksimum = maks, minimum = min)
}
print(maks_min_sekaligus(c(7, 2, 11, 4, 1)))
## maksimum minimum
## 11 1
# latihan 1 no 4
dax <- EuStockMarkets[, "DAX"]
kenaikan_dax <- dax[2:length(dax)] - dax[1:(length(dax) - 1)]
posisi_kenaikan <- which.max(kenaikan_dax)
cat("Kenaikan DAX terbesar:", kenaikan_dax[posisi_kenaikan],
"pada hari ke-", posisi_kenaikan + 1, "\n")
## Kenaikan DAX terbesar: 160.97 pada hari ke- 1653
# latihan 1 no 5
jual <- matrix(
c(10, 45, 34, 43,
63, 69, 22, 13,
13, 82, 23, 60),
nrow = 3,
byrow = TRUE
)
jumlah_per_minggu <- numeric(ncol(jual))
rata_rata_per_minggu <- numeric(ncol(jual))
for (j in 1:ncol(jual)) {
jumlah_per_minggu[j] <- 0
for (i in 1:nrow(jual)) {
jumlah_per_minggu[j] <- jumlah_per_minggu[j] + jual[i, j]
}
rata_rata_per_minggu[j] <- jumlah_per_minggu[j] / nrow(jual)
}
print(jual)
## [,1] [,2] [,3] [,4]
## [1,] 10 45 34 43
## [2,] 63 69 22 13
## [3,] 13 82 23 60
cat("Jumlah per minggu:", jumlah_per_minggu, "\n")
## Jumlah per minggu: 86 196 79 116
cat("Rata-rata per minggu:", rata_rata_per_minggu, "\n")
## Rata-rata per minggu: 28.66667 65.33333 26.33333 38.66667
cat("Minggu dengan penjualan tertinggi:",
which.max(jumlah_per_minggu), "\n")
## Minggu dengan penjualan tertinggi: 2
#Latihan 1 no 6
M <- matrix(0, nrow = 3, ncol = 3)
M[1, 2] <- 7
print(M)
## [,1] [,2] [,3]
## [1,] 0 7 0
## [2,] 0 0 0
## [3,] 0 0 0
# Latihan 2
# Sequential search tanpa boolean, dengan jejak
seq_search1_trace <- function(L, x) {
n <- length(L)
i <- 1
cmp <- 0
cat("SeqSearch1, x =", x, "\n")
while (i < n && L[i] != x) {
cmp <- cmp + 1
cat("i =", i, ", L[i] =", L[i], ": belum cocok\n")
i <- i + 1
}
if (i <= n) {
cmp <- cmp + 1
cat("i =", i, ", L[i] =", L[i], ": pemeriksaan akhir\n")
idx <- if (L[i] == x) i else 0
} else {
idx <- 0
}
cat("Indeks =", idx, "; perbandingan =", cmp, "\n")
invisible(c(indeks = idx, perbandingan = cmp))
}
# Sequential search dengan boolean, dengan jejak
seq_search2_trace <- function(L, x) {
i <- 1
n <- length(L)
ketemu <- FALSE
cmp <- 0
cat("SeqSearch2, x =", x, "\n")
while (i <= n && !ketemu) {
cmp <- cmp + 1
cat("i =", i, ", L[i] =", L[i])
if (L[i] == x) {
ketemu <- TRUE
cat(": ketemu\n")
} else {
cat(": belum cocok\n")
i <- i + 1
}
}
idx <- if (ketemu) i else 0
cat("Indeks =", idx, "; perbandingan =", cmp, "\n")
invisible(c(indeks = idx, perbandingan = cmp))
}
L_seq <- c(7, 3, 9, 3, 5)
seq_search1_trace(L_seq, 3)
## SeqSearch1, x = 3
## i = 1 , L[i] = 7 : belum cocok
## i = 2 , L[i] = 3 : pemeriksaan akhir
## Indeks = 2 ; perbandingan = 2
seq_search2_trace(L_seq, 3)
## SeqSearch2, x = 3
## i = 1 , L[i] = 7: belum cocok
## i = 2 , L[i] = 3: ketemu
## Indeks = 2 ; perbandingan = 2
seq_search1_trace(L_seq, 8)
## SeqSearch1, x = 8
## i = 1 , L[i] = 7 : belum cocok
## i = 2 , L[i] = 3 : belum cocok
## i = 3 , L[i] = 9 : belum cocok
## i = 4 , L[i] = 3 : belum cocok
## i = 5 , L[i] = 5 : pemeriksaan akhir
## Indeks = 0 ; perbandingan = 5
seq_search2_trace(L_seq, 8)
## SeqSearch2, x = 8
## i = 1 , L[i] = 7: belum cocok
## i = 2 , L[i] = 3: belum cocok
## i = 3 , L[i] = 9: belum cocok
## i = 4 , L[i] = 3: belum cocok
## i = 5 , L[i] = 5: belum cocok
## Indeks = 0 ; perbandingan = 5
# Bentuk aman bila bahasa tidak memakai short-circuit:
# periksa batas indeks dan elemen secara terpisah
seq_search_tanpa_short_circuit <- function(L, x) {
i <- 1
n <- length(L)
while (i <= n) {
if (L[i] == x) return(i)
i <- i + 1
}
0
}
# Binary search dengan boolean, untuk larik menaik
bin_search1_trace <- function(L, x) {
i <- 1
j <- length(L)
ketemu <- FALSE
cmp <- 0
k <- 0
cat("BinSearch1, x =", x, "\n")
while (!ketemu && i <= j) {
k <- (i + j) %/% 2
cmp <- cmp + 1
cat("i =", i, "j =", j, "k =", k, "L[k] =", L[k])
if (L[k] == x) {
ketemu <- TRUE
cat(": ketemu\n")
} else if (L[k] < x) {
i <- k + 1
cat(": cari kanan\n")
} else {
j <- k - 1
cat(": cari kiri\n")
}
}
idx <- if (ketemu) k else 0
cat("Indeks =", idx, "; perbandingan =", cmp, "\n")
invisible(c(indeks = idx, perbandingan = cmp))
}
# Binary search tanpa boolean
bin_search2_trace <- function(L, x) {
i <- 1
j <- length(L)
cmp <- 0
cat("BinSearch2, x =", x, "\n")
while (i < j) {
k <- (i + j) %/% 2
cmp <- cmp + 1
cat("i =", i, "j =", j, "k =", k, "L[k] =", L[k])
if (L[k] < x) {
i <- k + 1
cat(": cari kanan\n")
} else {
j <- k
cat(": cari kiri termasuk k\n")
}
}
cmp <- cmp + 1
idx <- if (L[i] == x) i else 0
cat("Kandidat akhir:", i, "nilai", L[i],
"; indeks =", idx,
"; perbandingan termasuk akhir =", cmp, "\n")
invisible(c(indeks = idx, perbandingan = cmp))
}
L_bin <- c(2, 5, 8, 12, 16, 23, 38, 56, 72, 91)
bin_search1_trace(L_bin, 23)
## BinSearch1, x = 23
## i = 1 j = 10 k = 5 L[k] = 16: cari kanan
## i = 6 j = 10 k = 8 L[k] = 56: cari kiri
## i = 6 j = 7 k = 6 L[k] = 23: ketemu
## Indeks = 6 ; perbandingan = 3
bin_search1_trace(L_bin, 6)
## BinSearch1, x = 6
## i = 1 j = 10 k = 5 L[k] = 16: cari kiri
## i = 1 j = 4 k = 2 L[k] = 5: cari kanan
## i = 3 j = 4 k = 3 L[k] = 8: cari kiri
## Indeks = 0 ; perbandingan = 3
bin_search2_trace(L_bin, 23)
## BinSearch2, x = 23
## i = 1 j = 10 k = 5 L[k] = 16: cari kanan
## i = 6 j = 10 k = 8 L[k] = 56: cari kiri termasuk k
## i = 6 j = 8 k = 7 L[k] = 38: cari kiri termasuk k
## i = 6 j = 7 k = 6 L[k] = 23: cari kiri termasuk k
## Kandidat akhir: 6 nilai 23 ; indeks = 6 ; perbandingan termasuk akhir = 5
bin_search2_trace(L_bin, 6)
## BinSearch2, x = 6
## i = 1 j = 10 k = 5 L[k] = 16: cari kiri termasuk k
## i = 1 j = 5 k = 3 L[k] = 8: cari kiri termasuk k
## i = 1 j = 3 k = 2 L[k] = 5: cari kanan
## Kandidat akhir: 3 nilai 8 ; indeks = 0 ; perbandingan termasuk akhir = 4
# Binary search untuk larik menurun
bin_search_menurun <- function(L, x) {
i <- 1
j <- length(L)
cmp <- 0
while (i <= j) {
k <- (i + j) %/% 2
cmp <- cmp + 1
if (L[k] == x) {
return(c(indeks = k, perbandingan = cmp))
}
if (L[k] > x) {
i <- k + 1
} else {
j <- k - 1
}
}
c(indeks = 0, perbandingan = cmp)
}
# Pencarian nama kota pada precip
kota <- names(precip)
kota_urut <- sort(kota)
x_kota <- "Seattle Tacoma"
seq_search_string_count <- function(L, x) {
cmp <- 0
for (i in seq_along(L)) {
cmp <- cmp + 1
if (L[i] == x) {
return(c(indeks = i, perbandingan = cmp))
}
}
c(indeks = 0, perbandingan = cmp)
}
bin_search_string_count <- function(L, x) {
i <- 1
j <- length(L)
cmp <- 0
while (i <= j) {
k <- (i + j) %/% 2
cmp <- cmp + 1
if (L[k] == x) {
return(c(indeks = k, perbandingan = cmp))
}
if (L[k] < x) {
i <- k + 1
} else {
j <- k - 1
}
}
c(indeks = 0, perbandingan = cmp)
}
cat("Sequential kota:",
seq_search_string_count(kota, x_kota), "\n")
## Sequential kota: 65 65
cat("Binary kota:",
bin_search_string_count(kota_urut, x_kota), "\n")
## Binary kota: 64 5
# Binary search rekursif
bin_search_rekursif <- function(L, x, kiri = 1, kanan = length(L)) {
if (kiri > kanan) return(0L)
tengah <- (kiri + kanan) %/% 2
if (L[tengah] == x) return(tengah)
if (L[tengah] < x) {
return(bin_search_rekursif(L, x, tengah + 1, kanan))
}
bin_search_rekursif(L, x, kiri, tengah - 1)
}
cat("Indeks 23:", bin_search_rekursif(L_bin, 23), "\n")
## Indeks 23: 6
cat("Maksimum perbandingan, n = 1.000.000:",
floor(log2(1000000)) + 1, "\n")
## Maksimum perbandingan, n = 1.000.000: 20
# Latihan 3
# Seleksi maksimum secara menurun, tampilkan setiap pass
selection_maks_menurun_trace <- function(L) {
A <- L
n <- length(A)
cat("Maksimum - awal:", A, "\n")
if (n > 1) {
for (i in 1:(n - 1)) {
imaks <- i
for (j in (i + 1):n) {
if (A[j] > A[imaks]) imaks <- j
}
tmp <- A[i]
A[i] <- A[imaks]
A[imaks] <- tmp
cat("Pass", i, ":", A, "\n")
}
}
invisible(A)
}
# Seleksi minimum secara menurun, tampilkan setiap pass
selection_min_menurun_trace <- function(L) {
A <- L
n <- length(A)
cat("Minimum - awal:", A, "\n")
if (n > 1) {
for (u in n:2) {
imin <- 1
for (j in 2:u) {
if (A[j] < A[imin]) imin <- j
}
tmp <- A[u]
A[u] <- A[imin]
A[imin] <- tmp
cat("Pass", n - u + 1, ":", A, "\n")
}
}
invisible(A)
}
data_sel <- c(25, 22, 18, 20, 15)
selection_maks_menurun_trace(data_sel)
## Maksimum - awal: 25 22 18 20 15
## Pass 1 : 25 22 18 20 15
## Pass 2 : 25 22 18 20 15
## Pass 3 : 25 22 20 18 15
## Pass 4 : 25 22 20 18 15
selection_min_menurun_trace(data_sel)
## Minimum - awal: 25 22 18 20 15
## Pass 1 : 25 22 18 20 15
## Pass 2 : 25 22 20 18 15
## Pass 3 : 25 22 20 18 15
## Pass 4 : 25 22 20 18 15
# Insertion sort menaik dengan hitungan perbandingan/pergeseran
insertion_sort_trace_count <- function(L) {
A <- L
n <- length(A)
perbandingan <- 0
pergeseran <- 0
cat("Data awal:", A, "\n")
if (n > 1) {
for (i in 2:n) {
y <- A[i]
j <- i - 1
while (j >= 1) {
perbandingan <- perbandingan + 1
if (y < A[j]) {
A[j + 1] <- A[j]
pergeseran <- pergeseran + 1
j <- j - 1
} else {
break
}
}
A[j + 1] <- y
cat("Pass", i - 1, "kunci", y, ":", A, "\n")
}
}
cat("Perbandingan:", perbandingan,
"; pergeseran:", pergeseran, "\n")
invisible(list(
larik = A,
perbandingan = perbandingan,
pergeseran = pergeseran
))
}
insertion_sort_trace_count(c(5, 4, 3, 2, 1))
## Data awal: 5 4 3 2 1
## Pass 1 kunci 4 : 4 5 3 2 1
## Pass 2 kunci 3 : 3 4 5 2 1
## Pass 3 kunci 2 : 2 3 4 5 1
## Pass 4 kunci 1 : 1 2 3 4 5
## Perbandingan: 10 ; pergeseran: 10
insertion_sort_trace_count(c(1, 2, 3, 5, 4))
## Data awal: 1 2 3 5 4
## Pass 1 kunci 2 : 1 2 3 5 4
## Pass 2 kunci 3 : 1 2 3 5 4
## Pass 3 kunci 5 : 1 2 3 5 4
## Pass 4 kunci 4 : 1 2 3 4 5
## Perbandingan: 5 ; pergeseran: 1
# Contoh selection sort tidak stabil dengan record
record <- data.frame(
nama = c("A", "B", "C"),
nilai = c(5, 5, 4),
stringsAsFactors = FALSE
)
cat("Record awal:\n")
## Record awal:
print(record)
## nama nilai
## 1 A 5
## 2 B 5
## 3 C 4
# Pass pertama selection sort minimum menaik:
# record C bertukar dengan record A
tmp <- record[1, ]
record[1, ] <- record[3, ]
record[3, ] <- tmp
cat("Setelah pass pertama:\n")
## Setelah pass pertama:
print(record)
## nama nilai
## 1 C 4
## 2 B 5
## 3 A 5
# Binary insertion sort stabil
binary_insertion_sort <- function(A) {
n <- length(A)
perbandingan_cari <- 0
pergeseran <- 0
if (n > 1) {
for (i in 2:n) {
y <- A[i]
lo <- 1
hi <- i
# Cari posisi setelah nilai yang sama agar stabil
while (lo < hi) {
mid <- (lo + hi) %/% 2
perbandingan_cari <- perbandingan_cari + 1
if (A[mid] <= y) {
lo <- mid + 1
} else {
hi <- mid
}
}
j <- i - 1
while (j >= lo) {
A[j + 1] <- A[j]
pergeseran <- pergeseran + 1
j <- j - 1
}
A[lo] <- y
}
}
list(
larik = A,
perbandingan_pencarian = perbandingan_cari,
pergeseran = pergeseran
)
}
print(binary_insertion_sort(c(5, 4, 3, 2, 1)))
## $larik
## [1] 1 2 3 4 5
##
## $perbandingan_pencarian
## [1] 8
##
## $pergeseran
## [1] 10
# 50 harga CAC pertama: selection sort dan insertion sort menurun
cac50 <- EuStockMarkets[1:50, "CAC"]
selection_sort_menurun_count <- function(A) {
n <- length(A)
cmp <- 0
pertukaran_pass <- 0
pertukaran_efektif <- 0
if (n > 1) {
for (i in 1:(n - 1)) {
imax <- i
for (j in (i + 1):n) {
cmp <- cmp + 1
if (A[j] > A[imax]) imax <- j
}
if (imax != i) {
tmp <- A[i]
A[i] <- A[imax]
A[imax] <- tmp
pertukaran_efektif <- pertukaran_efektif + 1
}
pertukaran_pass <- pertukaran_pass + 1
}
}
list(
larik = A,
perbandingan = cmp,
pertukaran_pass = pertukaran_pass,
pertukaran_efektif = pertukaran_efektif
)
}
insertion_sort_menurun_count <- function(A) {
n <- length(A)
cmp <- 0
pergeseran <- 0
if (n > 1) {
for (i in 2:n) {
y <- A[i]
j <- i - 1
while (j >= 1) {
cmp <- cmp + 1
if (A[j] < y) {
A[j + 1] <- A[j]
pergeseran <- pergeseran + 1
j <- j - 1
} else {
break
}
}
A[j + 1] <- y
}
}
list(
larik = A,
perbandingan = cmp,
pergeseran = pergeseran
)
}
hasil_selection <- selection_sort_menurun_count(cac50)
hasil_insertion <- insertion_sort_menurun_count(cac50)
cat("CAC menurun, selection sort:\n")
## CAC menurun, selection sort:
print(hasil_selection$larik)
## [1] 1873.2 1868.7 1864.3 1863.5 1860.8 1860.4 1857.7 1853.4 1851.8 1849.7
## [11] 1833.5 1820.3 1820.3 1820.3 1819.1 1808.8 1792.9 1789.5 1783.5 1782.4
## [21] 1780.4 1780.1 1778.1 1772.8 1768.9 1767.7 1766.8 1766.5 1763.5 1762.8
## [31] 1762.2 1759.8 1759.5 1758.1 1757.9 1757.5 1757.4 1756.6 1755.5 1754.7
## [41] 1754.3 1754.0 1750.5 1734.5 1725.6 1723.1 1718.0 1714.3 1708.1 1687.5
cat("CAC menurun, insertion sort:\n")
## CAC menurun, insertion sort:
print(hasil_insertion$larik)
## [1] 1873.2 1868.7 1864.3 1863.5 1860.8 1860.4 1857.7 1853.4 1851.8 1849.7
## [11] 1833.5 1820.3 1820.3 1820.3 1819.1 1808.8 1792.9 1789.5 1783.5 1782.4
## [21] 1780.4 1780.1 1778.1 1772.8 1768.9 1767.7 1766.8 1766.5 1763.5 1762.8
## [31] 1762.2 1759.8 1759.5 1758.1 1757.9 1757.5 1757.4 1756.6 1755.5 1754.7
## [41] 1754.3 1754.0 1750.5 1734.5 1725.6 1723.1 1718.0 1714.3 1708.1 1687.5
cat("Selection sort - perbandingan:",
hasil_selection$perbandingan,
"; pertukaran pass:", hasil_selection$pertukaran_pass,
"; pertukaran efektif:", hasil_selection$pertukaran_efektif, "\n")
## Selection sort - perbandingan: 1225 ; pertukaran pass: 49 ; pertukaran efektif: 47
cat("Insertion sort - perbandingan:",
hasil_insertion$perbandingan,
"; pergeseran:", hasil_insertion$pergeseran, "\n")
## Insertion sort - perbandingan: 1069 ; pergeseran: 1031