Estrutura de dados @

Capítulo 19
Algoritmos de
Ordenação e de
Pesquisa

Rui Rossi dos Santos

Programação de Computadores em Java

Editora NovaTerra

Objetivos do Capítulo
Conceituar ordenação e pesquisa.
Apresentar os algoritmos de ordenação por troca, por seleção e por inserção.
Explorar os algoritmos de pesquisa linear e de pesquisa binária. Rui Rossi dos Santos

Programação de Computadores em Java

Editora NovaTerra

Introdução
Ordenação
Operação realizada sobre registros
Objetivo: organizá-los sob determinada ordem

Pesquisa
Operação realizada sobre registros
Objetivo: localizar um registro
Chave: campo ou chave presente em todos os registros

Rui Rossi dos Santos

Programação de Computadores em Java

Editora NovaTerra

Introdução
Algoritmos de ordenação
Ordenação por troca
Ordenação por seleção
Ordenação por inserção

Algoritmos de pesquisa
Pesquisa linear
Pesquisa binária

Rui Rossi dos Santos

Programação de Computadores em Java

Editora NovaTerra

Ordenação por Troca
Características
O mais simples
O mais lento

Método: bolha (bubble sort)
Compare dois elementos
Se o elemento da esquerda for maior, troque-os.
Mova-se uma posição à direita.
Obs.: acumula os elementos ordenados no final do vetor.

Rui Rossi dos Santos

Programação de Computadores em Java

Editora NovaTerra

Ordenação por Troca
Modelo:
int[] dados = new int[]{45,23,78,35,15}; for(int out = dados.length - 1; out > 0; out--) for(int in = 0; in < out; in++) if(dados[in] > dados[in+1]) { int temp = dados[in]; dados[in] = dados[in+1]; dados[in+1] = temp;
}

Rui Rossi dos Santos

Programação de Computadores em Java

Editora NovaTerra

Ordenação por Troca
Exemplos:

Rui Rossi dos Santos

Programação de Computadores em Java

Editora NovaTerra

Ordenação por Troca
Código 19.1 – OrdenacaoTroca.java
Código 19.2 –TrocaTeste.java

Rui Rossi dos Santos

Programação de Computadores em Java

Editora NovaTerra

Ordenação por Troca
Código 19.1 – OrdenacaoTroca.java
Código 19.3 –TrocaData.java

Rui Rossi dos Santos