# 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