LATIHAN MATERI 3 ALGORITMA SORTING

selection_maks <- function(A) {
  n <- length(A)

  for (i in 1:(n-1)) {
    imaks <- i

    for (j in (i+1):n) {
      if (A[j] > A[imaks]) {
        imaks <- j
      }
    }

    temp <- A[i]
    A[i] <- A[imaks]
    A[imaks] <- temp

    print(A)
  }

  return(A)
}

A <- c(25, 22, 18, 20, 15)

selection_maks(A)

## [1] 25 22 18 20 15
## [1] 25 22 18 20 15
## [1] 25 22 20 18 15
## [1] 25 22 20 18 15

## [1] 25 22 20 18 15

binary_insertion_sort <- function(A) {

  n <- length(A)

  for (i in 2:n) {

    y <- A[i]

    kiri <- 1
    kanan <- i

    # Mencari posisi sisip
    while (kiri < kanan) {

      tengah <- (kiri + kanan) %/% 2

      if (A[tengah] <= y) {
        kiri <- tengah + 1
      } else {
        kanan <- tengah
      }
    }

    # Menggeser elemen
    j <- i

    while (j > kiri) {
      A[j] <- A[j-1]
      j <- j - 1
    }

    A[kiri] <- y
  }

  return(A)
}

A <- c(5, 2, 4, 1, 3)

print(binary_insertion_sort(A))

## [1] 1 2 3 4 5

# Latihan Materi 3 Nomor 5 ----
# Selection Sort dan Insertion Sort
# Data EuStockMarkets

# 1. Mengambil 50 data CAC pertama
data("EuStockMarkets")

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

print("Data CAC sebelum diurutkan:")

## [1] "Data CAC sebelum diurutkan:"

print(cac)

##  [1] 1772.8 1750.5 1718.0 1708.1 1723.1 1714.3 1734.5 1757.4 1754.0 1754.3
## [11] 1759.8 1755.5 1758.1 1757.5 1763.5 1762.8 1768.9 1778.1 1780.1 1767.7
## [21] 1757.9 1756.6 1754.7 1766.8 1766.5 1762.2 1759.5 1782.4 1789.5 1783.5
## [31] 1780.4 1808.8 1820.3 1820.3 1820.3 1687.5 1725.6 1792.9 1819.1 1833.5
## [41] 1853.4 1849.7 1851.8 1857.7 1864.3 1863.5 1873.2 1860.8 1868.7 1860.4

# 2. Fungsi Selection Sort (Menurun)
selection_sort <- function(x) {
  n <- length(x)
  perbandingan <- 0
  pertukaran <- 0

  for (i in 1:(n - 1)) {
    indeks_max <- i

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

      if (x[j] > x[indeks_max]) {
        indeks_max <- j
      }
    }

    if (indeks_max != i) {
      temp <- x[i]
      x[i] <- x[indeks_max]
      x[indeks_max] <- temp

      pertukaran <- pertukaran + 1
    }
  }

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


# 3. Fungsi Insertion Sort (Menurun)
insertion_sort <- function(x) {
  n <- length(x)
  perbandingan <- 0
  pergeseran <- 0

  for (i in 2:n) {
    key <- x[i]
    j <- i - 1

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

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

    x[j + 1] <- key
  }

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


# 4. Menjalankan Selection Sort
hasil_selection <- selection_sort(cac)

cat("\nHasil Selection Sort:\n")

## 
## Hasil Selection Sort:

print(hasil_selection$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

cat("Jumlah perbandingan:",
    hasil_selection$perbandingan, "\n")

## Jumlah perbandingan: 1225

cat("Jumlah pertukaran:",
    hasil_selection$pertukaran, "\n")

## Jumlah pertukaran: 47

# 5. Menjalankan Insertion Sort
hasil_insertion <- insertion_sort(cac)

cat("\nHasil Insertion Sort:\n")

## 
## Hasil Insertion Sort:

print(hasil_insertion$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

cat("Jumlah perbandingan:",
    hasil_insertion$perbandingan, "\n")

## Jumlah perbandingan: 1069

cat("Jumlah pergeseran:",
    hasil_insertion$pergeseran, "\n")

## Jumlah pergeseran: 1031

# 6. Membandingkan hasil kedua algoritma
perbandingan_algoritma <- data.frame(
  Algoritma = c("Selection Sort", "Insertion Sort"),
  Perbandingan = c(
    hasil_selection$perbandingan,
    hasil_insertion$perbandingan
  ),
  Pertukaran_Pergeseran = c(
    hasil_selection$pertukaran,
    hasil_insertion$pergeseran
  )
)

cat("\nTabel Perbandingan Operasi:\n")

## 
## Tabel Perbandingan Operasi:

print(perbandingan_algoritma)

##        Algoritma Perbandingan Pertukaran_Pergeseran
## 1 Selection Sort         1225                    47
## 2 Insertion Sort         1069                  1031

# 7. Memeriksa apakah hasil pengurutan sama
cat("\nApakah hasil kedua algoritma sama?\n")

## 
## Apakah hasil kedua algoritma sama?

print(identical(
  hasil_selection$hasil,
  hasil_insertion$hasil
))

## [1] TRUE