Juliana Jenny Kolb
Home > Simulados on-line > Questões de Concursos > Tecnologia da Informação (TI) > Algoritmos e Estruturas de Dados
Métodos de Pesquisa e Ordenação
*Exemplos em C.
Existem alguns métodos (algoritmos) muito utilizados para ordenar matrizes (listas e/ou matrizes). São eles:
Bubble Sort
O método Bubble sort, ou ordenação por flutuação (literalmente “por bolha”), é um algoritmo de ordenação dos mais simples. A ideia é percorrer o vetor diversas vezes, a cada passagem fazendo flutuar para o topo o maior elemento da sequência. Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.
O algoritmo Bubble Sort consome processamento. Apesar de simples, não deve ser utilizado com atrizes ou listas muito extensas para evitar lentidão no processamento.
Este método cria uma ordenação decrescente.
Para criar uma ordenação crescente, o algoritmo deverá mover o maior valor para a posição posterior, após o elemento testado.
Lembrando sempre que a dificuldade de ordenação está relacionada com a disposição dos elementos na matriz (lista) e também com o número de elementos presentes na mesma.
Select Sort
O algoritmo Select Sort também consome processamento e tempo, e assim, também não é adequado em matrizes e listas muito grandes.
Ele trabalha selecionando um elemento como o primeiro da lista, por exemplo. É realizada uma pesquisa na lista para encontrar o valor mínimo e este é então posicionado no lugar do elemento pesquisado.
A pesquisa continua procurando o segundo elemento menor (maior que o mínimo e menor que o selecionado). Esta ordenação será crescente.
Para obter uma ordenação decrescente, basta operar o algoritmo de maneira contrária. A figura abaixo mostra um exemplo hipotético para este modo de ordenação, no modo crescente.
Shell Sort
O método Shell é um refinamento do método de inserção direta. O algoritmo difere do método de inserção direta pelo fato de no lugar de considerar o array a ser ordenado como um único segmento, ele considera vários segmentos sendo aplicado o método de inserção direta em cada um deles. Basicamente o algoritmo passa várias vezes pela lista dividindo o grupo maior em menores.
Em outras palavras, a ordenação Shell Sort compara os elementos de uma matriz que estão separados por uma distância específica chamada gap, até que os elementos comparados com o gap corrente estejam em ordem.
O gap é então é dividido por 2 e o processo continua, até que o gap
seja igual a 1 e nenhuma divisão possa mais ser feita (com um valor inteiro como resultado). Ao final do processo, a matriz estará ordenada.
Este método se parece muito com o algoritmo tipo bolha (Buble Sort) somado ao tipo seleção (Select Sort), com a diferença de ser mais rápido e podermos escolher quais elementos da matriz serão ordenados. Assim, este algoritmo pode ser considerado um dos que consome menor processamento e também tempo de execução.
Quick Sort
Este algoritmo seleciona o valor central da lista como um separador. A partir daí ele cria duas listas: a primeira com os valores menores que o separador e outra com os valores maiores ou iguais ao separador. A seguir a ordenação chama a si mesma recursivamente, sempre selecionando um novo separador nas listas, e criando novas listas menores até que estas tenham apenas um único elemento.
O algoritmo então reposiciona os valores das novas listas na lista original. Ao final do algoritmo uma matriz (lista) estará ordenada. A figura abaixo mostra um exemplo deste algoritmo.
Note que as novas “listas” são geradas levando em conta a posição da lista anterior. Assim o programa saberá exatamente qual a posição de cada valor. O leitor deve observar porém que neste método, o consumo de memória é bem grande e isto, para alguns microcontroladores, pode ser um fator limitante.
Busca Sequencial
O algoritmo Busca Sequencial executa a pesquisa de um elemento em uma matriz comparando-o aos elementos da matriz um após o outro até obter o resultado “verdadeiro” ou chegar ao fim da matriz. Este tipo de busca só é viável se a matriz (lista) for pequena (ou média) e/ou não estiver ordenada. Devido ao seu modo de operação, a mesma costuma consumir tempo.
Busca Binária
A busca binária só deve ser executada em matrizes (listas) previamente ordenadas, seja no modo crescente ou decrescente. A pesquisa binária divide por dois a lista analisada e compara o valor.
Se o valor central for maior que o objeto da pesquisa, o algoritmo divide
novamente a lista em dois, desta vez considerando apenas a parte central e o topo da lista. Se o valor central for menor, a nova divisão será feita entre a parte central e o final da lista.
Agora o algoritmo compara novamente o objeto da pesquisa com o valor apresentado e continua a divisão até obter o resultado positivo, ou até não ser mais possível realizar a divisão da matriz. Se isto ocorrer, é porque o valor não foi encontrado e o algoritmo devolve este resultado. Note que esta pesquisa é muito rápida e é a mais adequada para uso com matrizes (listas) muito grandes.
Hashing
O método de Hashing é um método de transformação da chave de pesquisa, os registros armazenados em uma tabela são diretamente endereçados sobre a chave de pesquisa.