Algoritmos ESTG – IPPortalegre Curso Programadores de Informática Luís Baptista 2016

Algoritmos

ESTG – IPPortalegreCurso Programadores de Informática

Luís Baptista2016

2

O que é um algoritmo?• Um algoritmo é uma sequência de instruções, não ambíguas, para resolver um problema,

i.e., para obter o output correto para qualquer input, numa quantidade de tempo finita.– Um algoritmo tem que ser preciso, efectivo, e tem que terminar.– Para especificar um algoritmo: pseudocódigo e fluxogramas.– Programa: algoritmo escrito de forma a ser executado por um computador (linguagem de programação).

Algoritmos

Exemplos

• Instruções de montagem de um qualquer kit• Receita (depende…)• Programa de computador

Luís Baptista, PI/Algoritmos, 2016

problema

algoritmo

computadorinput output

3

Exemplos:

• Algoritmo de Euclides (mdc)– Calcule o máximo divisor comum entre 2 número: mdc(m,n)

• Contadores– Mostrar números de 0 a 100.

• Acumuladores– Somar números de 0 a 100.

Algoritmos


Pseudocódigo e Fluxogramas

4

Analisar um algoritmo

• Tempo (eficiência em termos de tempo)• Espaço (eficiência em termos de memória necessária)• Outras características importantes:

– Simplicidade e Generalidade

Algoritmos


Notação big oh - exemplos • Ciclo for – crescimento linear O(n)• For dentro de FOR – crescimento quadrático O(n2)

5

Definições

• Pretende-se ordenar ficheiros• Que contêm registos• Considerando uma chave

Métodos Elementares de Ordenação

Exemplo10222 Maria Silva EI 950 123 123 Portalegre10111 João Martins EC 940 111 222 Lisboa9044 António Ribeiro EI 950 999 888 Setúbal8300 João Silva EERA 950 111 222 Coimbra11001 Margarida Gil Bio 930 333 321 Portalegre9991 Luís Moreira EC 950 000 010 Lisboa10300 Rosa Matos Bio 940 444 888 Portalegre

ficheiroregisto

chave

10222 Maria Silva EI 950 123 123 Portalegre10111 João Martins EC 940 111 222 Lisboa9044 António Ribeiro EI 950 999 888 Setúbal8300 João Silva EERA 950 111 222 Coimbra11001 Margarida Gil Bio 930 333 321 Portalegre9991 Luís Moreira EC 950 000 010 Lisboa10300 Rosa Matos Bio 940 444 888 Portalegre

O que é Ordenar ?• Re-arranjar a sequência de registos do ficheiro segundo a

ordem ascendente das chaves• Envolve comparar e mover (trocar…) item’s (registos)

– Para item’s muito grandes, utilizar array de ponteiro(ordenação indirecta)


6

Estabilidade

• Um algoritmos de ordenação é estável quando mantém a ordem relativas dos Item’s com chaves iguais.


FCNIAHOARTO AACFHINOORT

• Provar a estabilidade exige formulação matemática (!)• Para provar a não estabilidade basta apresentar um caso

• FAZER: Ordenação do Excel é estável?– Abrir um ficheiro com informação que contenha várias colunas;– Ordenar por uma das colunas (coluna A);– Ordenar por outra coluna (coluna B);– O que acontece à coluna A, nos casos em que existem elementos repetidos?


7

EstabilidadeMétodos Elementares de Ordenação

• Queremos ordenar por várias chaves (sub-ordenações)• Consideremos que temos registos de alunos e queremos:

– Ordenar por localidade– E dentro de cada localidade, por nome

• Utilizando um algoritmo estável:– Ordenar por nome– Ordenar por localidade

• Existem muitos registos com a mesma localidade• Vão ficar juntos, mantendo a ordem anterior (por nome)

Exemplo da importância da estabilidade

•Podemos tornar qualquer algoritmo de ordenação estável?–Sim, adicionando à chave informação da sua posição


8

OrdenarMétodos Elementares de Ordenação

Como ordenar a seguinte sequência de letras?

E A S Y Q U E S T I O N

• FAZER…


9

Bubble SortMétodos Elementares de Ordenação

void bubble(Item a[], int l, int r){ int i, j; for (i = l; i < r; i++) for (j = r; j > i; j--) compexch(a[j-1], a[j]);}

• Troca os elementos adjacentes que estão fora de ordem• Até estarem todos ordenados7 6 3 9 4 2 5 1 6 8 4 3 6 4 9 7

