# LATIHAN MATERI 1
# 1. Nilai UTS pada contoh 1.2
# Data nilai UTS
nilai <- c(40, 96, 57, 52, 84, 72, 60,
           85, 86, 73, 81, 78, 89, 54, 62)

n <- length(nilai)

# Menghitung jumlah
total <- 0
for (i in 1:n) {
  total <- total + nilai[i]
}

# Menghitung rata-rata
rata <- total / n

# Menghitung jumlah kuadrat selisih
jumlah_kuadrat <- 0
for (i in 1:n) {
  jumlah_kuadrat <- jumlah_kuadrat +
    (nilai[i] - rata)^2
}

# Menghitung simpangan baku sampel
sb <- sqrt(jumlah_kuadrat / (n - 1))

cat("Jumlah nilai       :", total, "\n")
## Jumlah nilai       : 1069
cat("Rata-rata           :", round(rata, 2), "\n")
## Rata-rata           : 71.27
cat("Simpangan baku      :", round(sb, 2), "\n")
## Simpangan baku      : 16.26
#2. Modifikasi cariIdx
CariIdxMaks <- function(A) {
  maks <- 1

  for (i in 2:length(A)) {
    if (A[i] >= A[maks]) {
      maks <- i
    }
  }

  return(maks)
}

data <- c(10, 20, 30, 20, 30)

hasil <- CariIdxMaks(data)

cat("Indeks maksimum terakhir =", hasil, "\n")
## Indeks maksimum terakhir = 5
cat("Nilai maksimum =", data[hasil], "\n")
## Nilai maksimum = 30
# 3. Membuat prosedur MaksMin sekaligus
maks_min_sekaligus <- function(L) {

  maks <- L[1]
  minimum <- L[1]

  for (i in 2:length(L)) {

    if (L[i] > maks) {
      maks <- L[i]
    }

    if (L[i] < minimum) {
      minimum <- L[i]
    }
  }

  return(c(maksimum = maks, minimum = minimum))
}

# Contoh
L <- c(25, 10, 40, 5, 30, 15)

hasil <- maks_min_sekaligus(L)

print(hasil)
## maksimum  minimum 
##       40        5
# 4. Mencari hari dengan kenaikan harian terbesar DAX
# Memanggil data saham
data("EuStockMarkets")

# Mengambil kolom DAX
DAX <- EuStockMarkets[, "DAX"]

n <- length(DAX)

# Inisialisasi kenaikan terbesar
maks_naik <- DAX[2] - DAX[1]
hari <- 2

# Traversal untuk mencari kenaikan terbesar
for (i in 3:n) {

  kenaikan <- DAX[i] - DAX[i - 1]

  if (kenaikan > maks_naik) {
    maks_naik <- kenaikan
    hari <- i
  }
}

cat("Kenaikan harian terbesar DAX :", maks_naik, "\n")
## Kenaikan harian terbesar DAX : 160.97
cat("Terjadi pada hari ke-        :", hari, "\n")
## Terjadi pada hari ke-        : 1653
# 5. Menghitung jumlah dan rata-rata perkolom matriks penjualan
# Matriks penjualan 3 toko x 4 minggu
M <- matrix(c(
  10, 45, 34, 43,
  63, 69, 22, 13,
  13, 82, 23, 60
), nrow = 3, byrow = TRUE)

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

jumlah <- numeric(nkol)
rata <- numeric(nkol)

# Menghitung jumlah dan rata-rata setiap kolom
for (j in 1:nkol) {

  for (i in 1:nbar) {
    jumlah[j] <- jumlah[j] + M[i, j]
  }

  rata[j] <- jumlah[j] / nbar
}

# Mencari minggu dengan penjualan tertinggi
maks <- jumlah[1]
minggu_maks <- 1

for (j in 2:nkol) {
  if (jumlah[j] > maks) {
    maks <- jumlah[j]
    minggu_maks <- j
  }
}

cat("Jumlah per minggu :", jumlah, "\n")
## Jumlah per minggu : 86 196 79 116
cat("Rata-rata per minggu :", rata, "\n")
## Rata-rata per minggu : 28.66667 65.33333 26.33333 38.66667
cat("Penjualan tertinggi :", maks, "\n")
## Penjualan tertinggi : 196
cat("Minggu paling tinggi :", minggu_maks, "\n")
## Minggu paling tinggi : 2
# 6. Membuktikan bahwa [[0]*3]*3 menghasilkan baris yang saling terkait di Python
# Membuat matriks 3 x 3
M <- matrix(0, nrow = 3, ncol = 3)

