Tugas Alpro

##1.

import math

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 math.sqrt(jumlah_kuadrat / (n - 1))

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

## Simpangan Baku: 16.2589

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
  return(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")

## Simpangan Baku: 16.2589

##2.

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

L_uji = [10, 50, 30, 50, 20]
print("Indeks maks terakhir:", idx_maks_terakhir(L_uji)) # Output: 3 (indeks ke-4)

## Indeks maks terakhir: 3

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

L_uji <- c(10, 50, 30, 50, 20)
cat("Indeks maks terakhir:", idx_maks_terakhir(L_uji), "\n")

## Indeks maks terakhir: 4

##3.

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

L_uji = [5, 1, 9, 2, 8]
maks, min_val = maks_min_sekaligus(L_uji)
print("Maks:", maks, "| Min:", min_val)

## Maks: 9 | Min: 1

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

print(maks_min_sekaligus(c(5, 1, 9, 2, 8)))

## $maks
## [1] 9
## 
## $min
## [1] 1

##4.

def kenaikan_dax(L):
    imaks = 1
    maks_naik = L[1] - L[0]
    for i in range(1, len(L)):
        naik = L[i] - L[i-1]
        if naik > maks_naik:
            maks_naik = naik
            imaks = i
    return imaks + 1, maks_naik # +1 untuk hari ke- (1-based)

dax = [1600, 1610, 1605, 1630, 1620] 
hari, naik = kenaikan_dax(dax)
print(f"Kenaikan terbesar: {naik} pada hari ke-{hari}")

## Kenaikan terbesar: 25 pada hari ke-4

kenaikan_dax <- function(L) {
  imaks <- 2
  maks_naik <- L[2] - L[1]
  for (i in 2:length(L)) {
    naik <- L[i] - L[i-1]
    if (naik > maks_naik) { 
      maks_naik <- naik
      imaks <- i 
    }
  }
  return(list(hari = imaks, naik = maks_naik))
}

dax <- c(1600, 1610, 1605, 1630, 1620)
print(kenaikan_dax(dax))

## $hari
## [1] 4
## 
## $naik
## [1] 25

##5.

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

for j in range(nkol):
    for i in range(nbar): 
        total_kolom[j] += jual[i][j]
    print(f"Minggu {j+1}: Total={total_kolom[j]}, Rata2={total_kolom[j]/nbar:.2f}")

## Minggu 1: Total=86, Rata2=28.67
## Minggu 2: Total=196, Rata2=65.33
## Minggu 3: Total=79, Rata2=26.33
## Minggu 4: Total=116, Rata2=38.67

maks_minggu = 0
for j in range(1, nkol):
    if total_kolom[j] > total_kolom[maks_minggu]: 
        maks_minggu = j
print(f"Penjualan tertinggi: Minggu ke-{maks_minggu+1}")

## Penjualan tertinggi: Minggu ke-2

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

for (j in 1:nkol) {
  for (i in 1:nbar) total_kolom[j] <- total_kolom[j] + jual[i, j]
  cat(sprintf("Minggu %d: Total=%d, Rata2=%.2f\n", j, total_kolom[j], total_kolom[j]/nbar))
}

## Minggu 1: Total=86, Rata2=28.67
## Minggu 2: Total=196, Rata2=65.33
## Minggu 3: Total=79, Rata2=26.33
## Minggu 4: Total=116, Rata2=38.67

maks_minggu <- 1
for (j in 2:nkol) {
  if (total_kolom[j] > total_kolom[maks_minggu]) maks_minggu <- j
}
cat("Penjualan tertinggi: Minggu ke-", maks_minggu, "\n")

## Penjualan tertinggi: Minggu ke- 2

##6.

mat_salah = [[0]*3] * 3
mat_salah[0][0] = 99
print("Salah:", mat_salah) 

## Salah: [[99, 0, 0], [99, 0, 0], [99, 0, 0]]

mat_benar = [[0]*3 for _ in range(3)]
mat_benar[0][0] = 99
print("Benar:", mat_benar) 

## Benar: [[99, 0, 0], [0, 0, 0], [0, 0, 0]]

mat_benar <- matrix(0, 3, 3)
mat_benar[1,1] <- 99
print(mat_benar) 

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

Latihan 2 ##1.

def seq_search_1(L, x):
    for i in range(len(L)):
        print(f"  SeqSearch1: cek i={i+1}, L[{i+1}]={L[i]}")
        if L[i] == x: return i + 1
    return -1

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

L = [7, 3, 9, 3, 5]
print("Cari 3:")

## Cari 3:

print("Hasil 1:", seq_search_1(L, 3))

##   SeqSearch1: cek i=1, L[1]=7
##   SeqSearch1: cek i=2, L[2]=3
## Hasil 1: 2

print("Hasil 2:", seq_search_2(L, 3))

##   SeqSearch2: cek i=1, L[1]=7
##   SeqSearch2: cek i=2, L[2]=3
## Hasil 2: 2

print("\nCari 8:")

## 
## Cari 8:

print("Hasil 1:", seq_search_1(L, 8))

##   SeqSearch1: cek i=1, L[1]=7
##   SeqSearch1: cek i=2, L[2]=3
##   SeqSearch1: cek i=3, L[3]=9
##   SeqSearch1: cek i=4, L[4]=3
##   SeqSearch1: cek i=5, L[5]=5
## Hasil 1: -1

print("Hasil 2:", seq_search_2(L, 8))

##   SeqSearch2: cek i=1, L[1]=7
##   SeqSearch2: cek i=2, L[2]=3
##   SeqSearch2: cek i=3, L[3]=9
##   SeqSearch2: cek i=4, L[4]=3
##   SeqSearch2: cek i=5, L[5]=5
## Hasil 2: -1

seq_search_1 <- function(L, x) {
  for (i in 1:length(L)) {
    cat(sprintf("  SeqSearch1: cek i=%d, L[%d]=%d\n", i, i, L[i]))
    if (L[i] == x) return(i)
  }
  return(0)
}

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

L <- c(7, 3, 9, 3, 5)
cat("Cari 3:\n")

## Cari 3:

cat("Hasil 1:", seq_search_1(L, 3), "\n")

##   SeqSearch1: cek i=1, L[1]=7
##   SeqSearch1: cek i=2, L[2]=3
## Hasil 1: 2

cat("Hasil 2:", seq_search_2(L, 3), "\n\n")

##   SeqSearch2: cek i=1, L[1]=7
##   SeqSearch2: cek i=2, L[2]=3
## Hasil 2: 2

cat("Cari 8:\n")

## Cari 8:

cat("Hasil 1:", seq_search_1(L, 8), "\n")

##   SeqSearch1: cek i=1, L[1]=7
##   SeqSearch1: cek i=2, L[2]=3
##   SeqSearch1: cek i=3, L[3]=9
##   SeqSearch1: cek i=4, L[4]=3
##   SeqSearch1: cek i=5, L[5]=5
## Hasil 1: 0

cat("Hasil 2:", seq_search_2(L, 8), "\n")

##   SeqSearch2: cek i=1, L[1]=7
##   SeqSearch2: cek i=2, L[2]=3
##   SeqSearch2: cek i=3, L[3]=9
##   SeqSearch2: cek i=4, L[4]=3
##   SeqSearch2: cek i=5, L[5]=5
## Hasil 2: 0

##2.

def demo_tanpa_short_circuit(L, x):
    i = 0
    while True:
        # Memaksa evaluasi logika AND tanpa memedulikan short-circuit
        # Jika i sudah melewati batas, L[i] akan memicu IndexError
        if not (i < len(L) and L[i] != x):
            break
        i += 1
    return i if i < len(L) else -1

print(demo_tanpa_short_circuit([1, 2, 3], 5))

## -1

demo_tanpa_short <- function(L, x) {
  i <- 1
  repeat {
    if (!(i <= length(L) && L[i] != x)) break
    i <- i + 1
  }
  if (i <= length(L)) return(i) else return(0)
}
print(demo_tanpa_short(c(1, 2, 3), 5)) 

## [1] 0

##3.

def bin_search_1(L, x):
    low, high = 0, len(L) - 1
    while low <= high:
        mid = (low + high) // 2
        print(f"  low={low+1}, high={high+1}, mid={mid+1}, L[mid]={L[mid]}")
        if L[mid] == x: return mid + 1
        elif L[mid] < x: low = mid + 1
        else: high = mid - 1
    return -1

def bin_search_2(L, x):
    low, high = 0, len(L) - 1
    ketemu = False
    mid = 0 # Inisialisasi awal
    while low <= high and not ketemu:
        mid = (low + high) // 2
        print(f"  low={low+1}, high={high+1}, mid={mid+1}, L[mid]={L[mid]}")
        if L[mid] == x: ketemu = True
        elif L[mid] < x: low = mid + 1
        else: high = mid - 1
    return (mid + 1) if ketemu else -1

L = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print("Cari 23:")

## Cari 23:

print("Hasil 1:", bin_search_1(L, 23))

##   low=1, high=10, mid=5, L[mid]=16
##   low=6, high=10, mid=8, L[mid]=56
##   low=6, high=7, mid=6, L[mid]=23
## Hasil 1: 6

print("Hasil 2:", bin_search_2(L, 23))

##   low=1, high=10, mid=5, L[mid]=16
##   low=6, high=10, mid=8, L[mid]=56
##   low=6, high=7, mid=6, L[mid]=23
## Hasil 2: 6

print("\nCari 6:")

## 
## Cari 6:

print("Hasil 1:", bin_search_1(L, 6))

##   low=1, high=10, mid=5, L[mid]=16
##   low=1, high=4, mid=2, L[mid]=5
##   low=3, high=4, mid=3, L[mid]=8
## Hasil 1: -1

print("Hasil 2:", bin_search_2(L, 6))

##   low=1, high=10, mid=5, L[mid]=16
##   low=1, high=4, mid=2, L[mid]=5
##   low=3, high=4, mid=3, L[mid]=8
## Hasil 2: -1

bin_search_1 <- function(L, x) {
  low <- 1
  high <- length(L)
  while (low <= high) {
    mid <- floor((low + high) / 2)
    cat(sprintf("  low=%d, high=%d, mid=%d, L[mid]=%d\n", low, high, mid, L[mid]))
    if (L[mid] == x) return(mid)
    else if (L[mid] < x) low <- mid + 1
    else high <- mid - 1
  }
  return(0)
}

bin_search_2 <- function(L, x) {
  low <- 1
  high <- length(L)
  ketemu <- FALSE
  mid <- 0
  while (low <= high && !ketemu) {
    mid <- floor((low + high) / 2)
    cat(sprintf("  low=%d, high=%d, mid=%d, L[mid]=%d\n", low, high, mid, L[mid]))
    if (L[mid] == x) ketemu <- TRUE
    else if (L[mid] < x) low <- mid + 1
    else high <- mid - 1
  }
  if (ketemu) return(mid) else return(0)
}

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

## Cari 23:

cat("Hasil 1:", bin_search_1(L, 23), "\n")

##   low=1, high=10, mid=5, L[mid]=16
##   low=6, high=10, mid=8, L[mid]=56
##   low=6, high=7, mid=6, L[mid]=23
## Hasil 1: 6

cat("Hasil 2:", bin_search_2(L, 23), "\n")

##   low=1, high=10, mid=5, L[mid]=16
##   low=6, high=10, mid=8, L[mid]=56
##   low=6, high=7, mid=6, L[mid]=23
## Hasil 2: 6

cat("\nCari 6:\n")

## 
## Cari 6:

cat("Hasil 1:", bin_search_1(L, 6), "\n")

##   low=1, high=10, mid=5, L[mid]=16
##   low=1, high=4, mid=2, L[mid]=5
##   low=3, high=4, mid=3, L[mid]=8
## Hasil 1: 0

cat("Hasil 2:", bin_search_2(L, 6), "\n")

##   low=1, high=10, mid=5, L[mid]=16
##   low=1, high=4, mid=2, L[mid]=5
##   low=3, high=4, mid=3, L[mid]=8
## Hasil 2: 0

##4.

def bin_search_menurun(L, x):
    low, high = 0, len(L) - 1
    while low <= high:
        mid = (low + high) // 2
        if L[mid] == x: return mid + 1
        elif L[mid] > x: low = mid + 1 # Tanda dibalik
        else: high = mid - 1
    return -1

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

## Cari 16: 6

bin_search_menurun <- function(L, x) {
  low <- 1
  high <- length(L)
  while (low <= high) {
    mid <- floor((low + high) / 2)
    if (L[mid] == x) return(mid)
    else if (L[mid] > x) low <- mid + 1 # Tanda dibalik
    else high <- mid - 1
  }
  return(0)
}
L_turun <- c(91, 72, 56, 38, 23, 16, 12, 8, 5, 2)
cat("Cari 16:", bin_search_menurun(L_turun, 16), "\n")

## Cari 16: 6

##5.

# Simulasi data kota (kita urutkan dulu secara manual pakai Bubble Sort)
kota = ["Mobile", "Juneau", "Phoenix", "Little Rock", "Los Angeles"]
kota_terurut = list(kota)

# Pengurutan manual
n = len(kota_terurut)
for i in range(n - 1):
    for j in range(n - 1 - i):
        if kota_terurut[j] > kota_terurut[j+1]:
            kota_terurut[j], kota_terurut[j+1] = kota_terurut[j+1], kota_terurut[j]

# Binary search string
def bin_search_string(L, x):
    low, high = 0, len(L) - 1
    while low <= high:
        mid = (low + high) // 2
        if L[mid] == x: return mid + 1
        elif L[mid] < x: low = mid + 1
        else: high = mid - 1
    return -1

print("Kota terurut:", kota_terurut)

## Kota terurut: ['Juneau', 'Little Rock', 'Los Angeles', 'Mobile', 'Phoenix']

print("Cari Seattle Tacoma:", bin_search_string(kota_terurut, "Seattle Tacoma"))

## Cari Seattle Tacoma: -1

kota <- c("Mobile", "Juneau", "Phoenix", "Little Rock", "Los Angeles")
kota_terurut <- kota

# Pengurutan manual
n <- length(kota_terurut)
for (i in 1:(n-1)) {
  for (j in 1:(n-i)) {
    if (kota_terurut[j] > kota_terurut[j+1]) {
      tmp <- kota_terurut[j]
      kota_terurut[j] <- kota_terurut[j+1]
      kota_terurut[j+1] <- tmp
    }
  }
}

bin_search_string <- function(L, x) {
  low <- 1
  high <- length(L)
  while (low <= high) {
    mid <- floor((low + high) / 2)
    if (L[mid] == x) return(mid)
    else if (L[mid] < x) low <- mid + 1
    else high <- mid - 1
  }
  return(0)
}

cat("Kota terurut:", kota_terurut, "\n")

## Kota terurut: Juneau Little Rock Los Angeles Mobile Phoenix

cat("Cari Seattle Tacoma:", bin_search_string(kota_terurut, "Seattle Tacoma"), "\n")

## Cari Seattle Tacoma: 0

##6.

def bin_search_rek(L, x, low, high):
    if low > high: return -1
    mid = (low + high) // 2
    if L[mid] == x: return mid + 1
    elif L[mid] > x: return bin_search_rek(L, x, low, mid - 1)
    else: return bin_search_rek(L, x, mid + 1, high)

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

## Cari 38: 7

bin_search_rek <- function(L, x, low, high) {
  if (low > high) return(0)
  mid <- floor((low + high) / 2)
  if (L[mid] == x) return(mid)
  else if (L[mid] > x) return(bin_search_rek(L, x, low, mid - 1))
  else return(bin_search_rek(L, x, mid + 1, high))
}
L <- c(2, 5, 8, 12, 16, 23, 38, 56, 72, 91)
cat("Cari 38:", bin_search_rek(L, 38, 1, length(L)), "\n")

## Cari 38: 7

##7.

import math
n = 1000000
maks_perbandingan = math.floor(math.log2(n)) + 1
print(f"Maksimal perbandingan: {maks_perbandingan}")

## Maksimal perbandingan: 20

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

## Maksimal perbandingan: 20

##Latihan 3 ##1.

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

cetak_selection_sort_menurun([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]

cetak_selection_sort_menurun <- function(L) {
  n <- length(L)
  for (i in 1:(n-1)) {
    imaks <- i
    for (j in (i+1):n) {
      if (L[j] > L[imaks]) imaks <- j
    }
    tmp <- L[i]
    L[i] <- L[imaks]
    L[imaks] <- tmp
    cat("Pass", i, ":", L, "\n")
  }
}
cetak_selection_sort_menurun(c(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

##2.

def cetak_insertion_sort(L):
    banding = 0
    geser = 0
    for i in range(1, len(L)):
        kunci = L[i]
        j = i - 1
        while j >= 0:
            banding += 1
            if L[j] > kunci:
                L[j + 1] = L[j]
                geser += 1
                j -= 1
            else:
                break
        L[j + 1] = kunci
        print(f"i={i}: {L}")
    print(f"Total: {banding} perbandingan, {geser} pergeseran")

print("Data [5, 4, 3, 2, 1]:")

## Data [5, 4, 3, 2, 1]:

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

## i=1: [4, 5, 3, 2, 1]
## i=2: [3, 4, 5, 2, 1]
## i=3: [2, 3, 4, 5, 1]
## i=4: [1, 2, 3, 4, 5]
## Total: 10 perbandingan, 10 pergeseran

print("\nData [1, 2, 3, 5, 4]:")

## 
## Data [1, 2, 3, 5, 4]:

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

## i=1: [1, 2, 3, 5, 4]
## i=2: [1, 2, 3, 5, 4]
## i=3: [1, 2, 3, 5, 4]
## i=4: [1, 2, 3, 4, 5]
## Total: 5 perbandingan, 1 pergeseran

cetak_insertion_sort <- function(L) {
  banding <- 0
  geser <- 0
  for (i in 2:length(L)) {
    kunci <- L[i]
    j <- i - 1
    while (j >= 1) {
      banding <- banding + 1
      if (L[j] > kunci) { 
        L[j + 1] <- L[j]
        geser <- geser + 1
        j <- j - 1 
      } else {
        break
      }
    }
    L[j + 1] <- kunci
    cat("i =", i, ":", L, "\n")
  }
  cat("Total:", banding, "perbandingan,", geser, "pergeseran\n")
}

cat("Data [5, 4, 3, 2, 1]:\n")

## Data [5, 4, 3, 2, 1]:

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

## i = 2 : 4 5 3 2 1 
## i = 3 : 3 4 5 2 1 
## i = 4 : 2 3 4 5 1 
## i = 5 : 1 2 3 4 5 
## Total: 10 perbandingan, 10 pergeseran

cat("\nData [1, 2, 3, 5, 4]:\n")

## 
## Data [1, 2, 3, 5, 4]:

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

## i = 2 : 1 2 3 5 4 
## i = 3 : 1 2 3 5 4 
## i = 4 : 1 2 3 5 4 
## i = 5 : 1 2 3 4 5 
## Total: 5 perbandingan, 1 pergeseran

##3.

def selection_sort_record(L):
    n = len(L)
    for i in range(n - 1):
        imin = i
        for j in range(i + 1, n):
            if L[j][1] < L[imin][1]: # Bandingkan nilai (indeks ke-1)
                imin = j
        L[i], L[imin] = L[imin], L[i]
    return L

data = [("A", 80), ("B", 90), ("C", 80)]
print("Sebelum:", data)

## Sebelum: [('A', 80), ('B', 90), ('C', 80)]

print("Sesudah:", selection_sort_record(data))

## Sesudah: [('A', 80), ('C', 80), ('B', 90)]

selection_sort_record <- function(L) {
  n <- length(L)
  for (i in 1:(n-1)) {
    imin <- i
    for (j in (i+1):n) {
      if (L[[j]][2] < L[[imin]][2]) imin <- j
    }
    tmp <- L[[i]]
    L[[i]] <- L[[imin]]
    L[[imin]] <- tmp
  }
  return(L)
}

data <- list(c("A", "80"), c("B", "90"), c("C", "80"))
print(selection_sort_record(data))

## [[1]]
## [1] "A"  "80"
## 
## [[2]]
## [1] "C"  "80"
## 
## [[3]]
## [1] "B"  "90"

##4.

def binary_insertion_sort(L):
    L = list(L)
    banding = 0
    geser = 0
    for i in range(1, len(L)):
        kunci = L[i]
        low = 0
        high = i - 1
        
        # Binary search untuk mencari indeks sisip
        while low <= high:
            mid = (low + high) // 2
            banding += 1
            if L[mid] > kunci: 
                high = mid - 1
            else: 
                low = mid + 1
                
        # Geser elemen
        for j in range(i, low, -1):
            L[j] = L[j - 1]
            geser += 1
        L[low] = kunci
        
    return L, banding, geser

L, b, g = binary_insertion_sort([5, 4, 3, 2, 1])
print(f"Hasil: {L}, Banding: {b}, Geser: {g}")

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

binary_insertion_sort <- function(L) {
  banding <- 0
  geser <- 0
  for (i in 2:length(L)) {
    kunci <- L[i]
    low <- 1
    high <- i - 1
    
    # Binary search
    while (low <= high) {
      mid <- floor((low + high) / 2)
      banding <- banding + 1
      if (L[mid] > kunci) {
        high <- mid - 1
      } else {
        low <- mid + 1
      }
    }
    
    # Geser elemen (jika posisi low < i)
    if (low < i) {
      for (j in i:(low+1)) {
        L[j] <- L[j - 1]
        geser <- geser + 1
      }
    }
    L[low] <- kunci
  }
  return(list(L = L, banding = banding, geser = geser))
}

res <- binary_insertion_sort(c(5, 4, 3, 2, 1))
cat("Hasil:", res$L, "| Banding:", res$banding, "| Geser:", res$geser, "\n")

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

##5.

import random

# Simulasi 50 data CAC
random.seed(42) 
cac = [random.randint(2000, 4000) for _ in range(50)]

def hitung_selection(L):
    L = list(L)
    n = len(L)
    banding = 0
    tukar = 0
    for i in range(n - 1):
        imin = i
        for j in range(i + 1, n):
            banding += 1
            if L[j] < L[imin]: imin = j
        if imin != i: 
            L[i], L[imin] = L[imin], L[i]
            tukar += 1
    return banding, tukar

def hitung_insertion(L):
    L = list(L)
    banding = 0
    geser = 0
    for i in range(1, len(L)):
        kunci = L[i]
        j = i - 1
        while j >= 0:
            banding += 1
            if L[j] > kunci: 
                L[j + 1] = L[j]
                geser += 1
                j -= 1
            else: 
                break
        L[j + 1] = kunci
    return banding, geser

bs, ts = hitung_selection(cac)
bi, gi = hitung_insertion(cac)
print(f"Selection Sort -> Banding: {bs}, Tukar: {ts}")

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

print(f"Insertion Sort -> Banding: {bi}, Geser: {gi}")

## Insertion Sort -> Banding: 585, Geser: 539

set.seed(42)
cac <- sample(2000:4000, 50)

hitung_selection <- function(L) {
  n <- length(L)
  banding <- 0
  tukar <- 0
  for (i in 1:(n-1)) {
    imin <- i
    for (j in (i+1):n) {
      banding <- banding + 1
      if (L[j] < L[imin]) imin <- j
    }
    if (imin != i) { 
      tmp <- L[i]
      L[i] <- L[imin]
      L[imin] <- tmp
      tukar <- tukar + 1 
    }
  }
  return(list(banding = banding, tukar = tukar))
}

hitung_insertion <- function(L) {
  banding <- 0
  geser <- 0
  for (i in 2:length(L)) {
    kunci <- L[i]
    j <- i - 1
    while (j >= 1) {
      banding <- banding + 1
      if (L[j] > kunci) { 
        L[j + 1] <- L[j]
        geser <- geser + 1
        j <- j - 1 
      } else {
        break
      }
    }
    L[j + 1] <- kunci
  }
  return(list(banding = banding, geser = geser))
}

res_sel <- hitung_selection(cac)
res_ins <- hitung_insertion(cac)
cat(sprintf("Selection Sort -> Banding: %d, Tukar: %d\n", res_sel$banding, res_sel$tukar))

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

cat(sprintf("Insertion Sort -> Banding: %d, Geser: %d\n", res_ins$banding, res_ins$geser))

## Insertion Sort -> Banding: 619, Geser: 573