"Ordenação Mergesort"
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
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@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@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.
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@yahoo.com.br To: r-br@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@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.
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@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@yahoo.com.br To: r-br@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@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@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.
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@gmail.com Date: Thu, 14 Mar 2013 13:12:49 -0300 To: r-br@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@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@yahoo.com.br To: r-br@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@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@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@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.
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@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@gmail.com Date: Thu, 14 Mar 2013 13:12:49 -0300 To: r-br@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@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@yahoo.com.br To: r-br@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@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@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@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@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.
Entendi.Porém , quando eu executo a função mergesort diz "vec não encontrado".Porque será? Att,Jackeline.
From: beniltoncarvalho@gmail.com Date: Thu, 14 Mar 2013 13:56:40 -0300 To: r-br@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@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@gmail.com Date: Thu, 14 Mar 2013 13:12:49 -0300 To: r-br@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@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@yahoo.com.br To: r-br@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@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@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@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@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@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.
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@hotmail.com> escreveu:
Entendi. Porém , quando eu executo a função mergesort diz "vec não encontrado". Porque será?
Att, Jackeline.
From: beniltoncarvalho@gmail.com Date: Thu, 14 Mar 2013 13:56:40 -0300
To: r-br@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@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@gmail.com Date: Thu, 14 Mar 2013 13:12:49 -0300 To: r-br@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@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@yahoo.com.br To: r-br@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@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@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@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@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@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@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.
Mas nesse caso o vec seria o vetor que você quer ordenar...coloco vec=(c(NA,de tamanho qualquer?)
From: beniltoncarvalho@gmail.com Date: Thu, 14 Mar 2013 15:21:12 -0300 To: r-br@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@hotmail.com> escreveu:
Entendi. Porém , quando eu executo a função mergesort diz "vec não encontrado". Porque será?
Att, Jackeline.
From: beniltoncarvalho@gmail.com Date: Thu, 14 Mar 2013 13:56:40 -0300
To: r-br@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@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@gmail.com Date: Thu, 14 Mar 2013 13:12:49 -0300 To: r-br@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@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@yahoo.com.br > To: r-br@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@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@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@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@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@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@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@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.
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@gmail.com Date: Thu, 14 Mar 2013 15:21:12 -0300 To: r-br@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@hotmail.com> escreveu:
Entendi. Porém , quando eu executo a função mergesort diz "vec não encontrado". Porque será?
Att, Jackeline.
From: beniltoncarvalho@gmail.com Date: Thu, 14 Mar 2013 13:56:40 -0300
To: r-br@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@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@gmail.com Date: Thu, 14 Mar 2013 13:12:49 -0300 To: r-br@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@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@yahoo.com.br > To: r-br@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@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@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@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@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@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@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@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.
Quando eu peço para ordenar o vetor [3,1,6,7,9,3]obtenho como resposta o vetor [1,2,3,3,2,6,7,9] Aparece esses "2".. Não sei da onde =S
From: beniltoncarvalho@gmail.com Date: Thu, 14 Mar 2013 15:21:12 -0300 To: r-br@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@hotmail.com> escreveu:
Entendi. Porém , quando eu executo a função mergesort diz "vec não encontrado". Porque será?
Att, Jackeline.
From: beniltoncarvalho@gmail.com Date: Thu, 14 Mar 2013 13:56:40 -0300
To: r-br@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@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@gmail.com Date: Thu, 14 Mar 2013 13:12:49 -0300 To: r-br@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@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@yahoo.com.br > To: r-br@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@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@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@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@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@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@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@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.
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@gmail.com Date: Thu, 14 Mar 2013 15:21:12 -0300 To: r-br@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@hotmail.com> escreveu:
Entendi. Porém , quando eu executo a função mergesort diz "vec não encontrado". Porque será?
Att, Jackeline.
From: beniltoncarvalho@gmail.com Date: Thu, 14 Mar 2013 13:56:40 -0300
To: r-br@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@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@gmail.com Date: Thu, 14 Mar 2013 13:12:49 -0300 To: r-br@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@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@yahoo.com.br > To: r-br@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@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@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@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@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@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@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@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.
É 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@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@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@gmail.com Date: Thu, 14 Mar 2013 15:21:12 -0300 To: r-br@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@hotmail.com> escreveu:
Entendi. Porém , quando eu executo a função mergesort diz "vec não encontrado". Porque será?
Att, Jackeline.
From: beniltoncarvalho@gmail.com Date: Thu, 14 Mar 2013 13:56:40 -0300
To: r-br@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@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@gmail.com Date: Thu, 14 Mar 2013 13:12:49 -0300 To: r-br@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@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@yahoo.com.br >> To: r-br@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@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@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@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@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@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@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@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@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.
participantes (4)
-
andrebvs＠bol.com.br -
Benilton Carvalho -
Elias Teixeira Krainski -
Jackeline Bonetti Campos