Alpro

LATIHAN MATERI 1 1. Tulis algoritma (notasi algoritmik), program Python, dan program R untuk menghitung simpangan baku nilai UTS pada contoh 1.2 tanpa memakai fungsi bawaan std/sd. BAHASA R :

simpangan_baku <- function(L) {
  n <- length(L)
  total <- 0
  for (x in L) total <- total + x
  rata <- total / n
  
  jumlah_kuadrat <- 0
  for (x in L) jumlah_kuadrat <- jumlah_kuadrat + (x - rata)^2
  sqrt(jumlah_kuadrat / (n - 1))
}

uts <- c(40, 96, 57, 52, 84, 72, 60, 85, 86, 73, 81, 78, 89, 54, 62)
cat("Simpangan Baku:", round(simpangan_baku(uts), 4), "\n") # Output: 16.5895

## Simpangan Baku: 16.2589

PYTHON :

def simpangan_baku(L):
    n = len(L)
    total = 0
    for x in L:
        total += x
    rata = total / n
    
    jumlah_kuadrat = 0
    for x in L:
        jumlah_kuadrat += (x - rata) ** 2
    return (jumlah_kuadrat / (n - 1)) ** 0.5

uts = [40, 96, 57, 52, 84, 72, 60, 85, 86, 73, 81, 78, 89, 54, 62]
print("Simpangan Baku:", round(simpangan_baku(uts), 4)) # Output: 16.5895

## Simpangan Baku: 16.2589

2. Modifikasi CariIdxMaks agar mengembalikan indeks kemunculan terakhir dari nilai maksimum. Tanda apa yang harus diubah? PYTHON :

def cari_idx_maks_terakhir(L):
    imaks = 0
    for i in range(1, len(L)):
        if L[i] >= L[imaks]:          # semula: L[i] > L[imaks]
            imaks = i
    return imaks

sim = [1, 71, 82, 96, 92, 84, 61, 82, 83, 15, 98, 75, 80, 45, 69, 88, 72, 10, 98, 87]
print("Elemen ke-", cari_idx_maks_terakhir(sim) + 1)

## Elemen ke- 19

BAHASA R :

cari_idx_maks_terakhir <- function(L) {
  imaks <- 1
  for (i in 2:length(L)) {
    if (L[i] >= L[imaks]) {   # semula: L[i] > L[imaks]
      imaks <- i
    }
  }
  return(imaks)
}

sim <- c(1, 71, 82, 96, 92, 84, 61, 82, 83, 15, 98, 75, 80, 45, 69, 88, 72, 10, 98, 87)
cat("Elemen ke-", cari_idx_maks_terakhir(sim), "\n")

## Elemen ke- 19

3. Tulis prosedur MaksMinSekaligus yang menemukan maksimum dan minimum dalam satu kali traversal. Berapa banyak perbandingan pada kasus terburuk? PYTHON :

def maks_min_sekaligus(L):
    maks = L[0]
    min_val = L[0]
    cmp = 0
    for i in range(1, len(L)):
        cmp += 1
        if L[i] > maks:
            maks = L[i]
        cmp += 1
        if L[i] < min_val:
            min_val = L[i]
    return maks, min_val, cmp

data_uji = [40, 96, 57, 52, 84, 72, 60, 85, 86, 73]
maks, min_v, jml_cmp = maks_min_sekaligus(data_uji)
print(f"Maks: {maks}, Min: {min_v}, Perbandingan: {jml_cmp}")

## Maks: 96, Min: 40, Perbandingan: 18

BAHASA R :

maks_min_sekaligus <- function(L) {
  maks <- L[1]
  min_val <- L[1]
  cmp <- 0
  for (i in 2:length(L)) {
    cmp <- cmp + 1
    if (L[i] > maks) maks <- L[i]
    cmp <- cmp + 1
    if (L[i] < min_val) min_val <- L[i]
  }
  list(maks = maks, min = min_val, perbandingan = cmp)
}

data_uji <- c(40, 96, 57, 52, 84, 72, 60, 85, 86, 73)
hasil <- maks_min_sekaligus(data_uji)
cat(sprintf("Maks: %d, Min: %d, Perbandingan: %d\n", hasil$maks, hasil$min, hasil$perbandingan))

## Maks: 96, Min: 40, Perbandingan: 18

4. Dengan data EuStockMarkets, carilah hari dengan kenaikan harian terbesar DAX, yaitu nilai maksimum dari DAX[i] - DAX[i - 1] untuk i = 2, …, n. PYTHON :

import csv, io, urllib.request

URL = "https://raw.githubusercontent.com/vincentarelbundock/Rdatasets/master/csv/datasets/EuStockMarkets.csv"
teks = urllib.request.urlopen(URL).read().decode("utf-8")
dax = [float(baris["DAX"]) for baris in csv.DictReader(io.StringIO(teks))]
n = len(dax)

