Algoritmos de ordenação e de procura - Técnico … Pedro Silva –José Borges Computação e Programação 2009 / 2010 Algoritmos de ordenação 2 •Ordenação é o processo

Instituto Superior Técnico,

Dep. de Engenharia Mecânica - ACCAII

Algoritmos de ordenaçãoe de procura

• Ordenação

• Ordenação por selecção

• Ordenação por inserção linear

• Ordenação rápida

• A função sort

• Exemplos:

• Ordenar vectores de estruturas

• Ordenar strings

• Ordenar índices

• Procura

• Procura sequencial

• Procura binária

• A função find

Miguel Pedro Silva – José Borges Computação e Programação 2009 / 2010

Algoritmos de ordenação

2

• Ordenação é o processo de colocar uma lista em

ordem ascendente ou ordem descendente.

• Existem vários algoritmos de ordenação:

• Ordenação por selecção;

• Ordenação por inserção linear;

• Ordenação rápida;

• Etc ….

Miguel Pedro Silva – José Borges Computação e Programação 2009 / 2010 3

Ordenação por selecção

• Algoritmo (ordem crescente):

1. Procurar na lista o elemento mais pequeno, e colocá-lo naprimeira posição da lista, trocando-o de posição com o primeiro elemento da lista;

2. Procurar, a partir do segundo elemento da lista, o elemento mais pequeno, e colocá-lo na segunda posiçãoda lista, trocando-o de posição com o segundo elementoda lista;

3. Continuar o processo até o penúltimo elemento estarcolocado na posição correcta.



• Percorre várias vezes a lista ou parte da lista

• Em cada passagem, selecciona um item a ser correctamenteposicionado na lista

• Procura o elemento mais pequeno

• Troca-o com o primeiro elemento



• Repete para o resto da lista – as sublistas vão sendo sucessivamente mais pequenas


Ordenação por selecção: implementação


Ordenação por selecção: execução

7

>> lista=[67,33,21,84,49,50,75]

lista =

67 33 21 84 49 50 75

>> lista_ord=mysort(lista)

lista_ord =

21 33 49 50 67 75 84


A função sort

8

Descrição: Ordena por ordem ascendente (por omissão) ou por ordem descendente.

Sintaxe :

Y = SORT(X,DIM,MODE)

has two optional parameters.

DIM selects a dimension along which to sort.

MODE selects the direction of the sort

'ascend' results in ascending order

'descend' results in descending order

The result is in Y which has the same shape and

type as X.

[Y,I] = SORT(X,DIM,MODE) also returns an index

matrix I.


A função sort: exemplos

9

>> lista

lista =

67 33 21 84 49 50 75

>> [lista_ord,indices]=sort(lista)

lista_ord =

21 33 49 50 67 75 84

indices =

3 2 5 6 1 7 4


A função sort: exemplos

10

>> matriz = [4 6 2;8 3 7;9 7 1]

matriz =

4 6 2

8 3 7

9 7 1

>> matriz_ord_col = sort(matriz)

matriz_ord_col =

4 3 1

8 6 2

9 7 7

>> matriz_ord_lin = sort(matriz,2)

matriz_ord_lin =

2 4 6

3 7 8

1 7 9


A função sort: ordenação de strings: exemplos

11

>> words=char('Hello','Howdy','Hi','Goodbye','Ciao')

words =

Hello

Howdy

Hi

Goodbye

Ciao


A função sort: ordenação de strings: exemplos

12

>> sort(words)

ans =

Ce

Giad

Hildb

Hoolo

Howoyye

>> sort(words,2)

ans =

Hello

Hdowy

Hi

Gbdeooy

Caio


A função sortrows

13

Descrição: Ordena cada linha como um bloco (ou grupo), e por ordem ascendente .

Sintaxe : [Y,I] = SORTROWS(X)

Exemplo:

>> sortrows(words)

ans =

Ciao

Goodbye

Hello

Hi

Howdy


A função sort: ordenação de cell de strings

14

>> cellNomesEng={'Quimica','Mecanica','Electrotecnia','Civil'}

cellNomesEng =

'Quimica' 'Mecanica' 'Electrotecnia' 'Civil'

>> sort(cellNomesEng)

ans =

'Civil' 'Electrotecnia' 'Mecanica' 'Quimica'


A função sort: ordenação de cell de strings

15

>> cellNomesEng={'naval','Quimica','Mecanica','Electrotecnia','Civil'}

cellNomesEng =

'naval' 'Quimica' 'Mecanica' 'Electrotecnia' 'Civil'

