Rでバブルソート

再帰で実装

bubble_sort <- 
  function(x) {
    len_x <- length(x)
    for(i in 1L:(len_x - 1L)){
      if(x[i] > x[i + 1L]) {
        x[i:(i + 1L)] <- c(x[i + 1L], x[i])
        x <- sort_bubble(x)
      }
    }
    x
  }

x <- 100:1
bubble_sort(x)

  [1]   1   2   3   4   5   6   7   8   9  10  11  12  13  14
 [15]  15  16  17  18  19  20  21  22  23  24  25  26  27  28
 [29]  29  30  31  32  33  34  35  36  37  38  39  40  41  42
 [43]  43  44  45  46  47  48  49  50  51  52  53  54  55  56
 [57]  57  58  59  60  61  62  63  64  65  66  67  68  69  70
 [71]  71  72  73  74  75  76  77  78  79  80  81  82  83  84
 [85]  85  86  87  88  89  90  91  92  93  94  95  96  97  98
 [99]  99 100

実行時間計測

要素数が多くなるとネストが深くなってエラー．

> bench::system_time(bubble_sort(100:1))
process    real 
 46.8ms  50.2ms 
> bench::system_time(bubble_sort(1000:1))
Error: evaluation nested too deeply: infinite recursion / options(expressions=)?

再帰なしで実装

bubble_sort2 <- function(x) {
  i <- 1
  while(i < length(x)){
    if(x[i] > x[i + 1]) {
      x[i:(i+1)] <- c(x[i+1], x[i])
      i <- 1
    }else{
      i <- i + 1
    }
  }
  x
}

実行時間計測2

> bench::system_time(bubble_sort2(10:1))
process    real 
      0  89.2us 
> bench::system_time(bubble_sort2(100:1))
process    real 
 46.8ms  41.7ms 
> bench::system_time(bubble_sort2(1000:1))
process    real 
  30.5s   30.6s

Plot

library(tidyverse)

vector_len <- c(10, 100, 200, 300, 400, 500, 1000)
sec <- 
  map_dbl(vector_len, ~ bench::system_time(bubble_sort2(.x:1)) %>% .[2])

plot(vector_len, sec, type = 'b')