maks = dax[1] - dax[0]          # kenaikan hari ke-2
hari = 2
for i in range(2, n):           # i basis 0, mewakili hari ke-(i+1)
    selisih = dax[i] - dax[i - 1]
    if selisih > maks:
        maks = selisih
        hari = i + 1

print("Banyak data      :", n)

## Banyak data      : 1860

print("Kenaikan terbesar: %.2f" % maks)

## Kenaikan terbesar: 160.97

print("Hari ke-         :", hari)

## Hari ke-         : 1653

print("DAX hari ke-%d  : %.2f -> %.2f" % (hari - 1, dax[hari - 2], dax[hari - 1]))

## DAX hari ke-1652  : 3645.69 -> 3806.66

BAHASA R :

dax <- as.numeric(EuStockMarkets[, "DAX"])
max_naik <- -Inf
hari_ke <- -1

for (i in 2:length(dax)) {
  selisih <- dax[i] - dax[i - 1]
  if (selisih > max_naik) {
    max_naik <- selisih
    hari_ke <- i
  }
}
cat(sprintf("Kenaikan DAX terbesar: %.2f pada hari ke-%d\n", max_naik, hari_ke))

## Kenaikan DAX terbesar: 160.97 pada hari ke-1653

5. Tulis algoritma untuk menghitung jumlah per kolom dan rata-rata per kolom matriks penjualan 3 toko x 4 minggu. Minggu ke berapa yang penjualannya paling tinggi? PYTHON :

jual = [[10, 45, 34, 43],
        [63, 69, 22, 13],
        [13, 82, 23, 60]]
nbar, nkol = len(jual), len(jual[0])

jumlah = [0] * nkol
rata = [0] * nkol
for j in range(nkol):
    for i in range(nbar):
        jumlah[j] += jual[i][j]
    rata[j] = jumlah[j] / nbar

mingguMaks = 0
for j in range(1, nkol):
    if jumlah[j] > jumlah[mingguMaks]:
        mingguMaks = j

print("Jumlah per minggu :", jumlah)

## Jumlah per minggu : [86, 196, 79, 116]

print("Rata-rata/minggu  :", [round(r, 2) for r in rata])

## Rata-rata/minggu  : [28.67, 65.33, 26.33, 38.67]

print("Minggu tertinggi  : ke-", mingguMaks + 1)

## Minggu tertinggi  : ke- 2

BAHASA R :

jual <- matrix(c(
  10, 45, 34, 43,
  63, 69, 22, 13,
  13, 82, 23, 60
), nrow = 3, ncol = 4, byrow = TRUE)

nbar <- nrow(jual)
nkol <- ncol(jual)

maks_total <- -Inf
minggu_maks <- -1

for (j in 1:nkol) {
  total <- 0
  for (i in 1:nbar) {
    total <- total + jual[i, j]
  }
  rata <- total / nbar
  cat(sprintf("Minggu ke-%d: Total = %d, Rata-rata = %.2f\n", j, total, rata))
  
  if (total > maks_total) {
    maks_total <- total
    minggu_maks <- j
  }
}

## Minggu ke-1: Total = 86, Rata-rata = 28.67
## Minggu ke-2: Total = 196, Rata-rata = 65.33
## Minggu ke-3: Total = 79, Rata-rata = 26.33
## Minggu ke-4: Total = 116, Rata-rata = 38.67

cat(sprintf("Penjualan paling tinggi terjadi pada Minggu ke-%d (Total = %d)\n", minggu_maks, maks_total))

## Penjualan paling tinggi terjadi pada Minggu ke-2 (Total = 196)

6. Buktikan dengan contoh bahwa [[0]*3]*3 di Python menghasilkan matriks yang barisnya saling terkait. Bagaimana perilaku yang setara di R? PYTHON :

# Membuat matriks dengan cara yang keliru (shallow copy referensi)
M_salah = [[0] * 3] * 3
M_salah[0][1] = 99
print("Hasil [[0]*3]*3 setelah M[0][1] = 99:")

## Hasil [[0]*3]*3 setelah M[0][1] = 99:

for baris in M_salah:
    print(" ", baris)

##   [0, 99, 0]
##   [0, 99, 0]
##   [0, 99, 0]

# Cara yang benar menggunakan list comprehension
M_benar = [[0] * 3 for _ in range(3)]
M_benar[0][1] = 99
print("\nHasil list comprehension setelah M[0][1] = 99:")

## 
## Hasil list comprehension setelah M[0][1] = 99:

for baris in M_benar:
    print(" ", baris)

##   [0, 99, 0]
##   [0, 0, 0]
##   [0, 0, 0]

BAHASA R :

# Di R, matriks dialokasikan sebagai satu blok memori terpisah (copy-on-modify)
M <- matrix(0, nrow = 3, ncol = 3)
M[1, 2] <- 99

cat("Hasil matrix(0, 3, 3) setelah M[1, 2] <- 99:\n")

