Mergesort em C++ usando o pacote Rcpp

A muito tempo atrás eu comecei a ver como dava para usar código em linguagem C do R neste post aqui. Depois disso, no comentário alguém mais esperto que eu falou sobre um tal de pacote Rcpp, que permitia de maneira mais simples, usar código em linguagem C++ do R, depois disso eu fiz mais alguns testes, tentando implementar alguns algorítimos de ordenação, o bubblesort aqui e o insertion sort aqui.

Esse é o tipo de coisa inútil de se fazer, mas é divertido. E esses algorítimos de ordenação tem em qualquer curso introdutório de programação, então são implementações básicas para qualquer linguagem. Depois do mergesort eu ainda tenho o quicksort, mas no mergesort tudo começa a ficar mais complexo.

Por curiosidade, o método padrão na função sort() do R é o Shellsort, criado por Donald Shell mas o que está implementado no R é uma variante do Robert Sedgewick, esse cara da quatro cursos sobre programação gratuitos no Coursera, so olhar aqui.

Mas na função sort do R também temos o Quicksort, mas ele vai ficar pra próxima.

Agora vamos ver o mergesort. Ele é um algorítimo recursivo, ou seja uma função que chama ela mesma, e a ideia básica é, melhor que ordenar todo um vetor, é pegar dois vetores ordenados e então simplesmente intercalar eles. Mas a gente precisa de dois vetores ordenados pra poder usar esse esquema certo?
Pra isso é so a gente quebrar o vetor no meio, e de novo no meio para as duas metades, e de novo para os quatro quartos, e de novo até que vai chegar um momento que so vamos ter mini vetores de um elemento, um vetor de um elemento está necessariamente ordenado, logo agora é so voltar intercalando esses vetores que fica tudo bem.

MergeSort

É até estranho como isso funciona, mas funciona. Bem o legal que diferente do InsertionSort e o BubbleSort, aqui a gente vai precisar de uma função auxiliar, então a gente vai escrever o código em um arquivo, que vamos chamar de merge.cpp, e depois vamos chamar esse arquivo do R usando a função sourceCpp() do pacote Rcpp.

Então o código do mergesort é assim:

#include <Rcpp.h>
using namespace Rcpp;
 
void intercala(int p, int q, int r, NumericVector v,  NumericVector w)
{
  int i, j, k;
   i = p;
   j = q;
   k = 0;
   while (i < q && j < r) {
      if (v[i] < v[j]) {
         w[k] = v[i];
         i++;
      }
      else {
         w[k] = v[j];
         j++;
      }
      k++;
   }
   while (i < q) {
      w[k] = v[i];
      i++;
      k++;
   }
   while (j < r) {
      w[k] = v[j];
      j++;
      k++;
   }
   for (i = p; i < r; i++)
      v[i] = w[i-p];
}
 
void mergesort(int p, int r, NumericVector v, NumericVector aux)
{
   int q;
   if (p < r - 1) {
      q = (p + r) / 2;
      mergesort(p, q, v,aux);
      mergesort(q, r, v,aux);
      intercala(p, q, r, v,aux);
   }
}
 
// [[Rcpp::export]]
NumericVector mergesortC(NumericVector vetor) {
  Rcpp::NumericVector saida = Rcpp::clone(vetor);
  Rcpp::NumericVector aux = Rcpp::clone(vetor);
  int n = saida.size();
  mergesort(0,n,saida,aux);
  return saida;
}

