[R-br] "Ordenação Mergesort"
Jackeline Bonetti Campos
jackebcampos em hotmail.com
Quinta Março 14 18:32:17 BRT 2013
Meu código está rodando, porém não está ordenando corretamente.
Será que alguem consegue achar o erro?
Segue abaixo:
semisort=function(y,z) #Função que vai juntando dois vetores que estão ordenados{ resultado=c(NA,length(y)+length(z)) 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) #VET FALTANTE. 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=floor(tam/2) esq=vet[1:meio] dit=vet[(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"
> >>
> >> 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.
> >> >> >
> >> >> > 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
> >> >> > }
> >> >> > tamanho=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 elemento, 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?
> >> >> >>
> >> >> >>
> >> >> >> _______________________________________________
> >> >> >> 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.
> >
> > _______________________________________________
> > 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/20130315/8f72d823/attachment.html>
Mais detalhes sobre a lista de discussão R-br