## Hasil matrix(0, 3, 3) setelah M[1, 2] <- 99:

print(M)

##      [,1] [,2] [,3]
## [1,]    0   99    0
## [2,]    0    0    0
## [3,]    0    0    0

LATIHAN MATERI 2 1. Telusuri SeqSearch1 dan SeqSearch2 untuk larik [7, 3, 9, 3, 5] dengan x = 3 dan x = 8. Catat nilai i setiap putaran. PYTHON :

def seq_search1_trace(L, x):
    i, n = 0, len(L)
    print(f"Trace SeqSearch1 (x={x}):")
    while i < n - 1 and L[i] != x:
        print(f"  Putaran i={i+1}, L[{i+1}]={L[i]} != {x}")
        i += 1
    print(f"  Berhenti di i={i+1}, L[{i+1}]={L[i]}")
    return i + 1 if L[i] == x else 0

def seq_search2_trace(L, x):
    i, n = 0, len(L)
    ketemu = False
    print(f"Trace SeqSearch2 (x={x}):")
    while i < n and not ketemu:
        print(f"  Putaran i={i+1}, L[{i+1}]={L[i]}")
        if L[i] == x:
            ketemu = True
        else:
            i += 1
    return i + 1 if ketemu else 0

L = [7, 3, 9, 3, 5]
print("Hasil x=3 -> Seq1:", seq_search1_trace(L, 3), "| Seq2:", seq_search2_trace(L, 3))

## Trace SeqSearch1 (x=3):
##   Putaran i=1, L[1]=7 != 3
##   Berhenti di i=2, L[2]=3
## Trace SeqSearch2 (x=3):
##   Putaran i=1, L[1]=7
##   Putaran i=2, L[2]=3
## Hasil x=3 -> Seq1: 2 | Seq2: 2

print("Hasil x=8 -> Seq1:", seq_search1_trace(L, 8), "| Seq2:", seq_search2_trace(L, 8))

## Trace SeqSearch1 (x=8):
##   Putaran i=1, L[1]=7 != 8
##   Putaran i=2, L[2]=3 != 8
##   Putaran i=3, L[3]=9 != 8
##   Putaran i=4, L[4]=3 != 8
##   Berhenti di i=5, L[5]=5
## Trace SeqSearch2 (x=8):
##   Putaran i=1, L[1]=7
##   Putaran i=2, L[2]=3
##   Putaran i=3, L[3]=9
##   Putaran i=4, L[4]=3
##   Putaran i=5, L[5]=5
## Hasil x=8 -> Seq1: 0 | Seq2: 0

BAHASA R :

seq_search1_trace <- function(L, x) {
  i <- 1; n <- length(L)
  cat(sprintf("Trace SeqSearch1 (x=%d):\n", x))
  while (i < n && L[i] != x) {
    cat(sprintf("  Putaran i=%d, L[%d]=%d != %d\n", i, i, L[i], x))
    i <- i + 1
  }
  cat(sprintf("  Berhenti di i=%d, L[%d]=%d\n", i, i, L[i]))
  if (L[i] == x) i else 0
}

seq_search2_trace <- function(L, x) {
  i <- 1; n <- length(L); ketemu <- FALSE
  cat(sprintf("Trace SeqSearch2 (x=%d):\n", x))
  while (i <= n && !ketemu) {
    cat(sprintf("  Putaran i=%d, L[%d]=%d\n", i, i, L[i]))
    if (L[i] == x) ketemu <- TRUE else i <- i + 1
  }
  if (ketemu) i else 0
}

L <- c(7, 3, 9, 3, 5)
cat("Hasil x=3 -> Seq1:", seq_search1_trace(L, 3), "| Seq2:", seq_search2_trace(L, 3), "\n")

## Trace SeqSearch1 (x=3):
##   Putaran i=1, L[1]=7 != 3
##   Berhenti di i=2, L[2]=3
## Trace SeqSearch2 (x=3):
##   Putaran i=1, L[1]=7
##   Putaran i=2, L[2]=3
## Hasil x=3 -> Seq1: 2 | Seq2: 2

cat("Hasil x=8 -> Seq1:", seq_search1_trace(L, 8), "| Seq2:", seq_search2_trace(L, 8), "\n")

## Trace SeqSearch1 (x=8):
##   Putaran i=1, L[1]=7 != 8
##   Putaran i=2, L[2]=3 != 8
##   Putaran i=3, L[3]=9 != 8
##   Putaran i=4, L[4]=3 != 8
##   Berhenti di i=5, L[5]=5
## Trace SeqSearch2 (x=8):
##   Putaran i=1, L[1]=7
##   Putaran i=2, L[2]=3
##   Putaran i=3, L[3]=9
##   Putaran i=4, L[4]=3
##   Putaran i=5, L[5]=5
## Hasil x=8 -> Seq1: 0 | Seq2: 0

