Сортировка – это фундаментальная операция в информатике, которая упорядочивает элементы в определенном порядке. В этой статье блога мы рассмотрим различные алгоритмы сортировки на языке программирования R, уделив особое внимание методам, устраняющим повторяющиеся значения. Мы предоставим примеры кода для каждого алгоритма и обсудим их сильные и слабые стороны. Итак, давайте окунемся в мир сортировки без повторений в R!

1. Пузырьковая сортировка.
   Пузырьковая сортировка – это простой и интуитивно понятный алгоритм сортировки на основе сравнения. Он неоднократно сравнивает соседние элементы и меняет их местами, если они расположены в неправильном порядке. Чтобы удалить дубликаты, мы можем использовать функцию unique() для отсортированного массива.

bubble_sort <- function(arr) {
  n <- length(arr)

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

  arr <- unique(arr)
  return(arr)
}

2. Сортировка слиянием.
   Сортировка слиянием — это алгоритм «разделяй и властвуй», который делит входной массив на более мелкие подмассивы, сортирует их, а затем снова объединяет. Используя функцию unique() в отсортированных подмассивах, мы можем удалить повторяющиеся значения на этапе слияния.

merge_sort <- function(arr) {
  n <- length(arr)

  if (n <= 1) {
    return(arr)
  }

  mid <- floor(n/2)
  left <- merge_sort(arr[1:mid])
  right <- merge_sort(arr[(mid + 1):n])

  merged <- merge(left, right)
  merged <- unique(merged)

  return(merged)
}

3. Быстрая сортировка.
   Быстрая сортировка — это еще один эффективный алгоритм «разделяй и властвуй», который выбирает опорный элемент и разбивает массив вокруг него. Используя функцию unique() после разделения, мы можем исключить повторяющиеся значения.

quick_sort <- function(arr) {
  n <- length(arr)

  if (n <= 1) {
    return(arr)
  }

  pivot <- arr[1]
  smaller <- arr[arr < pivot]
  equal <- arr[arr == pivot]
  greater <- arr[arr > pivot]

  sorted <- c(quick_sort(smaller), equal, quick_sort(greater))
  sorted <- unique(sorted)

  return(sorted)
}

4. Поразрядная сортировка.
   Поразрядная сортировка — это алгоритм несравнительной сортировки, который сортирует элементы по цифрам или битам. Для сортировки без повторения мы можем использовать функцию unique() после каждой итерации процесса сортировки.

radix_sort <- function(arr) {
  max_val <- max(arr)
  exp <- 1

  while (max_val/exp > 0) {
    arr <- counting_sort(arr, exp)
    exp <- exp * 10
  }

  arr <- unique(arr)
  return(arr)
}
counting_sort <- function(arr, exp) {
  n <- length(arr)
  output <- numeric(n)
  count <- numeric(10)

  for (i in 1:n) {
    index <- (arr[i] %/% exp) %% 10
    count[index + 1] <- count[index + 1] + 1
  }

  for (i in 2:10) {
    count[i] <- count[i] + count[i - 1]
  }

  for (i in n:1) {
    index <- (arr[i] %/% exp) %% 10
    output[count[index + 1]] <- arr[i]
    count[index + 1] <- count[index + 1] - 1
  }

  return(output)
}

В этой статье блога мы рассмотрели несколько алгоритмов сортировки в R, которые удаляют повторяющиеся значения. Мы рассмотрели пузырьковую сортировку, сортировку слиянием, быструю сортировку и поразрядную сортировку, приведя примеры кода для каждого алгоритма. Понимая эти методы, вы сможете эффективно сортировать массивы, исключая повторение. Не забудьте выбрать правильный алгоритм с учетом размера и характеристик ваших данных.