MO417 - Ata de exercícios resolvidos em aula

Aula de 12/03/2009, 5a feira

Livro: Algoritmos, Teoria e Prática - Tradução da 2a edição americana
Capítulo 2 - Conceitos básicos

Exercício 2.2-2:
Considere a ordenação de n números armazenados no arranjo A, localizando primeiro o menor elemento de A e permutando esse elemento com o elemento contido em A[1]. Em seguida, encontre o segundo menor elemento de A e o troque pelo elemento A[2]. Continue dessa maneira para os primeiros n-1 elementos de A.
  1. Escreva o pseudocódigo para esse algoritmo, conhecido como ordenação por seleção.
    Resposta: 
       
      SELECTION-SORT(A)
      for i ← 1 to comprimento[A]-1 do 
      	  menor ← i
      	  for j ← i+1 to n do
              if A[j] < A[menor] then
	          menor ← j
           trocar A[menor] ↔ A[menor]
  2. Que loop invariante esse algoritmo mantém?
    Resposta:
    A[1 .. i-1] está ordenado
    e
    A[i-1] ≤ A[i .. n]

  3. Por que ele só precisa ser executado para os primeiros n-1 elementos, e não para todos os n elementos?
    Resposta:
    O último elemento do arranjo A já será o maior e não precisa ser ordenado.

  4. Forneça os tempos de execução do melhor caso e do pior caso da ordenação por seleção em notação θ.
    Resposta:
    Pior Caso: θ(n2)
    Melhor Caso: θ(n2)

Autor(a): Danielle Furtado dos Santos