2.1 – Ordenação por Inserção

meitcher

Um dos algoritmos clássicos para ordenação de um vetor é o insertion-sort, ele é parecido com o movimento que um jogador de cartas usa para ordenar as suas cartas. É um algoritmo eficiente para ordenar um número pequeno de elementos.

Exercícios:

2.1.1) Usando a Figura 2.2 como modelo, ilustre a operação de Insertion-Sort no arranjo A = {31, 41, 59, 26, 41, 58}.

31 41 59 26 41 58
26 31 41 59 41 58
26 31 41 41 59 58
26 31 41 41 58 59

 

2.1.2) Reescreva o procedimento Insertion-Sort para ordenar em ordem não crescente, em vez da ordem não decrescente.

  1. Insertion-Sort-Reverse(A)
  2. for j=2 to A.comprimento
  3. chave = A[j]
  4. i = j-1
  5. while i > 0 and A[i] < chave
  6. A[i+1] = A[i]
  7. i = i-1
  8. A[i+1] = chave

 

2.1.3) Considere o problema de busca:

Entrada: Uma sequência de números A = {a1, a2, …, an} e um valor v .
Saída: Um índice i tal que v = A[i] ou o valor especial NIL, se v não aparecer em A.

Escreva um pseudocódigo para busca linear, que faça a varredura da sequência, procurando por v. Usando um invariante de laço, prove que seu algoritmo é correto. Certifique-se que seu invariante de laço satisfaz as três propriedades necessárias.

  1. Busca-Linear(A, v)
  2. for i=1 to A.comprimento
  3. if A[i] == v
  4. return i
  5. return NIL

Invariante de laço: No começo de cada iteração i, o elemento A[j] != v, para todo j < i.

1. Inicialização: Quando i=1, não há possíveis elementos no vetor A[1 .. j], sendo assim, A[j] != v

2. Manutenção: Na iteração i+1, se A[j] fosse igual a v, não teria ido para essa iteração, retornando o j.

3. Término: Se A[i] = v, então irá retorna o i, senão já passou por todo o vetor e não encontrou um j, tal que A[j] = v, retornando NIL.

 

2.1.4) Considere o problema de somar dois inteiros binários de n bits, armazenados em dois arranjos de n elementos A e B. A soma dos dois inteiros deve ser armazenada em forma binária em um arranjo de (n+1) elementos C. Enuncie o problema formalmente e escreva o pseudocódigo para somar os dois inteiros.

Faça a soma de dois binários representados nos arranjos A[0 .. n-1], B[0 .. n-1] e armazene no arranjo C[0 .. n], onde o bit menos significativo fica no último índice dos arranjos.

  1. Soma-De-Binarios(A, B, n)
  2. C = [0 for i in range(n+1)]
  3. for i=n downto 1
  4. soma = C[i] + A[i-1] + B[i-1]
  5. C[i] = soma % 2
  6. C[i-1] = floor(soma/2)
  7. return C

 

O último exercício pode ser resolvido simplesmente utilizando a lógica que é feita para somar dois binários quaisquer.

Implementações em python desses exercícios no github: https://github.com/meitcher/mtcblog/blob/master/CLRS/Cap2/exercicios_2_1.py

 

Referências:

[1] CORMEN, T.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Introdução à Algoritmos (Terceira Edição). MIT Press and McGraw-Hill. 2009.

 

 

Deixe um comentário