Ata de Resolução de Exercícios - QuickSort - 19/03/2003


7.1-2
Que valor de q PARTITION retorna quando todos os elementos no arranjo A[p..r] têm o mesmo valor? Modifique PARTITION de forma que q = (p + r)/2 quando todos os elementos no arranjo A[p..r] têm o mesmo valor.


Para o caso de todos os elementos serem iguais, o PARTITION incrementa r-p vezes o valor do índice i, pois nenhum elemento do vetor é maior que o pivô A[r]. Por tanto o valor retornado é (p-1) + (r-p) + 1, ou seja, r, o índice para o último elemento do vetor.

Abaixo está a versão modificada do PARTITION. O trecho acrescido, linhas de 2 a 8, verifica se todos os elementos são iguais ao pivô. Neste caso retorna (p+r)/2. Caso contrário, o algoritmo continua sua operação de forma idêntica ao PARTITION original. 
PARTITION(A, p, r)
1  x ← A[r]
2  tudoigual ← true               ; Início das modificações
3  for j ← p to r-1
4     do if A[j] ≠ x
5        then tudoigual ← false
6             break
7  if tudoigual = true
8     then return (p+r)/2          ; Fim das modificações
9  i ← p - 1
10 for j ← p to r - 1
11    do if A[j] ≤ x
12       then i ← i + 1 
13            trocar A[i] ↔ A[j]
14 trocar A[i+1] ↔ A[r]
15 return i + 1


7.1-3
Forneça um breve argumento mostrando que o tempo de execução de PARTITION sobre um subarranjo de tamanho n é Θ(n).


Na linha 3 do PARTITION, o for é executado de p até r-1, então percorre r-p elementos, ou seja, n-1.







7-3

Os professores Howard, Fine e Howard propuseram o seguinte algoritmo de ordenação "elegante":

STOOGE-SORT(A, i, j)
1 if A[i] > A[j]
2   then trocar A[i] ↔ A[j]
3 if i + 1 ≥ j
4   then return
5 k ← (j-i+1)/3                ; Arredonda para menos
6 STOOGE-SORT(A, i, j-k)
7 STOOGE-SORT(A, i+k, j)
8 STOOGE-SORT(A, i, j-k)




a.Mostre que, se n = comprimento[A], então STOOGE-SORT(A, 1, comprimento[A])
ordena corretamente o arranjo de entrada A[1..n].


b.Forneça uma recorrência para o tempo de execução no pior caso de STOOGE-SORT e um limite
assintótico restrito (notação Θ) sobre o tempo de execução no pior caso.


c.Compare o tempo de execução no pior caso de STOOGE-SORT com o da ordenação por inserção,
da ordenação por intercalação, de heapsort e de quicksort. Os professores merecem a estabilidade
no emprego?










a)
O funcionamento do STOOGE-SORT tem as seguintes características:


    

  •  Para arranjos de 1 ou 2 elementos fornecidos como entrada, retorna o arranjo ordenado. Propriedade observada nas linhas de 1 a 4.
    • 

  •  Após a primeira chamada recursiva (linha 6) os maiores elementos dos primeiros 2/3 do arranjo de entrada estarão localizados no segundo 1/3.
    • 

  •  Após a segunda chamada recursiva (linha 7) o último 1/3 do arranjo de entrada estará ordenado, e conterá os maiores elementos. Os menores elementos dos últimos 2/3 estarão localizados no segundo 1/3.
    • 

  •  Após a terceira chamada recursiva (linha 8) o STOOGE-SORT terá reordenado os primeiros 2/3, e com isto todo o arranjo de entrada estará ordenado.
    • 


Ou seja, o algoritmo ordena corretamente o arranjo de entrada.

    



b)
A recorrência para o STOOGE-SORT é T(n) = 3 T(2n/3) + O(1).


Aplicando o método mestre para: a = 3, b = 3/2 e f(n) = 1, constata-se que f(n) = O( nlog3/23 - ε ) + 1, por tanto se encaixa no primeiro caso do método.




Então o STOOGE-SORT tem limite assintótico restrito Θ( nlog3/23 ) para o pior caso.





c)
O limite assintótico do STOOGE-SORT foi calculado como sendo Θ(nk), com k = log3/23 > 2. Por tanto STOOGE-SORT é ω(n2) para o pior caso, garantidamente pior que qualquer dos algoritmos de ordenação citados.



Quanto à estabilidade dos professores, apesar da mancada, não devemos julgar sem avaliar melhor suas outras contribuições.









Disciplina: 
MO417 - Complexidade de Algoritmos I


Livro texto: 
Algoritmos : teoria e prática / Thomas H. Cormen... [et al.]; tradução da segunda edição [americana] - Rio de Janeiro : Campus, 2002


Redator: 
Bruno Cedraz Brandão   022245