Algoritmos de Busca e Ordenação

Prévia do material em texto

Estrutura de Dados
_______________________________________
Algoritmos de Busca
Busca linear (listas)
o Examina cada elemento da estrutura seqüencialmente
o Complexidade: O(n)
o Pode ser usado diretamente em uma lista não-processada (desordenada)
o Muito lento para grandes quantidades de dados, mas aceitável para listas 
pequenas e que mudam constantemente
Implementação (iterativa):
private int linearSearch(int a[], int valueToFind) {
 for (int i=0; i<a.length; i++) {
 if (valueToFind == a[i]) {
 return i;
 }
 }
 return -1;
 }
Busca binária (listas)
o Realiza sucessivas divisões do espaço de busca, comparando o elemento 
buscado com o elemento no meio da subdivisão (divisão e conquista)
o Complexidade: O(log n)
o Parte do pressuposto que a lista é de acesso aleatório e está ordenada
o Ótimo desempenho comparado à busca linear para grandes quantidades de 
dados. Tem a desvantagem de requerer uma ordenação da lista após cada 
alteração na mesma
Implementação (recursiva):
BinarySearch(A[0..N-1], value, low, high) {
 if (high < low)
 return -1 // not found
 mid = (low + high) / 2
 if (A[mid] > value)
 return BinarySearch(A, value, low, mid-1)
 else if (A[mid] < value)
 return BinarySearch(A, value, mid+1, high)
 else
 return mid // found }
Busca em árvores
o Depth-first (busca em profundidade)
 Vai até uma determinada folha da árvore e faz backtracking
o Breadth-First (busca em largura)
 Faz a procura por níveis. Começa na raiz e pesquisa todos os nós 
adjacentes no mesmo nível e, se não achar o elemento procurado, 
desce para o próximo nível e repete o processo
Algoritmos de Ordenação Simples – O(n2)
Bubble Sort 
o A idéia é percorrer a lista diversas vezes, fazendo o maior elemento 
deslocar-se para o final da mesma após sucessivas comparações
o Compara v[i] com v[i+1]. Se estiverem desordenados, há um swap (troca). 
Isso é repetido para todos os elementos da lista dois-a-dois
 for(i = 0; i < v.length-1; i++){
 for(j = 0; j < v.length-1;j++){ 
 if(v[j] > v[j+1]){
 swap(v[j],v[j+1]);
 }
 }
 } 
Selection Sort 
o O algoritmo funciona da seguinte forma:
 Ache o valor mínimo da lista
 Troque-o pelo elemento na primeira posição
 Repita esses passos para o restante da lista (começando de índice+1)
public void SelectionSort(int[] v) {
 int index_min;
 int aux;
 for (int i=0; i<v.length; i++) {
 index_min = i;
 for (int j=i+1; j<v.length; j++) {
 if (v[j]<v[index_min]) {
 index_min=j;
 }
 if (index_min!=i) {
 aux = v[index_min];
 v[index_min] = v[i];
 v[i] = aux;
 } 
 }
 }
}
Insertion Sort 
o Em termos gerais, percorre um vetor de elementos da esquerda para a 
direita e à medida que avança vai deixando os elementos mais à esquerda 
ordenados.
public static void insertionSort(int[] vetor) {
 for (int i = 0; i < vetor.length; i++) {
 int aux = vetor[i];
 int j = i;
 while (j > 0 && vetor[j - 1] > aux) {
 vetor[j] = vetor[j - 1];
 j = j - 1;
 }
 vetor[j] = aux;
 }
Algoritmos de Ordenação Avançados – O(n log n) 
Mergesort 
o Conceitualmente o mergesort funciona da seguinte forma:
 Divida a lista não-ordenada em duas sublistas de aproximadamente 
metade do tamanho da original
 Divida cada uma das sublistas recursivamente até termos listas de 
tamanho 1, onde, então, elas são retornadas
 Junte (merge) as duas sublistas em uma lista ordenada
function mergesort(m)
 var list left, right, result
 if length(m) ≤ 1
 return m
 else
 var middle = length(m) / 2
 for each x in m up to middle
 add x to left
 for each x in m after middle
 add x to right
 left = mergesort(left)
 right = mergesort(right)
 result = merge(left, right)
 return result
Quicksort 
o Os passos são:
 Escolha um elemento , chamado de pivô, na lista
 Rearranje a lista de forma que todos os elementos anteriores ao pivô 
sejam menores ou iguais a ele, e todos os elementos posteriores ao 
pivô sejam maiores ou iguais a ele. Ao fim do processo o pivô estará 
em sua posição final. Essa operação é denominada partição
 Recursivamente ordene a sublista dos elementos menores e a sublista 
dos elementos maiores
o Complexidade: O (n log n) , mas , no pior caso, pode chegar a O(n2)
o Tipicamente, o quicksort é bem mais rápido do que os outros algoritmos 
que rodam a O(n log n), pois seu loop interno pode ser otimizado na 
maioria das arquiteturas
function quicksort(array)
 var list less, equal, greater
 if length(array) ≤ 1 
 return array 
 select a pivot value pivot from array
 for each x in array
 if x < pivot then append x to less
 if x = pivot then append x to equal
 if x > pivot then append x to greater 
 return concatenate(quicksort(less), equal, quicksort(greater))
Estrutura de dados: Array
Estrutura de dados linear, homogênea (contém elementos do mesmo tipo) e 
armazenada contiguamente
Elementos são acessados diretamente (acesso aleatório) através de um índice. 
Acesso rápido
Têm tamanho fixo , não podem ser incrementados ou diminuídos sem implicar 
complexos processos de cópia
Estrutura de dados: Stack (Pilha)
Estrutura do tipo Last in , First Out (LIFO)
Uma pilha é uma lista linear na qual o primeiro elemento a entrar é o último 
elemento a sair. Ela possui apenas uma entrada, chamada de topo, a partir da qual 
os dados entram e saem dela
É muito usada em compiladores para parsing e como estrutura para armazenar 
variáveis locais a um bloco de função
Operações: push (empilhar) , pop (desempilhar) e peek (olhar o conteúdo do 
topo)
Os itens em uma pilha podem ser empilhados e desempilhados em tempo 
constante de O(1), sendo desnecessário qualquer tipo de comparação
Estrutura de dados: Queue (Fila)
Estrutura do tipo First in , First Out (FIFO)
Semelhante à pilha, só que neste caso só são permitidas inserções no final da fila e 
remoções no começo.
Esse tipo específico de estrutura é muito usado em aplicações que requerem que os 
itens sejam acessados na ordem em que foram adicionados à lista
Outros tipos de filas:
o Deque (double-ended queue): permite remover/inserir elementos em 
qualquer lado
o Priority Queue: mantém os elementos ordenados de acordo com algum 
critério de prioridade
Estrutura de dados: Linked List (Lista Ligada)
Estrutura de dados do tipo linear e dinâmica
É composta por células que apontam para o próximo elemento da lista
Uma lista ligada deve guardar as referências para o seu primeiro e último 
elementos (este, por sua vez, tem seu apontador voltado para uma referência nula)
Vantagem: A inserção de um elemento no meio da lista não implica mover todos 
os elementos
Desvantagem: o acesso sequencial, para eliminação ou inserção de um elemento 
no meio da lista
Variação: lista duplamente encadeada
o Cada nó tem referência para ambos o anterior e o próximo elemento
o Melhora o desempenho de algumas operações sobre a lista, como remover 
um elemento do final ou mostrar os elementos na ordem inversa
Estrutura de dados: Binary Trees (Árvores Binárias)
Uma árvore binária é uma estrutura caracterizada por:
o Ou não tem elemento algum (árvore vazia)
o Ou tem um elemento distinto, denominado raiz, com dois apontadores para 
duas estruturas diferentes, denominadas sub-árvore esquerda e sub-árvore 
direita
 Cada elemento pode ter até, no máximo, dois filhos
Em uma árvore binária de busca, todos os nós que são descendentes à esquerda 
de um nó A têm valores menores que A. Todos os nós que são descendentes à 
direita de A têm valores maiores que A
Árvores binárias fazem buscas, inserções e deleções em O(log n)
Percorrer uma árvore significa visitar todosos seus nós em uma determinada 
ordem. 
Pode-se percorrer de 3 formas: 
o Pré ordem
 Visite a raiz
 Percorra a sub-árvore à esquerda
 Percorra a sub-árvore à direita
o Em ordem
 Percorra a sub-árvore à esquerda
 Visite a raiz
 Percorra a sub-árvore à direita
o Pós ordem
 Percorra a sub-árvore à esquerda
 Percorra a sub-árvore à direita
 Visite a raiz
Uma árvore binária balanceada é aquela em que a diferença de profundidade 
(nível) entre todas as folhas (elementos sem filhos) é de, no máximo, 1.
O número máximo de folhas por nível é dado por 2i, onde i = nível
Estrutura de dados: Hashtable (Tabela hash)
É uma estrutura de dados especial, que associa chaves de pesquisa (hash) a valores
Seu objetivo é, a partir de uma chave simples, fazer uma busca rápida e obter o 
valor desejado
É baseada em arrays
Função de espalhamento: responsável por gerar um índice a partir de uma 
determinada chave. Idealmente, este índice deve ser único para evitar colisões
Para resolver colisões pode-se usar:
o Algoritmo de rehash, que calcula um novo hash baseado em uma 
determinada função, caso haja colisão
o Encadeamento, onde encontra-se uma posição disponível na tabela e 
indicamos que está posição é a que deve ser buscada em seguida