O bubble sort recursivo pode ser pensado com o seguinte design: o array de entrada tem tamanho N (indexado de 0 a \mathrm{N}-1 ). 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 A[i] e A[i+1] ). Quando não houver mais trocas significa que o array está ordenado. Implemente o odd-even sort e calcule seu tempo de execução.

Passo 1

O enunciado pede:
  • (a) um algoritmo recursivo de Bubble Sort para ordenar um vetor A de tamanho N, indexado de 0 a N-1.
  • (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 A[0..m] para A[m] com um laço e depois ordenar recursivamente A[0..m-1].
Pseudocódigo (chamar inicialmente com m=N-1):
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 m (ou seja, \Theta(m)) e depois chama recursivamente com o problema de tamanho m-1. Logo, a relação de recorrência é
T(m) = T(m-1) + \Theta(m),
com condição de contorno T(0)=\Theta(1).

Passo 4

Somando a contribuição de m = 1 até N-1 obtemos
T(N-1)=\sum_{k=1}^{N-1}\Theta(k)=\Theta\bigl((N-1)N/2\bigr)=\Theta(N^2).
Portanto, o tempo de execução é \Theta(N^2).

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 \Theta(N) comparações e podem ser necessárias \Theta(N) iterações para propagar o maior elemento até o fim. Logo, o tempo total é \Theta(N)\times\Theta(N)=\Theta(N^2).

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. T(m)=T(m-1)+\Theta(m).
c. T(N)=\Theta(N^2).
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: \Theta(N^2).

Exercícios relacionados