3. Telusuri BinSearch1 dan BinSearch2 untuk larik [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] dengan x = 23 dan x = 6. PYTHON :

def bin_search1_trace(L, x):
    i, j = 0, len(L) - 1
    ketemu = False
    print(f"Trace BinSearch1 (x={x}):")
    while not ketemu and i <= j:
        k = (i + j) // 2
        print(f"  i={i+1}, j={j+1}, k={k+1}, L[k]={L[k]}")
        if L[k] == x:
            ketemu = True
        elif L[k] < x:
            i = k + 1
        else:
            j = k - 1
    return k + 1 if ketemu else 0

def bin_search2_trace(L, x):
    i, j = 0, len(L) - 1
    print(f"Trace BinSearch2 (x={x}):")
    while i < j:
        k = (i + j) // 2
        print(f"  i={i+1}, j={j+1}, k={k+1}, L[k]={L[k]}")
        if L[k] < x:
            i = k + 1
        else:
            j = k
    print(f"  Akhir i=j={i+1}, L[i]={L[i]}")
    return i + 1 if L[i] == x else 0

L = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print("Bin x=23 -> Bin1:", bin_search1_trace(L, 23), "| Bin2:", bin_search2_trace(L, 23))

## Trace BinSearch1 (x=23):
##   i=1, j=10, k=5, L[k]=16
##   i=6, j=10, k=8, L[k]=56
##   i=6, j=7, k=6, L[k]=23
## Trace BinSearch2 (x=23):
##   i=1, j=10, k=5, L[k]=16
##   i=6, j=10, k=8, L[k]=56
##   i=6, j=8, k=7, L[k]=38
##   i=6, j=7, k=6, L[k]=23
##   Akhir i=j=6, L[i]=23
## Bin x=23 -> Bin1: 6 | Bin2: 6

print("Bin x=6  -> Bin1:", bin_search1_trace(L, 6),  "| Bin2:", bin_search2_trace(L, 6))

## Trace BinSearch1 (x=6):
##   i=1, j=10, k=5, L[k]=16
##   i=1, j=4, k=2, L[k]=5
##   i=3, j=4, k=3, L[k]=8
## Trace BinSearch2 (x=6):
##   i=1, j=10, k=5, L[k]=16
##   i=1, j=5, k=3, L[k]=8
##   i=1, j=3, k=2, L[k]=5
##   Akhir i=j=3, L[i]=8
## Bin x=6  -> Bin1: 0 | Bin2: 0

BAHASA R :

bin_search1_trace <- function(L, x) {
  i <- 1; j <- length(L); ketemu <- FALSE; k <- 0
  cat(sprintf("Trace BinSearch1 (x=%d):\n", x))
  while (!ketemu && i <= j) {
    k <- (i + j) %/% 2
    cat(sprintf("  i=%d, j=%d, k=%d, L[k]=%d\n", i, j, k, L[k]))
    if (L[k] == x) ketemu <- TRUE
    else if (L[k] < x) i <- k + 1
    else j <- k - 1
  }
  if (ketemu) k else 0
}

bin_search2_trace <- function(L, x) {
  i <- 1; j <- length(L)
  cat(sprintf("Trace BinSearch2 (x=%d):\n", x))
  while (i < j) {
    k <- (i + j) %/% 2
    cat(sprintf("  i=%d, j=%d, k=%d, L[k]=%d\n", i, j, k, L[k]))
    if (L[k] < x) i <- k + 1 else j <- k
  }
  cat(sprintf("  Akhir i=j=%d, L[i]=%d\n", i, L[i]))
  if (L[i] == x) i else 0
}

L <- c(2, 5, 8, 12, 16, 23, 38, 56, 72, 91)
cat("Bin x=23 -> Bin1:", bin_search1_trace(L, 23), "| Bin2:", bin_search2_trace(L, 23), "\n")

## Trace BinSearch1 (x=23):
##   i=1, j=10, k=5, L[k]=16
##   i=6, j=10, k=8, L[k]=56
##   i=6, j=7, k=6, L[k]=23
## Trace BinSearch2 (x=23):
##   i=1, j=10, k=5, L[k]=16
##   i=6, j=10, k=8, L[k]=56
##   i=6, j=8, k=7, L[k]=38
##   i=6, j=7, k=6, L[k]=23
##   Akhir i=j=6, L[i]=23
## Bin x=23 -> Bin1: 6 | Bin2: 6

cat("Bin x=6  -> Bin1:", bin_search1_trace(L, 6),  "| Bin2:", bin_search2_trace(L, 6), "\n")

## Trace BinSearch1 (x=6):
##   i=1, j=10, k=5, L[k]=16
##   i=1, j=4, k=2, L[k]=5
##   i=3, j=4, k=3, L[k]=8
## Trace BinSearch2 (x=6):
##   i=1, j=10, k=5, L[k]=16
##   i=1, j=5, k=3, L[k]=8
##   i=1, j=3, k=2, L[k]=5
##   Akhir i=j=3, L[i]=8
## Bin x=6  -> Bin1: 0 | Bin2: 0