Então, tudo isso está dentro de um arquivo que eu chamei de merge.cpp
Basicamente o código você acha em qualquer esquina da rede mundial de computadores, mas especificamente aqui, temos que importar a biblioteca Rcpp.h, já que estamos usando um objeto específico dela, que é o NumericVector. Outra coisa é que o R manda um ponteiro pra cá, que aponta aonde estão os dados, desse objeto. Se a gente tentar mexer direto nele, não vai dar certo, eu tentei e fiz o R travar com isso heheh, ai perguntando no forum aqui, o cara que criou o pacote me mandou ir estudar, ai lendo o livro dele eu vi que mexer direto nos dados, muitas vezes não é uma boa ideia, dai a gente usa o método clone de NumericVector, a gente clona ele para outro vetor, e então manipula esse novo vetor, pra não mexer na memoria que não devemos.
Outra coisa é que, talvez um ponto fraco do mergeSort, é que para intercalar dois vetores, precisamos de outro lugar para ir guardando eles em ordem, ou seja, diferente do insertionsort, não da para ir arrumando dentro do próprio vetor, por isso precisamos de um vetor auxiliar, aqui eu ja criei um vetor auxiliar chamado aux, para ser usado para esse propósito. Eu até tentei criar vetores dentro da função intercala, mas isso deixou tudo bem lento, desse jeito a velocidade ficou um pouco melhor. Por último, mas bem legal, é que nesse caso, veja que temos três funções, uma que recebe e retorna tudo para o R, e outras duas que fazem o trabalho propriamente dito. Mas quando a gente olha no R, desse jeito a gente só vai ver a mergesortC, isso porque em cima dela tem escrito

// [[Rcpp::export]]

Isso faz com que a gente só veja ela, e não as funções auxiliares.

Concluído a construção da função em C++, agora é simples no R

> library(Rcpp) > sourceCpp("merge.cpp") > mergesortC(sample(1:10)) [1] 1 2 3 4 5 6 7 8 9 10

Basicamente, só damos um sourceCpp no arquivo com o código, podemos usar o argumento verbose=TRUE se quisermos acompanhar a compilação e ta tudo pronto para usar, e podemos ver que o mergesortC funciona certinho.

Agora a gente pode até medir o tempo que ele precisa para organizar, por exemplo, 1000 números inteiros, usando a função system.time.

> system.time(mergesortC(sample(1:1000))) usuário sistema decorrido 0.000 0.000 0.001

Alias, para ter uma noção de porque as pessoas continuaram inventando algorítimos de ordenação, a gente pode fazer uma comparação, entre o mergesort e o insertionsort por exemplo, e ver qual deles é o mais rápido, para organizar um vetor de um tamanho qualquer, é so a gente ficar bagunçando um vetor, com sample, e registar o tempo que ele leva para organizar, e repetir isso varias vezes.

dados<-data.frame(Tempo=rep(NA,1000),Algoritimo=rep(c("InsertionSort","MergeSort"),each=500)) for(i in 1:1000){ if(i<=500){ dados[i,1]<-system.time(insertionsortC(sample(1:10000)))[3] }else{ dados[i,1]<-system.time(mergesortC(sample(1:10000)))[3] } print(i) }

A gente cria então um dataframe para receber os dados, e faz o experimento, pegando o tempo total gasto no processo, o insertionsortC eu peguei do post passado.

O resultado disso é o seguinte.

01

É, o mergesort pode ser mais complicado de entender, e implementar, mas é muito mais rápido.

> aggregate(dados$Tempo, list(dados$Algoritimo), mean) Group.1 x 1 InsertionSort 0.043494 2 MergeSort 0.005362 > aggregate(dados$Tempo, list(dados$Algoritimo), sd) Group.1 x 1 InsertionSort 0.0044236978 2 MergeSort 0.0004933993

Ele é muitas vezes mais rápido, e varia muito menos no tempo de execução, não é a toa que o sort do R não usa o InsertionSort, mas ele também não usa o mergesort, ou seja, tem como melhorar ainda, mas essa vai ficar para a próxima porque ja está na hora de dormir.