cat("Matriks awal:\n")
## Matriks awal:
print(M)
##      [,1] [,2] [,3]
## [1,]    0    0    0
## [2,]    0    0    0
## [3,]    0    0    0
# Mengubah satu elemen
M[1, 1] <- 99

cat("\nMatriks setelah diubah:\n")
## 
## Matriks setelah diubah:
print(M)
##      [,1] [,2] [,3]
## [1,]   99    0    0
## [2,]    0    0    0
## [3,]    0    0    0
# LATIHAN MATERI 2
# 1. Menelusuri SeqSearch1 dan SeqSearch2
seq_search1 <- function(L, x) {
  n <- length(L)
  i <- 1

  while (i < n && L[i] != x) {
    i <- i + 1
  }

  if (n > 0 && L[i] == x) {
    return(i)
  } else {
    return(0)
  }
}


# Sequential Search 2 (dengan boolean)
seq_search2 <- function(L, x) {
  n <- length(L)
  i <- 1
  ketemu <- FALSE

  while (i <= n && !ketemu) {
    if (L[i] == x) {
      ketemu <- TRUE
    } else {
      i <- i + 1
    }
  }

  if (ketemu) {
    return(i)
  } else {
    return(0)
  }
}


# Program utama
L <- c(7, 3, 9, 3, 5)

cat("SEQSEARCH1\n")
## SEQSEARCH1
cat("x = 3:", seq_search1(L, 3), "\n")
## x = 3: 2
cat("x = 8:", seq_search1(L, 8), "\n")
## x = 8: 0
cat("\nSEQSEARCH2\n")
## 
## SEQSEARCH2
cat("x = 3:", seq_search2(L, 3), "\n")
## x = 3: 2
cat("x = 8:", seq_search2(L, 8), "\n")
## x = 8: 0
# 2. Apa yang terjadi jika tidak menggunakan short-circuit?
L <- c(7, 3, 9, 3, 5)
x <- 8

i <- 1
n <- length(L)
ketemu <- FALSE

while (i <= n) {
  if (L[i] == x) {
    ketemu <- TRUE
    break
  } else {
    i <- i + 1
  }
}

if (ketemu) {
  print("Data ditemukan")
} else {
  print("Data tidak ditemukan")
}
## [1] "Data tidak ditemukan"
# 3. Menelusuri BinSearch1 dan BinSearch2
bin_search1 <- function(L, x) {
  i <- 1
  j <- length(L)
  ketemu <- FALSE
  k <- 0

  while (!ketemu && i <= j) {
    k <- (i + j) %/% 2

    if (L[k] == x) {
      ketemu <- TRUE
    } else if (L[k] < x) {
      i <- k + 1
    } else {
      j <- k - 1
    }
  }

  if (ketemu) {
    return(k)
  } else {
    return(0)
  }
}


# Binary Search 2 (tanpa boolean)
bin_search2 <- function(L, x) {
  i <- 1
  j <- length(L)

  while (i < j) {
    k <- (i + j) %/% 2

    if (L[k] < x) {
      i <- k + 1
    } else {
      j <- k
    }
  }

  if (L[i] == x) {
    return(i)
  } else {
    return(0)
  }
}


# Program utama
L <- c(2, 5, 8, 12, 16, 23, 38, 56, 72, 91)

cat("BINSEARCH1\n")
## BINSEARCH1
for (x in c(23, 6)) {
  cat("x =", x, "posisi =", bin_search1(L, x), "\n")
}
## x = 23 posisi = 6 
## x = 6 posisi = 0
cat("\nBINSEARCH2\n")
## 
## BINSEARCH2
for (x in c(23, 6)) {
  cat("x =", x, "posisi =", bin_search2(L, x), "\n")
}
## x = 23 posisi = 6 
## x = 6 posisi = 0
# 4. Mengubah Binary Search agar bekerja pada larik terurut menurun
binary_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) {
      i <- k + 1
    } else {
      j <- k - 1
    }
  }

  return(0)
}


L <- c(91, 72, 56, 38, 23, 16, 12, 8, 5, 2)

cat("Posisi 23:", binary_menurun(L, 23), "\n")
## Posisi 23: 5
cat("Posisi 6:", binary_menurun(L, 6), "\n")
## Posisi 6: 0
# 5. Dataset precip dan Pencarian Seattle Tacoma
# Memanggil dataset precip
data(precip)

# Mengambil nama kota
kota <- names(precip)

# Menyimpan data asli
kota_asli <- kota

# =================================
# BUBBLE SORT (URUT ALFABETIS)
# =================================

n <- length(kota)