>> sort(cellNomesEng)

ans =

'Civil' 'Electrotecnia' 'Mecanica' 'Quimica' 'naval'


Ordenação por selecção: ordenar vectores de estruturas

16

Exemplo:

Escreva uma função que receba um array de estruturas e uma string que designa um campo numérico e que retorne o arrayde estruturas ordenado por ordem crescente, relativamente ao campo pedido.



17

% Este script auxiliar cria uma array de estruturas

OsMeusCDs(1) = struct('Genero','Rock', ...

'Artista','Xutos e Pontapés', ...

'Titulo','Circo de Feras', ...

'Ano', 1987);

OsMeusCDs(2) = struct('Genero','Rock', ...

'Artista','Metallica', ...

'Titulo','Black Album', ...

'Ano', 1991);

OsMeusCDs(3) = struct('Genero','Cubana', ...

'Artista','Eliades Ochoa', ...

'Titulo','Grandes Éxitos', ...

'Ano', 2000);

OsMeusCDs(4) = struct('Genero','Rock progressivo', ...

'Artista','Marillion', ...

'Titulo','Misplaced Childhood', ...

'Ano', 1985);



18



19

>> cria_array_estrut;

>> outv = ordena_vec_estrut(OsMeusCDs,'Ano');

>> outv(1)

ans =

Genero: 'Rock progressivo'

Artista: 'Marillion'

Titulo: 'Misplaced Childhood'

Ano: 1985

>> outv(2)

ans =

Genero: 'Rock'

Artista: 'Xutos e Pontapés'

Titulo: 'Circo de Feras'

Ano: 1987



20

>> outv(3)

ans =

Genero: 'Rock'

Artista: 'Metallica'

Titulo: 'Black Album'

Ano: 1991

>> outv(4)

ans =

Genero: 'Cubana'

Artista: 'Eliades Ochoa'

Titulo: 'Grandes Éxitos'

Ano: 2000


Algoritmos de ordenação: indexação

21

• A indexação é uma alternativa à ordenação de um vector. Com

a indexação o vector original é deixado na sua ordem e apenas

se utiliza um vector com índices que ordenam o vector original.

EXEMPLO:

>> lista

lista =

67 33 21 84 49 50 75

indices =

3 2 5 6 1 7 4

>> listaOrd=lista(indices)

listaOrd =

21 33 49 50 67 75 84


Algoritmos de ordenação: indexação

• Algoritmo (ordem crescente):

1. Inicializar os valores no vector de índices: 1, 2,3,…;

2. Utilizar um algoritmo de ordenação, mas comparar oselementos na lista original utilizando o vector de índicespara indexar os elementos na lista;

3. Quando o algoritmo de ordenação trocar valores, devemser trocados os elementos do vector de índices e não osvalores da lista original.


Algoritmos de ordenação: indexação: implementação

23


Algoritmos de ordenação: indexação: execução

24

>> lista

lista =

67 33 21 84 49 50 75

>> indOrd=createind(lista)

indOrd =

3 2 5 6 1 7 4


Ordenação por inserção linear

• Insere sucessivamente um novo elemento numa lista de elementos já ordenados

• O resultado é uma lista ordenada

Sublista tem apenas um elemento (67)

Insere 33; obtém-se uma lista com 2 items







Ordenação por inserção linear (cont.)

6 2 4 81012Array

original

Array

ordenado

Exemplo:



6 2 4 81012

6

Array

original

Exemplo:

Array

ordenado



2 6

6 2 4 81012Array

original

Exemplo:

Array

ordenado



2 6 12

6 2 4 81012Array

original

Exemplo:

Array

ordenado



2 4 6 12

6 2 4 81012Array

original

Exemplo:

Array

ordenado



2 4 6 10 12

6 2 4 81012Array

original

Exemplo:

Array

ordenado



2 4 6 8 10 12

6 2 4 81012Array

original

Exemplo:

Array

ordenado


Ordenação por inserção linear (cont.):a inserção

Dado o seguinte array:

Como inserir o número 7 neste array ?

2 4 6 8 10 12



2 4 6 8 10 12

Para inserir o 7 nesta posição, deve-se:

1. Inserir um espaço para o valor

2. Inserir o valor 7.

12



2 4 6 8 10 12






2 4 6 8 10 12






2 4 6 8 1210






2 4 6 8 1210






2 4 6 8 12107





Ordenação por inserção linear (cont.):implementação

function b = ordenaPorInsercao(a)

% EXERCÍCIO PARA CASA !!!


