Insertio short

An´lise de Algoritmos: a Melhor caso, pior caso, caso m´dio e
Fernando Lobo
Algoritmos e Estrutura de Dados II

1 / 25

Sum´rio a

Rever um problema e um algoritmo que j´ conhecem. a Descrevˆ-lo em pseudo-c´digo (como no livro). e o Come¸ar a usar a nota¸˜o assimpt´tica para descrever o c ca o tempo de execu¸˜o de algoritmos. ca

2 / 25

O problema de ordena¸˜o ca
Input: Uma sequˆncia de n n´meros a1 , a2 , . . . , an e u Output: Uma permuta¸˜o a1 , a2 , . . . , an da sequˆncia de ca e input tal que: a1 ≤ a2 ≤ . . . ≤ an Sequˆncia ´ tipicamente guardada num array. e e Exemplo:
Input: 8, 2, 4, 9, 3, 6 Output: 2, 3, 4, 6, 8, 9

3 / 25

Insertion Sort

Bom para ordenar um n´mero pequeno de elementos. u Funciona de modo an´logo ao modo como ordenamos uma a “m˜o”de cartas: a
Metemos as cartas na m˜o sempre ordenadas. a Ao recolhermos mais uma carta, inserimo-la na posi¸˜o ca correcta (para que as cartas na m˜o continuem ordenadas). a

4 / 25

Pseudoc´digo o (conven¸˜o: arrays come¸am na posi¸˜o 1) ca c ca

Insertion-Sort(A) 1 2 3 4 5 6 7 8 for j = 2 to length[A] key = A[j] / Insere A[j] na sequˆncia ordenada A[1 . . j − 1] / e i = j −1 while i > 0 and A[i] > key A[i + 1] = A[i] i = i −1 A[i + 1] = key

5 / 25

Exemplo

8 2 2 2 2 2

2 8 4 4 3 3

4 4 8 8 4 4

9 9 9 9 8 6

3 3 3 3 9 8

6 6 6 6 6 9

// // // // // //

input fim da fim da fim da fim da fim da

1a 2a 3a 4a 5a

itera¸~o ca itera¸~o ca itera¸~o ca itera¸~o ca itera¸~o ca

6 / 25

Correc¸˜o do algoritmo ca

c ca Invariante: No come¸o de cada itera¸˜o do ciclo for, o subarray A[1 . . j − 1] est´ ordenado. a Usamos o invariante para provar que o algoritmo funciona de modo correcto.

7 / 25

Correc¸˜o do algoritmo (cont.) ca

Temos de provar 3 coisas: 1. Inicializa¸˜o: Invariante ´ verdadeiro antes da 1a itera¸˜o. ca e ca 2. Manuten¸˜o: Se ´ verdadeiro no in´ de uma itera¸˜o, ca e ıcio ca mant´m-se verdadeiro no in´ da itera¸˜o seguinte. e ıcio ca a