for (i in 1:(n - 1)) {
  for (j in 1:(n - i)) {

    if (kota[j] > kota[j + 1]) {
      temp <- kota[j]
      kota[j] <- kota[j + 1]
      kota[j + 1] <- temp
    }

  }
}

cat("Nama kota setelah diurutkan:\n")
## Nama kota setelah diurutkan:
print(kota)
##  [1] "Albany"              "Albuquerque"         "Atlanta"            
##  [4] "Atlantic City"       "Baltimore"           "Bismarck"           
##  [7] "Boise"               "Boston"              "Buffalo"            
## [10] "Burlington"          "Charleston"          "Charlotte"          
## [13] "Cheyenne"            "Chicago"             "Cincinnati"         
## [16] "Cleveland"           "Columbia"            "Columbus"           
## [19] "Concord"             "Dallas"              "Denver"             
## [22] "Des Moines"          "Detroit"             "Duluth"             
## [25] "El Paso"             "Great Falls"         "Hartford"           
## [28] "Honolulu"            "Houston"             "Indianapolis"       
## [31] "Jackson"             "Jacksonville"        "Juneau"             
## [34] "Kansas City"         "Little Rock"         "Los Angeles"        
## [37] "Louisville"          "Memphis"             "Miami"              
## [40] "Milwaukee"           "Minneapolis/St Paul" "Mobile"             
## [43] "Nashville"           "New Orleans"         "New York"           
## [46] "Norfolk"             "Oklahoma City"       "Omaha"              
## [49] "Peoria"              "Philadelphia"        "Phoenix"            
## [52] "Pittsburgh"          "Portland"            "Portland"           
## [55] "Providence"          "Raleigh"             "Reno"               
## [58] "Richmond"            "Sacramento"          "Salt Lake City"     
## [61] "San Francisco"       "San Juan"            "Sault Ste. Marie"   
## [64] "Seattle Tacoma"      "Sioux Falls"         "Spokane"            
## [67] "St Louis"            "Washington"          "Wichita"            
## [70] "Wilmington"
# =================================
# BINARY SEARCH
# =================================

binary_search <- function(L, x) {

  i <- 1
  j <- length(L)
  perbandingan <- 0

  while (i <= j) {

    k <- (i + j) %/% 2
    perbandingan <- perbandingan + 1

    if (L[k] == x) {
      return(c(posisi = k,
               perbandingan = perbandingan))

    } else if (L[k] < x) {
      i <- k + 1

    } else {
      j <- k - 1
    }
  }

  return(c(posisi = 0,
           perbandingan = perbandingan))
}

# =================================
# SEQUENTIAL SEARCH
# =================================

sequential_search <- function(L, x) {

  perbandingan <- 0

  for (i in seq_along(L)) {

    perbandingan <- perbandingan + 1

    if (L[i] == x) {
      return(c(posisi = i,
               perbandingan = perbandingan))
    }
  }

  return(c(posisi = 0,
           perbandingan = perbandingan))
}

# Nilai yang dicari
target <- "Seattle Tacoma"

# Menjalankan pencarian
hasil_binary <- binary_search(kota, target)

hasil_sequential <- sequential_search(
  kota_asli, target
)

# Menampilkan hasil
cat("\nHASIL BINARY SEARCH\n")
## 
## HASIL BINARY SEARCH
print(hasil_binary)
##       posisi perbandingan 
##           64            5
cat("\nHASIL SEQUENTIAL SEARCH\n")
## 
## HASIL SEQUENTIAL SEARCH
print(hasil_sequential)
##       posisi perbandingan 
##           65           65
# 6. Binary Search Rekursif dalam R
binary_recursive <- function(L, x, i = 1, j = length(L)) {

  # Kondisi berhenti
  if (i > j) {
    return(0)
  }

  k <- (i + j) %/% 2

  if (L[k] == x) {
    return(k)

  } else if (L[k] < x) {
    return(
      binary_recursive(L, x, k + 1, j)
    )

  } else {
    return(
      binary_recursive(L, x, i, k - 1)
    )
  }
}


# Program utama
L <- c(2, 5, 8, 12, 16, 23, 38, 56, 72, 91)

cat("x = 23:", binary_recursive(L, 23), "\n")
## x = 23: 6
cat("x = 6:", binary_recursive(L, 6), "\n")
## x = 6: 0
# 7. Perbandingan Maksimum Binary Search
n <- 1000000

perbandingan <- floor(log2(n)) + 1

cat("Jumlah data:", n, "\n")
## Jumlah data: 1e+06
cat("Perbandingan maksimum:", perbandingan, "\n")
## Perbandingan maksimum: 20
# LATIHAN MATERI 3
# 1. Larik setelah setiap pass (Selection Sort) 
L <- c(25, 22, 18, 20, 15)

