tugas latihan 3

## ===================== LATIHAN MATERI 3 =====================

## ---------- Fungsi umum ----------
tukar <- function(x, a, b) { t <- x[a]; x[a] <- x[b]; x[b] <- t; x }

# Selection sort menurun (seleksi maksimum) + larik tiap pass
sel_max <- function(x, trace = TRUE) {
  n <- length(x); banding <- 0; tuker <- 0
  for (i in 1:(n - 1)) {
    idx <- i
    for (j in (i + 1):n) {
      banding <- banding + 1
      if (x[j] > x[idx]) idx <- j
    }
    if (idx != i) { x <- tukar(x, i, idx); tuker <- tuker + 1 }
    if (trace) cat("Pass", i, ":", x, "\n")
  }
  list(hasil = x, banding = banding, tukar = tuker)
}

# Selection sort menurun (seleksi minimum -> dipindah ke belakang)
sel_min <- function(x, trace = TRUE) {
  n <- length(x)
  for (p in 1:(n - 1)) {
    last <- n - p + 1
    idx <- 1
    for (j in 2:last) if (x[j] < x[idx]) idx <- j
    if (idx != last) x <- tukar(x, idx, last)
    if (trace) cat("Pass", p, ":", x, "\n")
  }
  x
}

# Insertion sort + hitung perbandingan & pergeseran
ins_sort <- function(x, desc = FALSE) {
  banding <- 0; geser <- 0
  for (i in 2:length(x)) {
    key <- x[i]; j <- i - 1
    while (j >= 1) {
      banding <- banding + 1
      if ((!desc && x[j] > key) || (desc && x[j] < key)) {
        x[j + 1] <- x[j]; geser <- geser + 1; j <- j - 1
      } else break
    }
    x[j + 1] <- key
  }
  list(hasil = x, banding = banding, geser = geser)
}

# Binary insertion sort + hitung perbandingan & pergeseran
bin_ins <- function(x, desc = FALSE) {
  banding <- 0; geser <- 0
  for (i in 2:length(x)) {
    key <- x[i]; lo <- 1; hi <- i - 1
    while (lo <= hi) {
      mid <- (lo + hi) %/% 2
      banding <- banding + 1
      if ((!desc && key < x[mid]) || (desc && key > x[mid])) hi <- mid - 1
      else lo <- mid + 1
    }
    if (lo < i) { x[(lo + 1):i] <- x[lo:(i - 1)]; geser <- geser + (i - lo) }
    x[lo] <- key
  }
  list(hasil = x, banding = banding, geser = geser)
}

## ---------- Soal 1 ----------
d1 <- c(25, 22, 18, 20, 15)
cat("== Seleksi Maksimum ==\n"); sel_max(d1)

## == Seleksi Maksimum ==

## 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

## $hasil
## [1] 25 22 20 18 15
## 
## $banding
## [1] 10
## 
## $tukar
## [1] 1

cat("== Seleksi Minimum ==\n");  sel_min(d1)

## == Seleksi Minimum ==

## 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

## [1] 25 22 20 18 15

## ---------- Soal 2 ----------
a <- ins_sort(c(5, 4, 3, 2, 1)); print(a)   # banding 10, geser 10

## $hasil
## [1] 1 2 3 4 5
## 
## $banding
## [1] 10
## 
## $geser
## [1] 10

b <- ins_sort(c(1, 2, 3, 5, 4)); print(b)   # banding 5,  geser 1

## $hasil
## [1] 1 2 3 4 5
## 
## $banding
## [1] 5
## 
## $geser
## [1] 1

## ---------- Soal 3 (bukti selection sort tidak stabil) ----------
rec <- data.frame(nama = c("A", "B", "C"), nilai = c(5, 5, 3))
sel_stabil <- function(df) {
  n <- nrow(df)
  for (i in 1:(n - 1)) {
    idx <- i
    for (j in (i + 1):n) if (df$nilai[j] < df$nilai[idx]) idx <- j
    if (idx != i) { t <- df[i, ]; df[i, ] <- df[idx, ]; df[idx, ] <- t }
  }
  df
}
print(rec); print(sel_stabil(rec))   # hasil: C, B, A -> urutan A,B terbalik

##   nama nilai
## 1    A     5
## 2    B     5
## 3    C     3

##   nama nilai
## 1    C     3
## 2    B     5
## 3    A     5

## ---------- Soal 4 ----------
x4 <- c(5, 4, 3, 2, 1)
r_biasa  <- ins_sort(x4)
r_binary <- bin_ins(x4)
cat("Insertion biasa : banding =", r_biasa$banding,  " geser =", r_biasa$geser,  "\n")

## Insertion biasa : banding = 10  geser = 10

cat("Binary insertion: banding =", r_binary$banding, " geser =", r_binary$geser, "\n")

## Binary insertion: banding = 6  geser = 10

# perbandingan turun, pergeseran sama

## ---------- Soal 5 ----------
cac <- as.numeric(EuStockMarkets[1:50, "CAC"])
s <- sel_max(cac, trace = FALSE)
i <- ins_sort(cac, desc = TRUE)
bi <- bin_ins(cac, desc = TRUE)

hasil <- data.frame(
  Metode      = c("Selection sort", "Insertion sort", "Binary insertion"),
  Perbandingan = c(s$banding, i$banding, bi$banding),
  `Pergeseran/Pertukaran` = c(s$tukar, i$geser, bi$geser),
  check.names = FALSE
)
print(hasil)

##             Metode Perbandingan Pergeseran/Pertukaran
## 1   Selection sort         1225                    47
## 2   Insertion sort         1069                  1031
## 3 Binary insertion          210                  1031

stopifnot(identical(s$hasil, i$hasil), identical(s$hasil, sort(cac, decreasing = TRUE)))