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

Benilton Carvalho beniltoncarvalho em gmail.com
Quinta Março 14 22:49:05 BRT 2013 

É uma linha de comando que terei prazer em dizer quando estiver num post
"próprio", no sentido de não invadir um outro assunto. ;-)
On Mar 14, 2013 9:16 PM, <andrebvs em bol.com.br> wrote:

> Em que situações essa rotina é interessante?
>
> Aproveitando o gancho, gostaria de saber como posso eliminar de uma matrix
> vetores repetidos, no exemplo abaixo, a linha1 e a linha5 são iguais,
> gostaria que houvesse uma outra matrix ou dataframe com apenas as linhas
> não repetidas.
>
> Seja a matrix 6x4:
>
> linha1 <- 1,2,4,5
> linha2 <- 7,2,1,5
>  linha3 <- 9,3,1,5
> linha4 <- 6,2,1,5
>  linha5 <- 5,2,1,4
> linha6 <- 9,2,1,5
>
> desde já agradeço!
>
> *Att.*
> *André*
>
>
> ------------------------------
> Em 14/03/2013 19:39, *Jackeline Bonetti Campos < jackebcampos em hotmail.com>
> * escreveu:
>  Consegui!
>
> Vou postar o código para caso alguém precise.
>
> Segue abaixo:
>
>  semisort=function(y,z) #Função que vai juntando dois vetores que estão
> ordenados
> {
>   resultado=NULL
>   tam_y=length(y)
>   tam_z=length(z)
>
>   i=1
>   while(tam_y>0 && tam_z>0) # Enquanto tiver elemento nos dois subvetores
>   {
>         if(y[1]<=z[1])       # se o primeiro elemento do subvetor a
> esquerda for menor que o primeiro elemento do subvetor a direita.
>         {
>             resultado[i]=y[1] #o resultado vai ser o elemento do vetor.
>             y=y[-1] # Tira o primeiro elemento do vetor, já que ele já foi
> adicionado ao resultado
>             tam_y=tam_y-1
>         }
>         else
>         {
>           resultado[i]=z[1]      # Se o primeiro elemento do vetor z for
> menor que o de y.
>           z=z[-1]
>           tam_z=tam_z-1                 #tira o primeiro elemento do
> vetor, já que ele já foi adicionado ao resultado
>         }
>         i<-i+1
>   }
>
>   if(tam_y==0)
>   {
>     resultado<-c(resultado,z)
>   }else
>   {
>     resultado<-c(resultado,y)
>   }
>
>     return(resultado) # Retorna o resultado ordenado
> }
>
> mergesort=function(vet)  # Função que irá dividir o subvetor ao meio
> {
>   tam=length(vet)     #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
>
>   cat("chamada: mergesort(",vet,")","\n")
>
>   if(tam>1)
>   {
>     meio=(tam/2)
>     esq=vet[1:floor(meio)]
>     dit=vet[floor(meio+1):tam]
>     esq=mergesort(esq)
>     dit=mergesort(dit)
>     vet_ord=semisort(esq,dit)
>     return(vet_ord)
>   }
>   else   # Se a entrada for um unico elemento não existe ordenação. Se
> TAM<1. devolve o elemento.
>   {
>      return(vet)
>   }
> }
>
>
> > From: beniltoncarvalho em gmail.com
> > Date: Thu, 14 Mar 2013 15:21:12 -0300
> > To: r-br em listas.c3sl.ufpr.br
> > Subject: Re: [R-br] "Ordenação Mergesort"
> >
> > vc precisa explicar como vc esta' executando a funcao... comigo ela
> > funciona como deveria:
> >
> > x = rnorm(10)
> > mergesort(x)
> >
> >
> > Em 14 de março de 2013 15:10, Jackeline Bonetti Campos
> > <jackebcampos em hotmail.com> escreveu:
> > > Entendi.
> > > Porém , quando eu executo a função mergesort diz "vec não encontrado".
> > > Porque será?
> > >
> > > Att,
> > > Jackeline.
> > >
> > >> From: beniltoncarvalho em gmail.com
> > >> Date: Thu, 14 Mar 2013 13:56:40 -0300
> > >
> > >> To: r-br em listas.c3sl.ufpr.br
> > >> Subject: Re: [R-br] "Ordenação Mergesort"
> > >>
> > >&gt ; exato, eu uso o i+1 p nao ter q ficar redimensionando o vetor a
> todo
> > >> momento...
> > >>
> > >> Em 14 de março de 2013 13:50, Jackeline Bonetti Campos
> > >> <jackebcampos em hotmail.com> escreveu:
> > >> > Verdade..
> > >> > Vou separar em duas funções e fazer as chamadas recursivas e ver se
> da
> > >> > certo!
> > >> > Ta muito parecido com o seu. A maior diferença é na resposta.
> > >> > A sua você criou um vetor do tamanho do vetor original e a partir
> que
> > >> > foram
> > >> > surgindo os menores valores você adotou i=1+i.
> > >> > Correto?
> > >> >
> > >> > Obrigada novamente!
> > >> >
> > >> >
> > >> >> From: beniltoncarvalho em gmail.com
> > >> >> Date: Thu, 14 Mar 2013 13:12:49 -0300
> > >> >> To: r-br em listas.c3sl.ufpr.br
> > >> >
> > >> >> Subject: Re: [R-br] "Ordenação Mergesort"
> > >> >>
> > >> >> Pela "cara" do codigo, tudo o que vc precisa e' separar o codigo em
> > >> >> duas funcoes... veja no que eu te mandei, que o mergesort chama ele
> > >> >> proprio... e a ultima coisa e' fazer a ordenacao.
> > >> >>
> > >> >> Em 14 de março de 2013 12:37, Jackeline Bonetti Campos
> > >> >> <jackebcampos em hotmail.com> escreveu:
> > >> >> > Olá Elias.
> > >> >> > É o merge sort.
> > >> >> >
> > >> >> > Benilton Carvalho,obrigada!
> > >> >> > Vou olhar a sua implementação.
> > >> >> > Não mandei o código inteiro. Somente a parte que está dando erro.
> &g t; >> >> >
> > >> >> > Segue abaixo o código todo:
> > >> >> >
> > >> >> > mergesort=function(x){ # Função que irá quebrar a entrada ao meio
> > >> >> > cada
> > >> >> > vez
> > >> >> > que for acionada
> > >> >> > semisort=function(y,z){ #Função que vai juntando ordenadamente as
> > >> >> > partes da entrada
> > >> >> > resultado=NULL
> > >> >> > while(length(y)>0 & length(z)>0){ # Enquanto tiver elemento
> > >> >> > nos dois subvetores
> > >> >> > if(y[1]<=z[1]){ # se o primeiro elemento do subvetor
> > >> >> > a esquerda for menor que o primeiro elemento do subvetor a
> direita
> > >> >> > resultado=c(resultado,y[1])
> > >> >> > y= y[-1] # Tira o primeiro elemento do vetor,
> > >> >> > já que ele já foi adicionado ao resultado
> > >> >> > }
> > >> >> > else{
> > >> >> > resultado=c(resultado,z[1])
> > >> >> > z=z[-1]
> > >> >> > }
> > >> >> > }
> > >> >> > if(length(y)>0){ # A partir do momento que acaba os
> > >> >> > elementos em uma das metades, me resta "copiar" o que sobrou da
> outra
> > >> >> > metade
> > >> >> > resultado=c(resultado,y)
> > >> >> > }
> > >> >> > if(length(z)>0){
> > >> >> > resultado=c(resultado,z)
> > >> >> > }
> > >> >> > return(resultado) # Retorna o resultado ordenado
> > >> >> > }
> > >> >> > tam anho=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= tamanho/2
> > >> >> > esq=x[1:floor(meio)]
> > >> >> > dit=x[floor(meio+1):tamanho]
> > >> >> > esq=mergesort(esq)
> > >> >> > dit=mergesort(dit)
> > >> >> > if(esq[length(esq)]<=dit[1]){
> > >> >> > return(c(esq,dit))
> > >> >> > }
> > >> >> > else{
> > >> >> > semisort(esq,dit)
> > >> >> > }
> > >> >> > }
> > >> >> > else{ # Se a entrada for um unico ele mento, a ordenação dela é
> > >> >> > trivial
> > >> >> > return(x)
> > >> >> > }
> > >> >> > }
> > >> >> >
> > >> >> > Att,
> > >> >> > Jackeline.
> > >> >> >
> > >> >> >
> > >> >> >> From: eliaskrainski em yahoo.com.br
> > >> >> >> To: r-br em listas.c3sl.ufpr.br
> > >> >> >> Date: Thu, 14 Mar 2013 16:27:03 +0100
> > >> >> >> Subject: Re: [R-br] "Ordenação Mergesort"
> > >> >> >
> > >> >> >>
> > >> >> >> Curiosidade: Esse algoritmo e' o quick sort?
> > >> >> >>
> > >> >> >>
> > >> >> >> _______________________________________________
> > >> &gt ;> >> 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.
> > >> >> >
> > >> >> > _______________________________________________
> > >> >> > 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.
> > >> >> _______________________________________________
> > >> >> R-br mai ling 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.
> > >> >
> > >> > _______________________________________________
> > >> > 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.
> > >> _______________________________________________
> > >> 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.
> > >
> > > _______________________________________________
> > > 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.
> > _______________________________________________
> > 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.
>
>
> _______________________________________________
> 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.
>
-------------- Próxima Parte ----------
Um anexo em HTML foi limpo...
URL: <http://listas.inf.ufpr.br/pipermail/r-br/attachments/20130314/d9e81b80/attachment.html>

Mais detalhes sobre a lista de discussão R-br