for (i in 1:(length(L)-1)) {
  idx <- i

  for (j in (i+1):length(L)) {
    if (L[j] > L[idx]) {
      idx <- j
    }
  }

  temp <- L[i]
  L[i] <- L[idx]
  L[idx] <- temp

  cat("Pass", i, ":", L, "\n")
}
## 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. Insertion Sort

insertion_sort <- function(L) {
  perbandingan <- 0
  pergeseran <- 0

  for (i in 2:length(L)) {
    key <- L[i]
    j <- i - 1

    while (j >= 1) {
      perbandingan <- perbandingan + 1

      if (L[j] > key) {
        L[j+1] <- L[j]
        pergeseran <- pergeseran + 1
        j <- j - 1
      } else {
        break
      }
    }

    L[j+1] <- key
    cat("Pass", i-1, ":", L, "\n")
  }

  cat("Perbandingan =", perbandingan, "\n")
  cat("Pergeseran =", pergeseran, "\n")
}

insertion_sort(c(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 
## Perbandingan = 10 
## Pergeseran = 10
cat("\n")
insertion_sort(c(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 
## Perbandingan = 5 
## Pergeseran = 1
# 3. Stabilitas Selection Sort

nama <- c("A", "B", "C")
nilai <- c(2, 2, 1)

for (i in 1:(length(nilai)-1)) {
  idx <- i

  for (j in (i+1):length(nilai)) {
    if (nilai[j] < nilai[idx]) {
      idx <- j
    }
  }

  temp <- nilai[i]
  nilai[i] <- nilai[idx]
  nilai[idx] <- temp

  temp_nama <- nama[i]
  nama[i] <- nama[idx]
  nama[idx] <- temp_nama
}

data.frame(nama, nilai)
##   nama nilai
## 1    C     1
## 2    B     2
## 3    A     2
# 4. Binary Insertion Sort

binary_insertion_sort <- function(L) {
  perbandingan <- 0
  pergeseran <- 0

  for (i in 2:length(L)) {
    key <- L[i]
    kiri <- 1
    kanan <- i

    while (kiri < kanan) {
      tengah <- floor((kiri + kanan) / 2)
      perbandingan <- perbandingan + 1

      if (L[tengah] > key) {
        kanan <- tengah
      } else {
        kiri <- tengah + 1
      }
    }

    for (j in i:kiri) {
      if (j > kiri) {
        L[j] <- L[j-1]
        pergeseran <- pergeseran + 1
      }
    }

    L[kiri] <- key
  }

  cat("Hasil:", L, "\n")
  cat("Perbandingan:", perbandingan, "\n")
  cat("Pergeseran:", pergeseran, "\n")
}

binary_insertion_sort(c(5, 4, 3, 2, 1))
## Hasil: 1 2 3 4 5 
## Perbandingan: 8 
## Pergeseran: 10
# 5. Pengurutan 50 Harga CA

data("EuStockMarkets")

L <- EuStockMarkets[1:50, "CAC"]

selection_sort <- function(A) {
  perbandingan <- 0
  pertukaran <- 0

  for (i in 1:(length(A)-1)) {
    idx <- i

    for (j in (i+1):length(A)) {
      perbandingan <- perbandingan + 1

      if (A[j] > A[idx]) {
        idx <- j
      }
    }

    if (idx != i) {
      temp <- A[i]
      A[i] <- A[idx]
      A[idx] <- temp
      pertukaran <- pertukaran + 1
    }
  }

  list(hasil=A, perbandingan=perbandingan,
       pertukaran=pertukaran)
}

insertion_sort <- function(A) {
  perbandingan <- 0
  pergeseran <- 0

  for (i in 2:length(A)) {
    key <- A[i]
    j <- i-1

    while (j >= 1) {
      perbandingan <- perbandingan + 1

      if (A[j] < key) {
        A[j+1] <- A[j]
        pergeseran <- pergeseran + 1
        j <- j-1
      } else {
        break
      }
    }

    A[j+1] <- key
  }

  list(hasil=A, perbandingan=perbandingan,
       pergeseran=pergeseran)
}

hasil1 <- selection_sort(L)
hasil2 <- insertion_sort(L)

cat("Selection Sort:\n")
## Selection Sort:
print(hasil1)
## $hasil
##  [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
## 
## $perbandingan
## [1] 1225
## 
## $pertukaran
## [1] 47
cat("\nInsertion Sort:\n")
## 
## Insertion Sort:
print(hasil2)
## $hasil
##  [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
## 
## $perbandingan
## [1] 1069
## 
## $pergeseran
## [1] 1031