Exercícios do Capítulo 8
bolha = function(v){
n = length(v)
for(j in 1:(n-1)){
for(i in 1:(n-j)){
if(v[i] > v[i+1]){
temp = v[i]
v[i] = v[i+1]
v[i+1] = temp
}
}
}
return(v)
}
vet = c(5,4,3,2,1)
bolha(vet)
## [1] 1 2 3 4 5
bolha_rec = function(v){
n = length(v)
if(n == 1) return(v)
for(i in 1:(n-1)){
if(v[i]>v[i+1]){
temp = v[i]
v[i] = v[i+1]
v[i+1] = temp
}
}
w = v[1:(n-1)]
wo = bolha_rec(w)
return(c(wo,v[n]))
}
bolha_rec(vet)
## [1] 1 2 3 4 5
bolha2 = function(v){
qtd = 0
n = length(v)
for(j in 1:(n-1)){
for(i in 1:(n-j)){
qtd = qtd + 1
if(v[i] > v[i+1]){
temp = v[i]
v[i] = v[i+1]
v[i+1] = temp
}
}
}
return(list(v,qtd))
}
vet = c(5,4,3,2,1)
bolha2(vet)
## [[1]]
## [1] 1 2 3 4 5
##
## [[2]]
## [1] 10
bolha_rec2 = function(v){
qtd = 0
n = length(v)
if(n == 1) return(list(v,qtd))
for(i in 1:(n-1)){
qtd = qtd + 1
if(v[i]>v[i+1]){
temp = v[i]
v[i] = v[i+1]
v[i+1] = temp
}
}
w = v[1:(n-1)]
wo = bolha_rec2(w)
return(list(c(wo[[1]],v[n]),qtd + wo[[2]]))
}
bolha_rec2(vet)
## [[1]]
## [1] 1 2 3 4 5
##
## [[2]]
## [1] 10
bolha3 = function(v){
qtd = 0
n = length(v)
for(j in 1:(n-1)){
for(i in 1:(n-j)){
if(v[i] > v[i+1]){
qtd = qtd + 1
temp = v[i]
v[i] = v[i+1]
v[i+1] = temp
}
}
}
return(list(v,qtd))
}
vet = c(5,4,3,2,1)
bolha3(vet)
## [[1]]
## [1] 1 2 3 4 5
##
## [[2]]
## [1] 10
bolha_rec3 = function(v){
qtd = 0
n = length(v)
if(n == 1) return(list(v,qtd))
for(i in 1:(n-1)){
if(v[i]>v[i+1]){
qtd = qtd + 1
temp = v[i]
v[i] = v[i+1]
v[i+1] = temp
}
}
w = v[1:(n-1)]
wo = bolha_rec3(w)
return(list(c(wo[[1]],v[n]),qtd + wo[[2]]))
}
bolha_rec3(vet)
## [[1]]
## [1] 1 2 3 4 5
##
## [[2]]
## [1] 10
bolha_rec_4 = function(v){
n = length(v)
if(n == 1) return(v)
for(i in 1:(n-1)){
if(v[i]>v[i+1]){
plot(v)
temp = v[i]
v[i] = v[i+1]
v[i+1] = temp
}
}
w = v[1:(n-1)]
wo = bolha_rec_4(w)
return(c(wo,v[n]))
}
v = c(5,4,3,2)
plot(bolha_rec_4(v))
# Os gráficos mostram como o algorítmo está ordenando os valores do vetor v.
# 1. Defina n = tamanho do vetor v;
# 2. Se n=1, retorne v;
# 3. Inicie i = 1;
# 4. Se v[i] < v[i+1], troque a posição i com posição i+1 no vetor v; (ATENÇÃO!)
# 5. Incremente: i = i + 1;
# 6. Se i <= n-1, volte para a linha 4;
# 7. Defina w = v[1:(n-1)];
# 8. Defina wo = OrdenaBolhaRec(w);
# 9. Retorne vo = (wo,v[n]).
bolha_desc_rec = function(v){
n = length(v)
if(n == 1) return(v)
for(i in 1:(n-1)){
if(v[i]<v[i+1]){
temp = v[i+1]
v[i+1] = v[i]
v[i] = temp
}
}
w = v[1:(n-1)]
wo = bolha_desc_rec(w)
return(c(wo,v[n]))
}
vet = c(1,5,4,3,2)
bolha_desc_rec(vet)
## [1] 5 4 3 2 1
quick_rec = function(v){
n = length(v)
if(n==1) return(v)
pivo = v[1]
i = 1
j = n
while(TRUE){
while(v[i] <= pivo && i < n){
i = i + 1
}
if(i == n && v[i] <= pivo){
v[1] = v[n]
v[n] = pivo
w=v[1:(n-1)]
wo = quick_rec(w)
return(c(wo,pivo))
}
while(v[j] > pivo){
j = j - 1
}
if(j == 1){
w=v[2:n]
wo = quick_rec(w)
return(c(pivo,wo))
}
if(j < i){
v[1] = v[j]
v[j] = pivo
we=v[1:(j-1)]
wd=v[(j+1):n]
weo = quick_rec(we)
wdo = quick_rec(wd)
return(c(weo,pivo,wdo))
}
aux = v[i]
v[i] = v[j]
v[j] = aux
}
}
vet = c(1,5,4,3,2)
quick_rec(vet)
## [1] 1 2 3 4 5
quick_rec2 = function(v){
n = length(v)
if(n==1) return(list(v,0))
qtd = 0
pivo = v[1]
i = 1
j = n
while(TRUE){
while(v[i] <= pivo && i < n){
i = i + 1
qtd = qtd + 1
}
qtd = qtd + 1
if(i == n && v[i] <= pivo){
v[1] = v[n]
v[n] = pivo
w=v[1:(n-1)]
wo = quick_rec2(w)
return(list(c(wo[[1]],pivo),qtd + wo[[2]]))
}
while(v[j] > pivo){
qtd = qtd + 1
j = j - 1
}
if(j == 1){
w=v[2:n]
wo = quick_rec2(w)
return(list(c(pivo,wo[[1]]),qtd + wo[[2]]))
}
qtd = qtd + 1
if(j < i){
v[1] = v[j]
v[j] = pivo
we=v[1:(j-1)]
wd=v[(j+1):n]
weo = quick_rec2(we)
wdo = quick_rec2(wd)
return(list(c(weo[[1]],pivo,wdo[[1]]),qtd + weo[[2]]+ wdo[[2]]))
}
aux = v[i]
v[i] = v[j]
v[j] = aux
}
}
vet = c(1,5,4,3,2)
quick_rec2(vet)
## [[1]]
## [1] 1 2 3 4 5
##
## [[2]]
## [1] 16
quick_rec3 = function(v){
n = length(v)
if(n==1) return(list(v,0))
qtd = 0
pivo = v[1]
i = 1
j = n
while(TRUE){
while(v[i] <= pivo && i < n){
i = i + 1
}
if(i == n && v[i] <= pivo){
qtd = qtd + 1
v[1] = v[n] #Troca
v[n] = pivo
w=v[1:(n-1)]
wo = quick_rec3(w)
return(list(c(wo[[1]],pivo),qtd + wo[[2]]))
}
while(v[j] > pivo){
j = j - 1
}
if(j == 1){
w=v[2:n]
wo = quick_rec3(w)
return(list(c(pivo,wo[[1]]),qtd + wo[[2]]))
}
if(j < i){
qtd = qtd + 1
v[1] = v[j] # Troca
v[j] = pivo
we=v[1:(j-1)]
wd=v[(j+1):n]
weo = quick_rec3(we)
wdo = quick_rec3(wd)
return(list(c(weo[[1]],pivo,wdo[[1]]),qtd + weo[[2]]+wdo[[2]]))
}
qtd = qtd + 1
aux = v[i] # Troca
v[i] = v[j]
v[j] = aux
}
}
vet = c(1,2,4,9,11,32,3)
quick_rec3(vet)
## [[1]]
## [1] 1 2 3 4 9 11 32
##
## [[2]]
## [1] 4
# 1. Defina n = tamanho do vetor v;
# 2. Se n=1, retorne v;
# 3. Defina pivo = v[1], i = 2 e j=n;
# 4. Se v[i] >= pivo e i < n, faça i = i + 1 e repete a linha 4;
# 5. Se i = n e v[i] >= pivo: troca o pivo com v[n]; defina w=v[1:(n-1)]; wo = OrdenaRapidoRec(w) e retorna c(wo,pivo).
# 6. Se v[j] < pivo, faça j = j - 1 e repete a linha 6.
# 7. Se j = 1: defina w=v[2:n]; wo = OrdenaRapidoRec(w) e retorna c(pivo,wo).
# 8. Se j < i: troca o v[j] com o pivo; defina we=v[1:(j-1)]; wd=v[j+1,n]; weo = OrdenaRapidoRec(we); wdo = OrdenaRapidoRec(wd); retorne c(weo,pivo,wdo).
# 9. Se i < j, troca o v[i] com o v[j] e volte para a linha 4;
quick_rec_desc = function(v){
n = length(v)
if(n==1) return(v)
pivo = v[1]
i = 1
j = n
while(TRUE){
while(v[i] >= pivo && i < n){ #Troquei
i = i + 1
}
if(i == n && v[i] >= pivo){ #Troquei
v[1] = v[n]
v[n] = pivo
w=v[1:(n-1)]
wo = quick_rec_desc(w)
return(c(wo,pivo))
}
while(v[j] < pivo){#Troquei
j = j - 1
}
if(j == 1){
w=v[2:n]
wo = quick_rec_desc(w)
return(c(pivo,wo))
}
if(j < i){
v[1] = v[j]
v[j] = pivo
we=v[1:(j-1)]
wd=v[(j+1):n]
weo = quick_rec_desc(we)
wdo = quick_rec_desc(wd)
return(c(weo,pivo,wdo))
}
aux = v[i]
v[i] = v[j]
v[j] = aux
}
}
vet2 = c(10,9,7,4,3,2,4,65,7,8,4,2,4,1)
quick_rec_desc(vet2)
## [1] 65 10 9 8 7 7 4 4 4 4 3 2 2 1
v<-c(1,3,5,5,4,0,-1,2,6,-2)
bolha_rec2(v) # Comparações para o método bolha
## [[1]]
## [1] -2 -1 0 1 2 3 4 5 5 6
##
## [[2]]
## [1] 45
bolha_rec3(v) # Trocas para o método bolha
## [[1]]
## [1] -2 -1 0 1 2 3 4 5 5 6
##
## [[2]]
## [1] 26
quick_rec2(v) # Comparações para o método rápido
## [[1]]
## [1] -2 -1 0 1 2 3 4 5 5 6
##
## [[2]]
## [1] 45
quick_rec3(v) # Trocas para o método rápido
## [[1]]
## [1] -2 -1 0 1 2 3 4 5 5 6
##
## [[2]]
## [1] 11
v<-c(10,9,8,7,6,5,4,3,2,1)
bolha_rec2(v) # Comparações para o método bolha
## [[1]]
## [1] 1 2 3 4 5 6 7 8 9 10
##
## [[2]]
## [1] 45
bolha_rec3(v) # Trocas para o método bolha
## [[1]]
## [1] 1 2 3 4 5 6 7 8 9 10
##
## [[2]]
## [1] 45
quick_rec2(v) # Comparações para o método rápido
## [[1]]
## [1] 1 2 3 4 5 6 7 8 9 10
##
## [[2]]
## [1] 58
quick_rec3(v) # Trocas para o método rápido
## [[1]]
## [1] 1 2 3 4 5 6 7 8 9 10
##
## [[2]]
## [1] 5
v<-c("fabio","ana","pedro","bruno","bruna","maria","clara","julia","vicente","daniel")
bolha_rec2(v) # Comparações para o método bolha
## [[1]]
## [1] "ana" "bruna" "bruno" "clara" "daniel" "fabio" "julia"
## [8] "maria" "pedro" "vicente"
##
## [[2]]
## [1] 45
bolha_rec3(v) # Trocas para o método bolha
## [[1]]
## [1] "ana" "bruna" "bruno" "clara" "daniel" "fabio" "julia"
## [8] "maria" "pedro" "vicente"
##
## [[2]]
## [1] 17
quick_rec2(v) # Comparações para o método rápido
## [[1]]
## [1] "ana" "bruna" "bruno" "clara" "daniel" "fabio" "julia"
## [8] "maria" "pedro" "vicente"
##
## [[2]]
## [1] 38
quick_rec3(v) # Trocas para o método rápido
## [[1]]
## [1] "ana" "bruna" "bruno" "clara" "daniel" "fabio" "julia"
## [8] "maria" "pedro" "vicente"
##
## [[2]]
## [1] 9