Ordenação rápida

• Muito eficiente; é muitas vezes implementada de forma recursiva

• Estratégia

• Escolhe um elemento chamado de pivot

• Faz trocas de forma a que:

Todos os elementos menores que o pivot ficam à suaesquerda

Todos os elementos maiores que o pivot ficam à sua direita

• Divide as duas sublistas resultantes, cada uma com o seupivot, e efectua o mesmo tipo de trocas


Ordenação rápida (cont.)

• Seja 75 o pivot

• Procurar da direita para a esquerda por um número < 75

• Procurar da esquerda para a direita por um número > 75

• Trocar os números



• Continuar, desde a direita e da esquerda, efectuando as trocas necessárias

• Troca-se então o pivot com o número do meio



• Aplica-se de novo a ordenação rápida nas duas sublistas restantes

• Isto pode ser feito recursivamente• A âncora é o caso em que a lista examinada está vazia ou

contém apenas um elemento

• O passo recursivo (inductivo) são os casos em que a lista tem mais de um elemento


Ordenação rápida(cont.): implementação

function b = ordenacaoRapida(a)

% EXERCÍCIO PARA CASA !!!


Algoritmos de procura

46

• Procura significa encontrar numa lista, ordenada ou

não, um dado elemento (que se irá denominar por

elemento chave)

• Existem vários algoritmos de procura:

• Procura sequencial;

• Procura binária;

• Etc ….


Procura sequencial

• Geralmente utilizada em listas não ordenadas!

• Algoritmo :

1. Utilizando um ciclo que percorra todos os elementos de uma lista, testar se o elemento na posição com índice k é igual ao elemento chave, se for retornar o índice k, casocontrário continuar a procura;

2. Se o elemento chave não for encontrado deve ser devolvido o valor 0 ou -1;


Procura sequencial

• Procura elementos consecutivos numa lista

• Começa no primeiro

• Continua até encontrar o item procurado ou até chegar aofim da lista

[1] [2] [3] [4] [5] [6] [7]


Procura sequencial: implementação

49


Procura sequencial: execução

50

>> lista

lista =

67 33 21 84 49 50 75

>> indice=seqsearch(lista,50)

indice =

6


Procura binária

• Utilizada em listas ordenadas!

• Algoritmo :

1. Verificar se o elemento chave é igual ao elemento do meioda lista. Se for: retornar o índice k associado;casocontrário:

2. Verificar em qual das sub-listas o elemento chave se podeencontrar. Se a sub-lista estiver vazia ir para o passo 3; caso contrário ir para o passo 1;

3. Se o elemento chave não for encontrado deve ser devolvido o valor 0 ou -1.


Procura binária

• O algoritmo mais eficiente para procurar numa listaordenada (para n items, máximo de log2n comparações)

• Começa no elemento do meio

• Compara procurado com o elemento

• Se meio < procurado, vai para meio da sublista à direita

• Se meio > procurado, vai para meio da sublista à esquerda

procurado

Note-se que procurado é

encontrado em dois passos

[1] [2] [3] [4] [5] [6] [7]


Procura binária: implementação

53


Procura binária: execução

54

>> lista=[11,22,33,44,55,66,77]

lista =

11 22 33 44 55 66 77

>> indice=binsearch(lista,66)

indice =

6


A função find

55

Descrição: Retorna os índices dos elementos que não são zero.

Sintaxe :

I = FIND(X) returns the linear indices

corresponding to the nonzero entries of the array

X.

X may be a logical expression.


A função find: exemplos

56

>> lista=[67,33,21,84,49,50,75]

lista =

67 33 21 84 49 50 75

>> indices=find(lista==33)

indices =

2

>> indices=find(lista>=33)

indices =

1 2 4 5 6 7

>> lista_proc=lista(indices)

lista_proc =

67 33 84 49 50 75


Referências

57

• Capítulo 12 (12.3—12.5) de Stormy Attaway (2009), “Matlab: A Practical Introduction to Programming and Problem Solving”, Elsevier.

• Getting started with MATLAB: http://www.mathworks.com/access/helpdesk/help/pdf_doc/matlab/getstart.pdf

http://www.mathworks.com/access/helpdesk/help/pdf_doc/matlab/getstart.pdf

http://www.mathworks.com/access/helpdesk/help/pdf_doc/matlab/getstart.pdf

Documents

Algoritmos de ordenação e de procura - Técnico … Pedro Silva –José Borges Computação e Programação 2009 / 2010 Algoritmos de ordenação 2 •Ordenação é o processo