Алгоритмы сортировки

---

Задача

Дан массив, нужно отсортировать его элементы. Существует достаточно большое количество сортировок. Отличаются они друг от друга скоростью выполнения. Мы рассмотрим одну из самых медленных, но самую понятную в реализации сортировку. Она называется сортировкой пузырьком.

Алгоритм сортировки пузырьком

Сортировка пузырьком - это метод сортировки массивов и списков путем последовательного сравнения и обмена соседних элементов, если предшествующий оказывается больше последующего. В процессе выполнения данного алгоритма элементы с большими значениями оказываются в конце списка, а элементы с меньшими значениями постепенно перемещаются по направлению к началу списка. Образно говоря, тяжелые элементы падают на дно, а легкие медленно всплывают подобно пузырькам воздуха.

В сортировке методом пузырька количество итераций внешнего цикла определяется длинной списка минус единица, так как когда второй элемент становится на свое место, то первый уже однозначно минимальный и находится на своем месте.

Количество итераций внутреннего цикла зависит от номера итерации внешнего цикла, так как конец списка уже отсортирован, и выполнять проход по этим элементам смысла нет.

bubble_sort <- function(x){
  n <- length(x)
  for(i in (n-1):1){
    for(j in 1:i){
      if(x[j] > x[j+1]){
        a <- x[j]
        x[j] <- x[j+1]
        x[j+1] <- a
      }
    }
  }
  return(x)
}
x <- sample(1:100,10)
print(x)

##  [1] 59  8 91 33 78 48  1 24 15 99

print(bubble_sort(x))

##  [1]  1  8 15 24 33 48 59 78 91 99

Рассмотрим также реализации других алгоритмов сортировки.

Сортировка выбором

Статья про сортировку выбором.

Алгоритм:

1. Найти наименьшее значение в списке.
2. Записать его в начало списка, а первый элемент - на место, где раньше стоял наименьший.
3. Снова найти наименьший элемент в списке. При этом в поиске не участвует первый элемент.
4. Второй минимум поместить на второе место списка. Второй элемент при этом перемещается на освободившееся место.
5. Продолжать выполнять поиcк и обмен, пока не будет достигнут конец списка

Иногда вместо минимума ищут максимум в массиве, тогда код может слегка отличаться. В качестве тренировки попробуйте дома построить алгоритм при нахождении максимума.

selection <- function(x){
  for(i in 1:(length(x)-1)){
    m <- i
    for(j in (i+1):length(x)){
      if(x[j]<x[m]){
        m <- j
      }
    }
    a <- x[i]
    x[i] <- x[m]
    x[m] <- a
  }
  return(x)
}

x <- sample(-500:500, size = 8)
print(x)

## [1]  481  408 -119  208 -214  156  479  384

selection(x)

## [1] -214 -119  156  208  384  408  479  481

Сортировка вставками

Статья про сортировку вставками.

insertion <- function(x){
  for(i in 2:length(x)){
    k <- i
    
    C <- x[i]
    for(j in (i-1):1){
      if(x[j] > C){
        x[j+1] <- x[j]
        k <- j
      }
    }
    x[k] <- C
  }
  return(x)
}

x <- sample(1:100,30)
print(x)

##  [1]  9 15 63 46 76 95 43 51 82 70 88 40 16 29 74 44 57 73 87 53 97 18 50
## [24] 84 72  8 34 91  1 66

print(insertion(x))

##  [1]  1  8  9 15 16 18 29 34 40 43 44 46 50 51 53 57 63 66 70 72 73 74 76
## [24] 82 84 87 88 91 95 97

Сортировка слиянием

Статья про сортировку слиянием.

При сортировке слиянием массив разбивается пополам на 2 массива до тех пор, пока не останется по одному элементу. Потом начинается поочередное слияние, но только уже в отсортированном порядке. Более наглядно представлено на рисунках.

MERGE <- function(A,B){ 
  C <- c() 
  while(length(A)>0 & length(B)>0){ 
    if(A[1]<B[1]){ 
      C <- c(C,A[1]) 
      A <- A[-1] 
    }else{ 
      C <- c(C,B[1]) 
      B <- B[-1] 
    } 
  } 
  C <- c(C,A,B) 
  return(C) 
} 
mergeSORT <- function(D){ 
  if(length(D)==1){ 
    return(D) 
  }else{ 
    mid <- length(D)%/%2 
    D <- MERGE(mergeSORT(D[1:mid]),mergeSORT(D[(mid+1):length(D)])) 
  } 
  return(D) 
}

x <- sample(1:100,30)
print(x)

##  [1] 51 49 65 73 67 91 83 53 22 18  6 31 82 56 12 89 26 41 52 94 77 10 90
## [24] 55 29 74  1 32 79 58

print(mergeSORT(x))

##  [1]  1  6 10 12 18 22 26 29 31 32 41 49 51 52 53 55 56 58 65 67 73 74 77
## [24] 79 82 83 89 90 91 94