Estrutura de Dados: Algoritmos para pesquisa e ordenação interna
A estrutura de dados é uma forma de organizar e armazenar dados na memória de um computador, de modo que eles possam ser acessados e manipulados de forma eficiente. Existem diversos tipos de estruturas de dados, como listas, pilhas, filas, árvores, grafos, etc. Cada uma delas tem suas vantagens e desvantagens, dependendo do problema que se quer resolver.
Técnologia em Alta
Um dos problemas mais comuns que envolvem estruturas de dados é a pesquisa e a ordenação de dados. A pesquisa consiste em encontrar um elemento específico dentro de uma estrutura de dados, enquanto a ordenação consiste em rearranjar os elementos de uma estrutura de dados em uma ordem específica, como crescente ou decrescente.
Existem diversos algoritmos para realizar a pesquisa e a ordenação de dados, e cada um deles tem seu próprio desempenho e complexidade. Neste post, vamos apresentar alguns dos algoritmos mais conhecidos e utilizados para pesquisa e ordenação interna, ou seja, quando os dados estão armazenados na memória principal do computador.
Algoritmos de pesquisa
Os algoritmos de pesquisa são divididos em dois tipos: pesquisa sequencial e pesquisa binária.
Pesquisa sequencial
A pesquisa sequencial é o método mais simples de pesquisa. Ela consiste em percorrer a estrutura de dados, elemento por elemento, até encontrar o elemento desejado ou chegar ao final da estrutura. A pesquisa sequencial pode ser aplicada em qualquer tipo de estrutura de dados, seja ela ordenada ou não.
– Recebe como entrada uma estrutura de dados A, um elemento x e o tamanho n da estrutura.
– Inicializa uma variável i com 0.
– Enquanto i < n, faça:
– Se A[i] == x, então retorna i (elemento encontrado na posição i).
– Senão, incrementa i em 1.
– Se chegou ao final da estrutura, retorna -1 (elemento não encontrado).
A complexidade do algoritmo de pesquisa sequencial é O(n), pois no pior caso ele precisa percorrer toda a estrutura de dados.
Pesquisa binária
A pesquisa binária é um método mais eficiente de pesquisa, porém ela só pode ser aplicada em estruturas de dados ordenadas. Ela consiste em dividir a estrutura de dados em duas partes, comparar o elemento desejado com o elemento do meio e repetir o processo na metade que contém o elemento, até encontrá-lo ou chegar a uma parte vazia.
O algoritmo de pesquisa binária é o seguinte:
– Recebe como entrada uma estrutura de dados A, um elemento x e os índices início e fim da estrutura.
– Se início > fim, então retorna -1 (elemento não encontrado).
– Calcula o índice meio como (início + fim) / 2.
– Se A[meio] == x, então retorna meio (elemento encontrado na posição meio).
– Se A[meio] > x, então chama a pesquisa binária com os parâmetros A, x, início e meio – 1 (elemento está na metade esquerda).
– Se A[meio] < x, então chama a pesquisa binária com os parâmetros A, x, meio + 1 e fim (elemento está na metade direita).
A complexidade do algoritmo de pesquisa binária é O(log n), pois a cada passo ele reduz o tamanho da estrutura de dados pela metade.
Algoritmos de ordenação
Os algoritmos de ordenação são divididos em dois tipos: ordenação por comparação e ordenação por distribuição.
Ordenação por comparação
A ordenação por comparação é o método mais comum de ordenação. Ela consiste em comparar os elementos da estrutura de dados entre si e trocá-los de posição até que a estrutura esteja ordenada. Existem diversos algoritmos de ordenação por comparação, como o bubble sort, o insertion sort, o selection sort, o merge sort, o quick sort, etc. Cada um deles tem sua própria forma de realizar as comparações e as trocas.
O algoritmo de ordenação por comparação mais simples é o bubble sort. Ele consiste em percorrer a estrutura de dados várias vezes, comparando os elementos adjacentes e trocando-os de posição se estiverem fora de ordem, até que não haja mais trocas.
O algoritmo de bubble sort é o seguinte:
– Recebe como entrada uma estrutura de dados A e o tamanho n da estrutura.
– Inicializa uma variável troca com verdadeiro.
– Enquanto troca for verdadeiro, faça:
– Atribui falso para troca.
– Para i de 0 até n – 2, faça:
– Se A[i] > A[i + 1], então:
– Troca os valores de A[i] e A[i + 1].
– Atribui verdadeiro para troca.
A complexidade do algoritmo de bubble sort é O(n^2), pois no pior caso ele precisa percorrer a estrutura de dados n vezes, fazendo n – 1 comparações em cada vez.
Ordenação por distribuição
A ordenação por distribuição é um método alternativo de ordenação, que não usa comparações entre os elementos, mas sim a distribuição dos elementos em outras estruturas auxiliares, de acordo com algum critério. Existem diversos algoritmos de ordenação por distribuição, como o counting sort, o radix sort, o bucket sort, etc. Cada um deles tem sua própria forma de distribuir os elementos e de reconstruir a estrutura ordenada.
O algoritmo de ordenação por distribuição mais simples é o counting sort. Ele consiste em contar a frequência de cada elemento da estrutura de dados em um vetor auxiliar, e depois usar esse vetor para reconstruir a estrutura ordenada.
O algoritmo de counting sort é o seguinte:
– Recebe como entrada uma estrutura de dados A, o tamanho n da estrutura e o valor máximo k dos elementos.
– Cria um vetor auxiliar B de tamanho k + 1, inicializado com zeros.
– Para i de 0 até n – 1, faça:
– Incrementa B[A[i]] em 1 (conta a frequência de cada elemento).
– Inicializa uma variável j com 0.
– Para i de 0 até k, faça:
– Enquanto B[i] > 0, faça:
– Atribui i para A[j] (reconstrói a estrutura ordenada).
– Incrementa j em 1.
– Decrementa B[i] em 1.
A complexidade do algoritmo de counting sort é O(n + k), pois ele precisa percorrer a estrutura de dados uma vez, o vetor auxiliar uma vez e reconstruir a estrutura de dados uma vez.