7 6 3 9 4 2 5 1 6 8 4 3 6 4 7 9

7 6 3 9 4 2 5 1 6 8 4 3 4 6 7 9

7 6 3 9 4 2 5 1 6 8 3 4 4 6 7 9

7 6 3 9 4 2 5 1 6 3 8 4 4 6 7 9

7 6 3 9 4 2 5 1 3 6 8 4 4 6 7 9

7 6 3 9 4 2 1 5 3 6 8 4 4 6 7 9

7 6 3 9 4 1 2 5 3 6 8 4 4 6 7 9

7 6 3 9 1 4 2 5 3 6 8 4 4 6 7 9

7 6 3 1 9 4 2 5 3 6 8 4 4 6 7 9

7 6 1 3 9 4 2 5 3 6 8 4 4 6 7 9

7 1 6 3 9 4 2 5 3 6 8 4 4 6 7 9

1 7 6 3 9 4 2 5 3 6 8 4 4 6 7 9


10

OrdenarMétodos Elementares de Ordenação

Ordene a seguinte sequência de letras usando o bubble sort

E A S Y Q U E S T I O N

• FAZER…– Apresentando as várias interacções resultantes da execução do

algoritmo.


11

Selection SortMétodos Elementares de Ordenação

void selection(Item a[], int l, int r){ int i, j; for (i = l; i < r; i++) { int min = i; for (j = i+1; j <= r; j++) if (less(a[j], a[min])) min = j; exch(a[i], a[min]); }}

• Encontrar o menor elementono array e trocá-lo com o da1º posição

• Encontrar o segundo menorelemento no array e trocá-locom o da 2º posição

• Repetir o mesmo processo até ao fim do array

7 6 3 9 4 2 5 1 6 8 4 3 6 4 9 7

1 6 3 9 4 2 5 7 6 8 4 3 6 4 9 7

1 2 3 9 4 6 5 7 6 8 4 3 6 4 9 7


12

Insertion SortMétodos Elementares de Ordenação

void insertion(Item a[], int l, int r){ int i, j; for (i = l+1; i <= r; i++) for (j = i; j > l; j--) compexch(a[j-1], a[j]);}

• Considerar os elementos um de cada vez e inseri-los na posição correcta

• Mover os elementos maiores para a direita, para fazer espaço para inserir o elemento na posição deixada vazia

2 3 4 6 7 9 5 1 6 8 4 3 6 4 9 7

2 3 4 5 6 7 9 1 6 8 4 3 6 4 9 7


13


Key-Indexed Sort

• Consideremos N Item’s• Onde as chaves (keys) são elementos distintos entre 0 e N-1• Resolução directa utilizando um array temporário e sem

necessidade de comparações.for(i=0; i<N; i++) b[key(a[i])] = a[i];

• É um algoritmos de ordenação de tempo linear– Desde que as chaves esteja dentro de um factor constantes de Nvoid distcount(int a[], int l, int r){ int i, j, cnt[M], b[maxN]; for (j = 0; j < M; j++) cnt[j] = 0; for (i = l; i <= r; i++) cnt[a[i]+1]++; for (j = 1; j < M; j++) cnt[j] += cnt[j-1]; for (i = l; i <= r; i++) b[cnt[a[i]]++] = a[i]; for (i = l; i <= r; i++) a[i] = b[i];}


14

Insertion Sort - OptimizaçõesMétodos Elementares de Ordenação

void insertion(Item a[], int l, int r){ int i; for (i = l+1; i <= r; i++) compexch(a[l], a[i]); for (i = l+2; i <= r; i++) { int j = i; Item v = a[i]; while (less(v, a[j-1])) { a[j] = a[j-1]; j--; } a[j] = v; }}

• Deslocar em vez de trocar• Parar o ciclo interior • Sentinela (evita testar início)

• Colocar o menor no início

2 3 4 6 7 9 5 1 6 8 4 3 6 4 9 7

2 3 4 6 7 9 1 6 8 4 3 6 4 9 7

5

5

2 3 4 5 6 7 9 1 6 8 4 3 6 4 9 7

v=

2 3 4 5 6 7 9 6 8 4 3 6 4 9 7

1

…

1 7 6 9 4 3 5 2 6 8 4 3 6 4 9 7


Documents

Algoritmos ESTG – IPPortalegre Curso Programadores de Informática Luís Baptista 2016