[R-br] "Ordenação Mergesort"

[Benilton Carvalho]

seu codigo nao e' reproduzivel...

e num momento de autruismo saiu o codigo abaixo:


merger <- function(left, right){
  res <- rep(NA, length(left)+length(right))
  i <- 1
  while (length(left) > 0 | length(right) > 0){
    if (length(left) > 0 & length(right) > 0){
      if (left[1] <= right[1]){
        res[i] <- left[1]
        left <- left[-1]
      } else {
        res[i] <- right[1]
        right <- right[-1]
      }
    } else if (length(left) > 0){
      res[i] <- left[1]
      left <- left[-1]
    } else if (length(right) > 0){
      res[i] <- right[1]
      right <- right[-1]
    }
    i <- i+1
  }
  return(res)
}

mergesort <- function(vec){
  if (length(vec) <= 1) return(vec)
  mid <- ceiling(length(vec)/2)
  left <- vec[1:mid]
  right <- vec[-(1:mid)]
  left <- mergesort(left)
  right <- mergesort(right)
  return(merger(left, right))
}


Em 13 de março de 2013 20:19, Jackeline Bonetti Campos
<jackebcampos em hotmail.com> escreveu:
> Olá!
> Procurei no fórum e não encontrei nenhum post a respeito desse tipo de
> ordenação.
> Esse algorítimo quebra o vetor de tamanho n em subvetores e se chama
> recursivamente até que os subvetores tenham tamanho 1.
> Depois, compara dois subvetores colando na posição 1 o subvetor menor e na
> posição 2 o subvetor maior.
> E depois volta a comparar os subvetores à direita e à esquerda até ter o
> vetor original ordenado.
>
> Estou implementando esse algoritmo porém, não estou conseguindo dividir o
> vetor até que length seja = 1.
>
> mergesort=function(x){ # Função que irá dividir o subvetor ao meio
>         subsort=function(y,z){ #Função que vai juntando ordenadamente as
> partes da entrada
>                 resultado=NULL
>
> tam=length(x) # Se a entrada tiver mais de um elemento, o algoritmo irá
> "quebrar" a entrada ao "meio" para ordenar individualmente cada entrada e
> depois juntar as metades já ordenadas
>         if(tamanho>1)
>              {
>                 meio= tam/2
>                 esq=c[1:flor(meio)]
>                 dit=c[(meio+1):tam]
>                 esq=mergesort(esq) #vou ter que ficar aplicando o mergesort
> até o vetor da esquerda ter um elemento.
>                 dit=mergesort(dit) #vou ter que ficar aplicando o mergesort
> até o vetor da direita ter um elemento
>                 if(esq[length(esq)]<=dit[1])  #se o vetor da esquerda do
> tamanho da esquerda (que deve ser um) for menor ou igual a 1
>                 {
>                         return(c(esq,dit))      #na hora de juntar o
> subvetor da esquerda fica primeiro.
>                 }
>                 else
>                 {
>                         subsort(esq,dit) #subsort é o vetor temporário.
>                 }
>         }
>         else  # Se a entrada for um único elemento não existe ordenação. Se
> TAM<1. devolve o elemento.
>         {
>                 return(x)
>         }
>
>
> Obrigada!
>
> Att,
> Jackeline
>
> _______________________________________________
> R-br mailing list
> R-br em listas.c3sl.ufpr.br
> https://listas.inf.ufpr.br/cgi-bin/mailman/listinfo/r-br
> Leia o guia de postagem (http://www.leg.ufpr.br/r-br-guia) e forneça código
> mínimo reproduzível.