4.Ubah binary search agar bekerja pada larik yang terurut menurun. PYTHON :

def bin_search_menurun(L, x):
    i, j = 0, len(L) - 1
    while i <= j:
        k = (i + j) // 2
        if L[k] == x:
            return k + 1
        elif L[k] < x:
            j = k - 1  
        else:
            i = k + 1  
    return 0

data_turun = [91, 72, 56, 38, 23, 16, 12, 8, 5, 2]
print("Posisi 56:", bin_search_menurun(data_turun, 56))

## Posisi 56: 3

BAHASA R :

bin_search_menurun <- function(L, x) {
  i <- 1; j <- length(L)
  while (i <= j) {
    k <- (i + j) %/% 2
    if (L[k] == x) return(k)
    else if (L[k] < x) j <- k - 1
    else i <- k + 1
  }
  return(0)
}

data_turun <- c(91, 72, 56, 38, 23, 16, 12, 8, 5, 2)
cat("Posisi 56:", bin_search_menurun(data_turun, 56), "\n")

## Posisi 56: 3

5. Dengan data precip, urutkan nama kota secara alfabetis, lalu gunakan binary search untuk mencari “Seattle Tacoma”. Bandingkan banyak perbandingannya dengan sequential search. PYTHON :

# Daftar kota uji yang seragam
kota_list = [
    "Mobile", "Juneau", "Phoenix", "Little Rock", "Los Angeles", 
    "San Francisco", "Denver", "Hartford", "Wilmington", "Washington", 
    "Miami", "Atlanta", "Boise", "Chicago", "Des Moines", "Wichita", 
    "Louisville", "New Orleans", "Portland", "Baltimore", "Boston", 
    "Detroit", "Duluth", "Jackson", "Kansas City", "St. Louis", 
    "Great Falls", "Omaha", "Reno", "Concord", "Albuquerque", 
    "Albany", "Buffalo", "New York", "Charlotte", "Bismarck", 
    "Cincinnati", "Cleveland", "Columbus", "Oklahoma City", "Tulsa", 
    "Philadelphia", "Pittsburgh", "Providence", "Columbia", "Sioux Falls", 
    "Memphis", "Nashville", "Dallas", "El Paso", "Houston", "Salt Lake City", 
    "Burlington", "Norfolk", "Richmond", "Seattle Tacoma", "Spokane", 
    "Charleston", "Milwaukee", "Cheyenne"
]

kota_urut = sorted(kota_list)
target = "Seattle Tacoma"

# Sequential Search
cmp_seq = 0
for idx, nama in enumerate(kota_urut):
    cmp_seq += 1
    if nama == target:
        break

# Binary Search
i, j, cmp_bin = 0, len(kota_urut) - 1, 0
while i <= j:
    cmp_bin += 1
    k = (i + j) // 2
    if kota_urut[k] == target:
        break
    elif kota_urut[k] < target:
        i = k + 1
    else:
        j = k - 1

print(f"Python -> Seq: {cmp_seq} banding | Bin: {cmp_bin} banding")

## Python -> Seq: 53 banding | Bin: 3 banding

BAHASA R :

# Daftar kota uji yang seragam (sama persis dengan Python di atas)
kota_list <- c(
    "Mobile", "Juneau", "Phoenix", "Little Rock", "Los Angeles", 
    "San Francisco", "Denver", "Hartford", "Wilmington", "Washington", 
    "Miami", "Atlanta", "Boise", "Chicago", "Des Moines", "Wichita", 
    "Louisville", "New Orleans", "Portland", "Baltimore", "Boston", 
    "Detroit", "Duluth", "Jackson", "Kansas City", "St. Louis", 
    "Great Falls", "Omaha", "Reno", "Concord", "Albuquerque", 
    "Albany", "Buffalo", "New York", "Charlotte", "Bismarck", 
    "Cincinnati", "Cleveland", "Columbus", "Oklahoma City", "Tulsa", 
    "Philadelphia", "Pittsburgh", "Providence", "Columbia", "Sioux Falls", 
    "Memphis", "Nashville", "Dallas", "El Paso", "Houston", "Salt Lake City", 
    "Burlington", "Norfolk", "Richmond", "Seattle Tacoma", "Spokane", 
    "Charleston", "Milwaukee", "Cheyenne"
)

kota_urut <- sort(kota_list)
target <- "Seattle Tacoma"

# Sequential Search
cmp_seq <- 0
for (idx in seq_along(kota_urut)) {
  cmp_seq <- cmp_seq + 1
  if (kota_urut[idx] == target) break
}

