Métodos de Ordenação

UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ
Engenharia de Produção

implementação de ordenação

meDIANEIRA
2014
introdução
Quando temos um Vetor (ou Matriz) com muitos elementos e precisamos descobrir se um determinado elemento que procuramos se encontra no vetor, uma solução que certamente nos vem à mente é comparar o elemento que procuramos com cada elemento do vetor, até que encontremos ou até que possamos concluir que o elemento procurado não está no vetor. Esta é a base do raciocínio dos algoritmos de pesquisa ou busca ("Search"), que como sugere o nome, "Pesquisam", em um vetor, a existência ou não existência de um elemento procurado.
PESQUISA SEQUENCIAL
Forma mais simples de realizar pesquisas.
Metodologia: Percorre o vetor, elemento por elemento, verificando se o elemento desejado está presente no vetor.
O termo busca linear (ou busca sequêncial) para expressar um tipo de pesquisa em vetores ou listas de modo sequencial, i. e., elemento por elemento, de modo que a função do tempo em relação ao número de elementos é linear, ou seja, cresce proporcionalmente. Num vetor ordenado, essa não é a pesquisa mais eficiente, a pesquisa (ou busca) binária, por exemplo, é um tipo de pesquisa com o gráfico de tempo logarítmo.
O melhor caso, o elemento a ser buscado é encontrado logo na primeira tentativa da busca. No pior caso, o elemento a ser buscado encontra-se na última posição e são feitas N comparações, sendo N o número total de elementos. No caso médio, o elemento é encontrado após N/2 comparações. O algoritmo de busca linear é um algoritmo O(n).

PESQUISA BINÁRIA

A pesquisa ou busca binária (em inglês binary search algorithm ou binary chop) é um algoritmo de busca em vetores que segue o paradigma de divisão e conquista. Ela parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do