Algoritmos de Busca e Ordenação em Estruturas de Dados

Algoritmos de Busca

Busca Sequencial

• Percorre cada item do vetor até encontrar a informação solicitada.
• Apresenta baixo desempenho quando se tem uma grande quantidade de registros.
• Melhor desempenho quando os dados estão ordenados.

Busca Binária

• Divide o vetor ao meio e compara o elemento central com o procurado.
• Se o elemento procurado for menor, repete o processo no lado esquerdo; se for maior, repete no lado direito.
• Os elementos devem estar ordenados.
• Desempenho melhor que a busca sequencial.

Busca por Interpolação

• É uma variação da busca binária.
• Escolhe a próxima posição pesquisada com base em uma estimativa sobre a posição do elemento procurado em relação ao restante do vetor.
• Pode ser mais eficiente do que a pesquisa binária, se os dados estiverem uniformemente distribuídos.

Gerenciamento de Memória

Alocação Estática

• Quantidade de memória utilizada é previamente definida, no próprio código.
• Cada dado tem sua área reservada, e não há variação ao longo da execução do programa.
• O Sistema Operacional garante que o espaço de memória utilizado por uma variável estática jamais poderá ser utilizado por outra.

Desvantagens

• Desperdício de espaço na memória em caso de superdimensionamento.
• Não funcionamento do programa caso haja subdimensionamento.

Alocação Dinâmica

• Na alocação dinâmica, os espaços são alocados durante a execução do programa.
• Isto significa que conforme o programa necessitar de memória, alocará os espaços.
• Não há reserva antecipada de espaços, pelo contrário, o espaço é solicitado sob demanda.
• O programa é capaz de criar novas variáveis enquanto é executado.

Algoritmos de Ordenação

Insertion Sort

• Ordena um vetor pela inserção de cada elemento em sua posição correta.
• Implementação simples.
• Fácil compreensão.
• Divide o vetor em duas partições.
• Baixa eficiência para ordenar muitos elementos.

Bubble Sort

• Efetua sucessivas comparações de elementos dois a dois, com a consequente troca desses elementos.
• Mais conhecida dentre as técnicas.
• Fácil de compreender e de implementar.
• Baixo desempenho em comparação às outras.

Selection Sort

• Percorre o vetor e em cada iteração descobre o menor elemento, colocando-o em sua posição definitiva.
• Simples e de fácil entendimento.
• Baixo desempenho para ordenar grandes quantidades de informações.

Merge Sort

• Divide o vetor ao meio, recursivamente, até que o vetor fique com um elemento e estes sejam ordenados e intercalados.
• Utiliza a técnica da divisão e conquista.
• O vetor é dividido em duas partes que são ordenadas recursivamente pelo mesmo método.

Quick Sort

• Assim como o Merge Sort, se baseia no paradigma de dividir e conquistar.
• Escolhe-se um pivô e separam-se os elementos em 2 partes: os elementos menores que o pivô ficam à esquerda e os maiores à direita.
• O processo é repetido recursivamente.

Shell Sort

• As comparações e trocas são feitas baseadas em uma distância determinada (incremento).
• A distância é reduzida a cada iteração (5, 3, 1).
• O processo se repete até que a distância seja 1 e as últimas comparações e trocas sejam efetuadas.