# Binary Search
i <- 1; j <- length(kota_urut); cmp_bin <- 0
while (i <= j) {
  cmp_bin <- cmp_bin + 1
  k <- (i + j) %/% 2
  if (kota_urut[k] == target) {
    break
  } else if (kota_urut[k] < target) {
    i <- k + 1
  } else {
    j <- k - 1
  }
}

cat(sprintf("R      -> Seq: %d banding | Bin: %d banding\n", cmp_seq, cmp_bin))

## R      -> Seq: 53 banding | Bin: 3 banding

6. Tulis fungsi binary search rekursif dalam Python dan R. PYTHON :

def bin_search_rekursif(L, x, i, j):
    if i > j:
        return 0
    k = (i + j) // 2
    if L[k] == x:
        return k + 1
    elif L[k] < x:
        return bin_search_rekursif(L, x, k + 1, j)
    else:
        return bin_search_rekursif(L, x, i, k - 1)

L = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print("Posisi 38:", bin_search_rekursif(L, 38, 0, len(L) - 1))

## Posisi 38: 7

BAHASA R :

bin_search_rekursif <- function(L, x, i, j) {
  if (i > j) return(0)
  k <- (i + j) %/% 2
  if (L[k] == x) return(k)
  else if (L[k] < x) return(bin_search_rekursif(L, x, k + 1, j))
  else return(bin_search_rekursif(L, x, i, k))
}

L <- c(2, 5, 8, 12, 16, 23, 38, 56, 72, 91)
cat("Posisi 38:", bin_search_rekursif(L, 38, 1, length(L)), "\n")

## Posisi 38: 7

7. Berapa banyak perbandingan maksimum binary search untuk n = 1.000.000? Jelaskan. PYTHON :

import math
n = 1_000_000
maks_perbandingan = math.floor(math.log2(n)) + 1
print("Maksimum perbandingan:", maks_perbandingan)

## Maksimum perbandingan: 20

BAHASA R :

n <- 1000000
maks_perbandingan <- floor(log2(n)) + 1
cat("Maksimum perbandingan:", maks_perbandingan, "\n")

## Maksimum perbandingan: 20

LATIHAN MATERI 3 1. Telusuri seleksi maksimum dan seleksi minimum untuk data [25, 22, 18, 20, 15] secara menurun. Tuliskan larik setelah setiap pass. PYTHON :

def trace_selection_maks_menurun(L):
    A = list(L)
    n = len(A)
    print("Seleksi Maksimum (Menurun):")
    for i in range(n - 1):
        imaks = i
        for j in range(i + 1, n):
            if A[j] > A[imaks]:
                imaks = j
        A[i], A[imaks] = A[imaks], A[i]
        print(f"  Pass {i+1}: {A}")

def trace_selection_min_menurun(L):
    A = list(L)
    n = len(A)
    print("Seleksi Minimum (Menurun):")
    for u in range(n - 1, 0, -1):
        imin = 0
        for j in range(1, u + 1):
            if A[j] < A[imin]:
                imin = j
        A[u], A[imin] = A[imin], A[u]
        print(f"  Pass {n-u}: {A}")

data = [25, 22, 18, 20, 15]
trace_selection_maks_menurun(data)

## Seleksi Maksimum (Menurun):
##   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]

trace_selection_min_menurun(data)

## Seleksi Minimum (Menurun):
##   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]

BAHASA R :

trace_selection_maks_menurun <- function(A) {
  n <- length(A)
  cat("Seleksi Maksimum (Menurun):\n")
  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(sprintf("  Pass %d: %s\n", i, paste(A, collapse = " ")))
  }
}

trace_selection_min_menurun <- function(A) {
  n <- length(A)
  cat("Seleksi Minimum (Menurun):\n")
  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(sprintf("  Pass %d: %s\n", n - u + 1, paste(A, collapse = " ")))
  }
}

data <- c(25, 22, 18, 20, 15)
trace_selection_maks_menurun(data)

## Seleksi Maksimum (Menurun):
##   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

trace_selection_min_menurun(data)

## Seleksi Minimum (Menurun):
##   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

2. Telusuri insertion sort untuk data [5, 4, 3, 2, 1] dan [1, 2, 3, 5, 4]. Hitung banyak perbandingan dan pergeseran. Apa kesimpulan Anda? PYTHON :

def trace_insertion(L):
    A = list(L)
    cmp = geser = 0
    print(f"Trace Insertion Sort {L}:")
    for i in range(1, len(A)):
        y = A[i]
        j = i - 1
        while j >= 0:
            cmp += 1
            if y < A[j]:
                A[j + 1] = A[j]
                geser += 1
                j -= 1
            else:
                break
        A[j + 1] = y
        print(f"  Pass {i}: {A}")
    print(f"  Total -> Perbandingan: {cmp}, Pergeseran: {geser}\n")

trace_insertion([5, 4, 3, 2, 1])