Bem o script está aqui embaixo além do repositório recologia no github. Esse foi o primeiro código no Rcpp que envolvia mais de uma função, e no final muitas coisas envolvem varias funções, então acho que assim vamos abrindo portas para possibilidades legais. Outra coisa é que esse tipo de estratégia para resolver problemas, de partir o problema em partes menores, e resolver essas partes antes de resolver um problema maior, pode parecer algo longe para biologia, mas a gente vai pela mesma estrada em problemas como o de alinhamento de sequências. E vamos dormir.

library(Rcpp)
 
sourceCpp("merge.cpp",verbose=T)
 
mergesortC(sample(1:10))
 
system.time(mergesortC(sample(1:1000)))
 
cppFunction("
    NumericVector insertionsortC(NumericVector vetor) {
        int n = vetor.size();
 
        double aux;
        int i , j;
 
        for(i=1;i<n;i++) {
            aux=vetor[i];
            j=i-1;
            while(j>=0 && vetor[j]>aux) {
                vetor[j+1]=vetor[j];
                j=j-1;
                }
            vetor[j+1]=aux;
            }
        return vetor;
        }
")
 
dados<-data.frame(Tempo=rep(NA,1000),Algoritimo=rep(c("InsertionSort","MergeSort"),each=500))
 
for(i in 1:1000){
    if(i<=500){
        dados[i,1]<-system.time(insertionsortC(sample(1:10000)))[3]
    }else{
        dados[i,1]<-system.time(mergesortC(sample(1:10000)))[3]
    }
    print(i)
}
 
#Figura 1
boxplot(Tempo~Algoritimo,data=dados)
 
aggregate(dados$Tempo, list(dados$Algoritimo), mean)
aggregate(dados$Tempo, list(dados$Algoritimo), sd)

Insertionsort em R e C++ usando o pacote rcpp

Bem, depois de vermos o algorítimo mais simples que tem para ordenar um vetor, o bubble sort. Agora a gente vai olhar outro um pouco mais legal, esse se chama insertion sort.

A ideia é a seguinte:

Então a gente tem um vetor qualquer, com n elementos.
 C = \{X_1 , X_2 , X_3 , \dots , X_n  \}

E a gente quer que esses elementos fiquem assim:

 Regra = \{x_1 \leq x_2 \leq x_3 \leq \dots \leq x_n  \}

Como a gente faz?
Vamos supor um conjunto aqui.

 C = \{6, 5, 3, 1, 8, 7, 2, 4\}

Ele esta desorganizado porque ele não respeita nossa Regra_1. So olhar o primeiro elemento que é 6.

So que a estratégia aqui muda. O que a gente faz?
Primeiro pega um sub-vetor, um pedaço desse la em cima.

 C = \{6\}

Esse vetor está organizado? Sim, não temos ninguém para comparar. Um vetor de 1 elemento sempre está organizado.

Agora pegamos o segundo elemento, o 5.
Ai fazemos a pergunta onde ele deveria está?
Antes ou depois do 6?
Bem ele é menor que o 6 então tem que estar depois, então movemos o 6 um índice pra frente e dai colocamos o 5.

 C = \{5 ,6\}

Agora pegamos outro elemento, o 3, e repetimos o os passos anteriores.

Perguntamos, onde é a posição do 3?
Ele é menor que o 6? Sim então movemos o 6 um índice para a frente.
Ele é menor que o 5? Sim, então movemos o 5 um índice para a frente, como estamos na primeira casa do vetor, paramos. E ficamos com o seguinte.

 C = \{3 ,5 ,6\}

Notem que o que temos é que o inicio do vetor sempre esta organizado dessa forma, e sempre adicionamos um elemento a um vetor organizado. Mas se o elemento que formos adicionar deve ficar na ultima posição, a gente não vai mover nada de lugar, ou seja, vai estar tudo certo e teremos organizado com menos trocas de posição de elementos. Diferente do bubblesort, que tínhamos que comparar o vetor inteiro para garantir que o ultimo elemento é o maior, mas depois temos que refazer varias comparações para garantir que o segundo maior elemento é o penúltimo, ou seja nunca tinha como escapar de comparar tudo com tudo, aqui tem.

Mas talvez vendo uma animaçãozinha fica mais fácil de entender.

Insertion-sort-example-300px

Apesar de parecer complicado, esse é o jeito que a maioria das pessoas organiza cartas na mão, quando a gente quer deixar em alguma ordem. Veja so.

Ok, mas então como fica esse processo no R?

insertionsort<-function(vetor){
    n<-length(vetor)
 
    for(i in 2:n) {
        aux=vetor[i]
        j=i-1
        while(j>=1 && vetor[j]>aux) {
            vetor[j+1]<-vetor[j]
            j=j-1
            }
        vetor[j+1]=aux
        }
    return(vetor)
    }

Bem simples, um loop usando i diz qual o tamanho do vetor que já está organizado, veja que a gente começa do 2, ja que o índice 1 já está organizado, e ai é só salvar a ultima posição, usamos um while para quanto o auxiliar for menor que o valor no vetor ir empurrando ele para a frente e quando isso não é verdade, colocamos o valor que salvamos no auxiliar na posição desejada.

E esse processo funciona que uma beleza.

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

Podemos fazer isso também usando o Rcpp, mas ai é preciso lembrar, que na linguagem C e C++, diferente do R, os índices começam no 0 e não em 1, então o primeiro elemento de um vetor está na posição vetor[1] no R, mas esta na posição vetor[0] no C++.
Com isso em mente, o código é praticamente o mesmo.

library(Rcpp)
cppFunction("
    NumericVector insertionsortC(NumericVector vetor) {
        int n = vetor.size();
 
        double aux;
        int i , j;
 
        for(i=1;i<n;i++) {
            aux=vetor[i];
            j=i-1;
            while(j>=0 && vetor[j]>aux) {
                vetor[j+1]=vetor[j];
                j=j-1;
                }
            vetor[j+1]=aux;
            }
        return vetor;
        }
")

E funciona legal também.

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

Bem a gente vai ver daqui dois algorítimos de ordenação, se eu continuar fazendo isso, que o que a gente manda para o Rcpp, o código que está entre aspas, pode ser um arquivo texto com o código. E poderíamos mandar mais funções juntas, mas no quicksort a gente vai ver como organizar isso, por enquanto deixa desse jeito que é mais simples.

Mas outra forma ainda de implementar isso é com recursão. A gente ja usou recursão para resolver problemas no Rosalind. Mas basicamente é so chamar a mesma função dentro dela mesma. Um exemplo bem simples é o fatorial.

Fatorial é aquele número que multiplicamos por ele menos 1 até chegar a 1.
Assim,  3!=3 \cdot 2 \cdot 1 e 2 fatorial seria  2!=2 \cdot 1

Então outra forma de escrever isso é  3!=3 \cdot 2!. Fazendo isso até chegar no 1 fatorial, logo no R isso fica assim.

fatorial<-function(n) {
    if(n==1) {
        return(1)
        } else {
            return(n*fatorial(n-1))
            }
    }

Que da.

> fatorial(3) [1] 6

Ou seja, temos um caso base, que é o 1 e vamos fazendo alguma coisa até chegar nessa base.
O insertionsort pode seguir esse raciocínio também da seguinte forma:

cppFunction("
    NumericVector insertionsortRC(NumericVector vetor, int n) {
 
        double aux;
        int i;
 
        if(n>1) {
            insertionsortRC(vetor,n-1);
            aux=vetor[n-1];
            i=n-1;
            while(vetor[i-1]>aux && i>=0 ) {
                vetor[i]=vetor[i-1];
                i--;
                }
            vetor[i]=aux;
            }
 
        return vetor;
        }
    ")

Que funciona também

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

Agora eu so conseguir fazer o insertionsort recursivo fazendo uma função que recebe dois argumentos. Eu até perguntei no stack-overflow aqui se tinha como fazer de outra forma, mas não sei se é possivel, mas tudo funciona de qualquer forma.
Que descobri que não sabia fazer foi fazer o insertion sort de forma recursiva no R. Tem uma pergunta aberta aqui na lista brasilera de r r-br. Se alguém puder me explicar como faz, eu fico grato.

E bem eu acho que é isso, agora temos dois algorítimos de ordenação. Vamos adicionar mais alguns a essa lista e depois será divertido tentar analisar o quão bom cada um é, e quanto…

Bem o script está aqui embaixo além do repositório recologia no github. Até a próxima.

vetor<-sample(100)
vetor
 
insertionsort<-function(vetor){
    n<-length(vetor)
 
    for(i in 2:n) {
        aux=vetor[i]
        j=i-1
        while(j>=1 && vetor[j]>aux) {
            vetor[j+1]<-vetor[j]
            j=j-1
            }
        vetor[j+1]=aux
        }
    return(vetor)
    }
 
insertionsort(vetor)
 
library(Rcpp)
 
cppFunction("
    NumericVector insertionsortC(NumericVector vetor) {
        int n = vetor.size();
 
        double aux;
        int i , j;
 
        for(i=1;i<n;i++) {
            aux=vetor[i];
            j=i-1;
            while(j>=0 && vetor[j]>aux) {
                vetor[j+1]=vetor[j];
                j=j-1;
                }
            vetor[j+1]=aux;
            }
        return vetor;
        }
")
 
 
 
insertionsortC(vetor)
 
cppFunction("
    NumericVector insertionsortRC(NumericVector vetor, int n) {
 
        double aux;
        int i;
 
        if(n>1) {
            insertionsortRC(vetor,n-1);
            aux=vetor[n-1];
            i=n-1;
            while(vetor[i-1]>aux && i>=0 ) {
                vetor[i]=vetor[i-1];
                i--;
                }
            vetor[i]=aux;
            }
 
        return vetor;
        }
    ")
 
vetor
insertionsortRC(vetor,length(vetor))
 
fatorial<-function(n) {
    if(n==1) {
        return(1)
        } else {
            return(n*fatorial(n-1))
            }
    }
 
fatorial(3)

Bubblesort em R e C++ usando o pacote rcpp

Opa, a algum tempo atras eu estava olhando como usar funções escritas em C do R, aqui.

Mas como a gente viu la, é um tramite danado tudo isso, desde a parte de escrever o programa, compilar, etc.

Mas o mais complicado, é conseguir fazer a linguagem C entender como está organizado os dados que vem do R, e vice versa. Mas quem viu aquele post, também viu uma alma caridosa que postou no comentario sobre como fazer isso usando o pacote rcpp.

Bem, dando uma olhada como fazer as coisas, parece que nada é tão impraticável assim. Então como uma primeiro olhada, vamos olha um algorítimo chamado bubblesort feito direto no R e usando o rcpp.

Esse algorítimo entra numa categoria que acho que todo livro de algorítimos básico aborda, e realiza uma tarefa básica essencial, organiza um vetor em alguma ordem, aqui a ordem numérica.

Então a gente tem um vetor qualquer, com n elementos.
 C = \{X_1 , X_2 , X_3 , \dots , X_n  \}

E a gente quer que esses elementos fiquem assim:

 C = \{x_1 \leq x_2 \leq x_3 \leq \dots \leq x_n  \}

Ou seja, uma ordem crescente, eles vão ficar organizados dentro do vetor.

Como a gente consegue isso? A gente vai comparando o primeiro com o segundo, se o segundo for menor a gente troca os dois de lugares, senão a gente mantem eles nos mesmo lugares, depois comparamos o segundo com o terceiro, se for diferente trocamos de lugares esses dois, senão mantemos nos mesmo lugares, fazemos isso até chegar na comparação do ultimo com o penúltimo. Depois dessa comparação e troca se necessário, a gente pode fazer uma afirmação quanto a esse vetor, podemos dizer que o ultimo elemento é o maior elemento do vetor, ja que ele foi empurrado la pro fundo, a partir daqui da para pensar que se continuamos fazendo isso agora até o penúltimo, depois até o antepenúltimo, ao chegar na comparação que vai até o segundo termo, temos certeza que todo o vetor está organizado depois disso.

No fim do post tem uma animação para entender melhor, mas vamos ver como fica o código na linguagem R.

bubblesortR<-function(vetor) {
    aux<-numeric()
    for(i in 1:(length(vetor)-1)) {
        for(j in 1:(length(vetor)-i)) {
            if(vetor[j]>vetor[j+1]) {
                aux<-vetor[j]
                vetor[j]<-vetor[j+1]
                vetor[j+1]<-aux
                    }
                }
            }
        return(vetor)
 
    }

Então a gente recebe o vetor, ai veja que o primeiro loop, que usa i, ele vai até o fim do vetor, depois ele vem diminuindo, isso é o que diminuímos no segundo loop que usa j, e dentro desses dois loops tudo que a gente faz é comparar os pares de valores, e se j for menor que o próximo, a gente troca, senão não fazemos nada.

Mas mais fácil é testar a função, então se temos uma vetor desorganizado, com 100 números assim:

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

A função vai organizar eles e deixar assim:

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

Legal né, acontece que para fazer isso então, quanto mais números tivermos, mais operações temos que fazer e mais isso demora.

A gente pode na verdade medir o tempo no R usando a função system.time, fazendo algo como um experimento, sorteamos um vetor de números inteiros do tamanho que queremos e ordenamos ele, marcando quanto tempo demora, e a gente pode fazer isso para diferentes tamanhos e ver o que acontece, nesse caso a gente ve o seguinte.

> system.time(bubblesortR(sample(100))) usuário sistema decorrido 0.048 0.000 0.045 > system.time(bubblesortR(sample(1000))) usuário sistema decorrido 4.684 0.004 4.701 > system.time(bubblesortR(sample(5000))) usuário sistema decorrido 116.784 0.172 117.215

Mais ou menos, conforme aumentamos o número de elementos, aumentamos o tempo de execução, mas não linearmente, porque olha so, ao aumentarmos de 100 para 1000, aumentamos uma ordem de magnitude o tempo ali, mas quanto aumentamos em 5 vezes o número de elementos, aumentamos muito mais que 5 vezes o tempo.
Legal né, mas esse não é o foco ainda. Vamos olhar como fazer a mesma coisa no rcpp, usando código na linguagem c++.

library(Rcpp)
 
cppFunction("
    NumericVector bubblesortC(NumericVector vetor) {
        int n = vetor.size();
 
        double aux;
        int i , j;
 
        for(i=0;i<n-1;i++) {
            for(j=0;j<n-i-1;j++) {
                if(vetor[j]>vetor[j+1]) {
                    aux=vetor[j];
                    vetor[j]=vetor[j+1];
                    vetor[j+1]=aux;
                    }
                }
            }
        return vetor;
        }
")

Bem, o código é bem parecido, so a sintaxe do for que é diferente um pouco e temos que usar uma função para obter o tamanho do vetor, igual quando usamos length no R.
Se usarmos ele no mesmo vetor que criamos antes teremos o mesmo efeito

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

Certo, mas vamos olhar os tempos de execução para matar a curiosidade.

> system.time(bubblesortC(sample(100))) usuário sistema decorrido 0 0 0 > system.time(bubblesortC(sample(1000))) usuário sistema decorrido 0.004 0.000 0.004 > system.time(bubblesortC(sample(5000))) usuário sistema decorrido 0.084 0.000 0.087

São bem menores, isso porque é outra linguagem que é mais rápida que o R, mas como nada na vida é de graça, a gente paga o preço de tudo ser mais complexo de fazer. Complexo no sentido que, pelo menos eu, acho mais fácil escrever as coisas direto no R.

Mas quanto o tempo começar a se mostrar como um empecilho, vale a pensa pelo menos ter idea de soluções possíveis como essa. Existe um tutorial bem bacana aqui sobre como usar o Rcpp, além de um livro do próprio autor que está disponível, e foi publicado esse ano.

Outra coisa é que esse algorítimo é bem lento, mas é interessante pensar como ele funciona, como a descrição sempre é complexa para mim, eu fiz essa animação bem comum em todo post, livro ou sei la quem que está tentando entender o que esta acontecendo numa ordenação.

bubblesort

Bem o script esta aqui embaixo e no repositório recologia, e espero continuar lendo mais um pouco sobre Rcpp e colocando mais coisas aqui, mas aqui ja deu para ter uma ideia, e ver que é bem legal, ja que poupa todo o tramite como visto ao tentarmos usar a função .C
Além de quebrar o recesso sem postar nada, muitas provas ultimamente 🙁

library(Rcpp)
 
cppFunction("
    NumericVector bubblesortC(NumericVector vetor) {
        int n = vetor.size();
 
        double aux;
        int i , j;
 
        for(i=0;i<n-1;i++) {
            for(j=0;j<n-i-1;j++) {
                if(vetor[j]>vetor[j+1]) {
                    aux=vetor[j];
                    vetor[j]=vetor[j+1];
                    vetor[j+1]=aux;
                    }
                }
            }
        return vetor;
        }
")
 
bubblesortR<-function(vetor) {
    aux<-numeric()
    for(i in 1:(length(vetor)-1)) {
        for(j in 1:(length(vetor)-i)) {
            if(vetor[j]>vetor[j+1]) {
                aux<-vetor[j]
                vetor[j]<-vetor[j+1]
                vetor[j+1]<-aux
                    }
                }
            }
        return(vetor)
 
    }
 
vetor<-sample(100)
 
vetor
bubblesortR(vetor)
bubblesortC(vetor)
 
system.time(bubblesortR(sample(100)))
system.time(bubblesortR(sample(1000)))
system.time(bubblesortR(sample(5000)))
 
system.time(bubblesortC(sample(100)))
system.time(bubblesortC(sample(1000)))
system.time(bubblesortC(sample(5000)))
 
 
vetor<-sample(8)
 
#Animação
num<-1
aux<-vector()
resposta<-logical()
 
for(i in 1:(length(vetor)-1)) {
    for(j in 1:(length(vetor)-i)) {
        num<-num+1
        jpeg(sprintf("bubble%04d.jpg",num), width = 350, height = 350)
        cores<-rep("grey",8)
        cores[c(j,j+1)]<-"blue"
        resposta<-vetor[j]>vetor[j+1]
        barplot(vetor,names.arg = vetor,yaxt="n",col=cores,main=paste(vetor[j],"maior que", vetor[j+1],"?"))
        dev.off()
 
         if(vetor[j]>vetor[j+1]) {
             aux<-vetor[j]
             vetor[j]<-vetor[j+1]
             vetor[j+1]<-aux
             }
 
        num<-num+1
        jpeg(sprintf("bubble%04d.jpg",num), width = 350, height = 350)
        if(resposta==TRUE) {
            cores<-rep("grey",8)
            cores[c(j,j+1)]<-"red"
            barplot(vetor,names.arg = vetor,yaxt="n",col=cores,main=paste("Trocamos",vetor[j],"e", vetor[j+1],"de lugar"))
            }else{
                cores<-rep("grey",8)
                cores[c(j,j+1)]<-"blue"
                barplot(vetor,names.arg = vetor,yaxt="n",col=cores,main="Não trocamos nada")
                }
        dev.off()
        }
    }
 
system("convert -delay 90 bu*.jpg  bubblesort.gif")
system("rm bu*.jpg")