O bubble sort recursivo pode ser pensado com o seguinte design: o array de entrada tem tamanho N (indexado de 0 a
). Caso o “pedaço” do array a ser ordenado tenha apenas 1 elemento então não faz nada. Caso contrário, o algoritmo “empurra” o maior elemento do “pedaço” considerado para o final e chama recursivamente considerando um pedaço menor (excluindo o último elemento).
a. Escreva o algoritmo
b. Qual seria a relação de recorrência desse algoritmo?
c. Qual o tempo do algoritmo segundo sua relação de recorrência.
5. O algoritmo odd-even sort é uma variação do bubble sort. Ele funciona através da comparação de todos os pares indexados com ímpar de elementos adjacentes. Se um par está na ordem errada (A[i] A[i+1] estão na ordem errada), os elementos são trocados. O próximo passo repete isso para os pares indexados com par de elementos adjacentes. E o algoritmo continua até que a entrada esteja ordenada. Você pode pensar no algoritmo como se a cada iteração um bubblesort é aplicado considerando índices ímpares e outro considerando índices pares (as trocas são feitas entre elementos
e
). Quando não houver mais trocas significa que o array está ordenado. Implemente o odd-even sort e calcule seu tempo de execução.
a. Escreva o algoritmo
b. Qual seria a relação de recorrência desse algoritmo?
c. Qual o tempo do algoritmo segundo sua relação de recorrência.
5. O algoritmo odd-even sort é uma variação do bubble sort. Ele funciona através da comparação de todos os pares indexados com ímpar de elementos adjacentes. Se um par está na ordem errada (A[i] A[i+1] estão na ordem errada), os elementos são trocados. O próximo passo repete isso para os pares indexados com par de elementos adjacentes. E o algoritmo continua até que a entrada esteja ordenada. Você pode pensar no algoritmo como se a cada iteração um bubblesort é aplicado considerando índices ímpares e outro considerando índices pares (as trocas são feitas entre elementos
Passo 1
O enunciado pede:
- (a) um algoritmo recursivo de Bubble Sort para ordenar um vetor
de tamanho , indexado de a . - (b) a relação de recorrência que expressa o tempo desse algoritmo.
- (c) a solução assintótica dessa recorrência.
Depois, pede que implementemos o algoritmo odd-even sort e calculemos seu tempo de execução.
Conteúdo: análise de algoritmos recursivos, recorrência, ordenação por trocas.
Passo 2
Escrevendo o Bubble Sort recursivo. A ideia é “empurrar” o maior elemento do pedaço
para
com um laço e depois ordenar recursivamente
.
Pseudocódigo (chamar inicialmente com ):
Pseudocódigo (chamar inicialmente com
procedure RecBubbleSort(A, m)
if m ≤ 0 then
return
end if
for i ← 0 to m-1 do
if A[i] > A[i+1] then
swap A[i] and A[i+1]
end if
end for
RecBubbleSort(A, m-1)
end procedure
Passo 3
Cada chamada faz um laço de tamanho
(ou seja,
) e depois chama recursivamente com o problema de tamanho
. Logo, a relação de recorrência é
com condição de contorno
.
Passo 4
Somando a contribuição de
até
obtemos
Portanto, o tempo de execução é
.
Passo 5
Odd-even sort intercaladamente faz passadas nos pares ímpares e pares até não haver mais trocas. Pseudocódigo:
procedure OddEvenSort(A, N)
repeat
swapped ← false
// fase ímpar: pares de índices (1,2), (3,4), …
for i ← 1 to N-2 step 2 do
if A[i] > A[i+1] then
swap A[i] and A[i+1]
swapped ← true
end if
end for
// fase par: pares de índices (0,1), (2,3), …
for i ← 0 to N-2 step 2 do
if A[i] > A[i+1] then
swap A[i] and A[i+1]
swapped ← true
end if
end for
until not swapped
end procedure
Passo 6
No pior caso, cada iteração (duas fases) faz
comparações e podem ser necessárias
iterações para propagar o maior elemento até o fim. Logo, o tempo total é
.
Resposta
a.
procedure RecBubbleSort(A, m)
if m ≤ 0 then return
for i ← 0 to m-1 do
if A[i] > A[i+1] then swap A[i],A[i+1]
end for
RecBubbleSort(A, m-1)
end procedure
b.
.
c. .
5.
c.
5.
procedure OddEvenSort(A,N)
repeat
swapped ← false
for i ← 1 to N-2 step 2 do … end for
for i ← 0 to N-2 step 2 do … end for
until not swapped
end procedure
Tempo:
.