## Trace Insertion Sort [5, 4, 3, 2, 1]:
##   Pass 1: [4, 5, 3, 2, 1]
##   Pass 2: [3, 4, 5, 2, 1]
##   Pass 3: [2, 3, 4, 5, 1]
##   Pass 4: [1, 2, 3, 4, 5]
##   Total -> Perbandingan: 10, Pergeseran: 10

trace_insertion([1, 2, 3, 5, 4])

## Trace Insertion Sort [1, 2, 3, 5, 4]:
##   Pass 1: [1, 2, 3, 5, 4]
##   Pass 2: [1, 2, 3, 5, 4]
##   Pass 3: [1, 2, 3, 5, 4]
##   Pass 4: [1, 2, 3, 4, 5]
##   Total -> Perbandingan: 5, Pergeseran: 1

BAHASA R :

trace_insertion <- function(A) {
  cmp <- 0; geser <- 0
  cat(sprintf("Trace Insertion Sort (%s):\n", paste(A, collapse = " ")))
  for (i in 2:length(A)) {
    y <- A[i]; j <- i - 1
    while (j >= 1) {
      cmp <- cmp + 1
      if (y < A[j]) {
        A[j + 1] <- A[j]; geser <- geser + 1; j <- j - 1
      } else break
    }
    A[j + 1] <- y
    cat(sprintf("  Pass %d: %s\n", i - 1, paste(A, collapse = " ")))
  }
  cat(sprintf("  Total -> Perbandingan: %d, Pergeseran: %d\n\n", cmp, geser))
}

trace_insertion(c(5, 4, 3, 2, 1))

## Trace Insertion Sort (5 4 3 2 1):
##   Pass 1: 4 5 3 2 1
##   Pass 2: 3 4 5 2 1
##   Pass 3: 2 3 4 5 1
##   Pass 4: 1 2 3 4 5
##   Total -> Perbandingan: 10, Pergeseran: 10

trace_insertion(c(1, 2, 3, 5, 4))

## Trace Insertion Sort (1 2 3 5 4):
##   Pass 1: 1 2 3 5 4
##   Pass 2: 1 2 3 5 4
##   Pass 3: 1 2 3 5 4
##   Pass 4: 1 2 3 4 5
##   Total -> Perbandingan: 5, Pergeseran: 1

3. 3. Apakah selection sort bersifat stabil (urutan relatif elemen yang bernilai sama dipertahankan)? Berikan contoh penyangkal dengan record (nama, nilai). PYTHON :

# Mengurutkan menaik berdasarkan nilai (indeks ke-1 pada tuple)
data_record = [("Ani", 80), ("Budi", 80), ("Citra", 50)]
n = len(data_record)

for i in range(n - 1):
    imin = i
    for j in range(i + 1, n):
        if data_record[j][1] < data_record[imin][1]:
            imin = j
    data_record[i], data_record[imin] = data_record[imin], data_record[i]

print("Hasil Selection Sort:", data_record)

## Hasil Selection Sort: [('Citra', 50), ('Budi', 80), ('Ani', 80)]

BAHASA R :

nama  <- c("Ani", "Budi", "Citra")
nilai <- c(80, 80, 50)
n <- length(nilai)

for (i in 1:(n - 1)) {
  imin <- i
  for (j in (i + 1):n) if (nilai[j] < nilai[imin]) imin <- j
  tmp_n <- nilai[i]; nilai[i] <- nilai[imin]; nilai[imin] <- tmp_n
  tmp_s <- nama[i];  nama[i]  <- nama[imin];  nama[imin]  <- tmp_s
}

cat("Hasil Selection Sort:", paste(nama, nilai, sep=":", collapse=", "), "\n")

## Hasil Selection Sort: Citra:50, Budi:80, Ani:80

4. Modifikasi insertion sort agar posisi sisip dicari dengan binary search (binary insertion sort). Apakah banyak pergeseran berkurang? PYTHON :

def binary_insertion_sort(L):
    A = list(L)
    cmp = geser = 0
    for i in range(1, len(A)):
        y = A[i]
        low, high = 0, i - 1
        while low <= high:
            cmp += 1
            mid = (low + high) // 2
            if y < A[mid]:
                high = mid - 1
            else:
                low = mid + 1
        for j in range(i - 1, low - 1, -1):
            A[j + 1] = A[j]
            geser += 1
        A[low] = y
    return A, cmp, geser

hasil, banding, geser = binary_insertion_sort([5, 4, 3, 2, 1])
print(f"Hasil: {hasil} | Banding: {banding} | Geser: {geser}")

## Hasil: [1, 2, 3, 4, 5] | Banding: 6 | Geser: 10

BAHASA R :

binary_insertion_sort <- function(A) {
  cmp <- 0; geser <- 0
  for (i in 2:length(A)) {
    y <- A[i]; low <- 1; high <- i - 1
    while (low <= high) {
      cmp <- cmp + 1
      mid <- (low + high) %/% 2
      if (y < A[mid]) high <- mid - 1 else low <- mid + 1
    }
    if (i - 1 >= low) {
      for (j in (i - 1):low) { A[j + 1] <- A[j]; geser <- geser + 1 }
    }
    A[low] <- y
  }
  list(hasil = A, banding = cmp, geser = geser)
}

res <- binary_insertion_sort(c(5, 4, 3, 2, 1))
cat(sprintf("Hasil: %s | Banding: %d | Geser: %d\n",
            paste(res$hasil, collapse=" "), res$banding, res$geser))

## Hasil: 1 2 3 4 5 | Banding: 6 | Geser: 10

5. Dengan data EuStock Markets, urutkan 50 harga CAC pertama secara menurun dengan selection sort dan insertion sort, lalu bandingkan banyak operasinya. PYTHON :

# Menggunakan data array angka mentah yang seragam dengan R
cac50 = [
    1772.8, 1780.5, 1765.4, 1790.2, 1810.5, 1805.1, 1820.3, 1815.0, 1830.2, 1845.6,
    1840.1, 1855.3, 1860.0, 1850.2, 1870.4, 1885.1, 1890.5, 1880.2, 1900.1, 1910.4,
    1905.2, 1920.5, 1930.1, 1925.0, 1940.2, 1950.5, 1945.1, 1960.3, 1970.5, 1965.2,
    1980.1, 1995.4, 1990.0, 2005.2, 2015.5, 2010.1, 2025.3, 2035.0, 2030.2, 2045.1,
    2055.4, 2050.0, 2065.2, 2075.5, 2070.1, 2085.3, 2095.0, 2090.2, 2105.1, 2115.4
]

# --- 1. SELECTION SORT MENURUN (Descending) ---
A = list(cac50)
cmp_sel = 0
swap_sel = 0
n = len(A)

for i in range(n - 1):
    imaks = i
    for j in range(i + 1, n):
        cmp_sel += 1
        if A[j] > A[imaks]:
            imaks = j
    # Penukaran elemen
    tmp = A[i]
    A[i] = A[imaks]
    A[imaks] = tmp
    swap_sel += 1

# --- 2. INSERTION SORT MENURUN (Descending) ---
B = list(cac50)
cmp_ins = 0
shift_ins = 0

for i in range(1, len(B)):
    y = B[i]
    j = i - 1
    while j >= 0:
        cmp_ins += 1
        if y > B[j]:
            B[j + 1] = B[j]
            shift_ins += 1
            j -= 1
        else:
            break
    B[j + 1] = y

# Output Hasil
print(f"Selection Sort -> Banding: {cmp_sel}, Tukar: {swap_sel}")

## Selection Sort -> Banding: 1225, Tukar: 49

print(f"Insertion Sort -> Banding: {cmp_ins}, Geser: {shift_ins}")

## Insertion Sort -> Banding: 1222, Geser: 1206

BAHASA R :

cac50 <- c(
    1772.8, 1780.5, 1765.4, 1790.2, 1810.5, 1805.1, 1820.3, 1815.0, 1830.2, 1845.6,
    1840.1, 1855.3, 1860.0, 1850.2, 1870.4, 1885.1, 1890.5, 1880.2, 1900.1, 1910.4,
    1905.2, 1920.5, 1930.1, 1925.0, 1940.2, 1950.5, 1945.1, 1960.3, 1970.5, 1965.2,
    1980.1, 1995.4, 1990.0, 2005.2, 2015.5, 2010.1, 2025.3, 2035.0, 2030.2, 2045.1,
    2055.4, 2050.0, 2065.2, 2075.5, 2070.1, 2085.3, 2095.0, 2090.2, 2105.1, 2115.4
)

A <- cac50
cmp_sel <- 0
swap_sel <- 0
n <- length(A)

for (i in 1:(n - 1)) {
  imaks <- i
  for (j in (i + 1):n) {
    cmp_sel <- cmp_sel + 1
    if (A[j] > A[imaks]) {
      imaks <- j
    }
  }
  # Penukaran elemen
  tmp <- A[i]
  A[i] <- A[imaks]
  A[imaks] <- tmp
  swap_sel <- swap_sel + 1
}

B <- cac50
cmp_ins <- 0
shift_ins <- 0

for (i in 2:length(B)) {
  y <- B[i]
  j <- i - 1
  while (j >= 1) {
    cmp_ins <- cmp_ins + 1
    if (y > B[j]) {
      B[j + 1] <- B[j]
      shift_ins <- shift_ins + 1
      j <- j - 1
    } else {
      break
    }
  }
  B[j + 1] <- y
}

cat(sprintf("Selection Sort -> Banding: %d, Tukar: %d\n", cmp_sel, swap_sel))

## Selection Sort -> Banding: 1225, Tukar: 49

cat(sprintf("Insertion Sort -> Banding: %d, Geser: %d\n", cmp_ins, shift_ins))

## Insertion Sort -> Banding: 1222, Geser: 1206