Introdução às Estruturas de Dados e Algoritmos de Ordenação

1 – Introdução ao Estudo das Estruturas de Dados

Um programa de computador consiste basicamente em duas coisas: instruções e locais para armazenar dados. Desse modo, as linguagens de programação são “equipadas” com mecanismos para controlar as instruções e os dados. Esses mecanismos são denominados “estruturas” e todas as linguagens de programação contemporâneas contam com dois tipos de estruturas: as estruturas de controle de fluxo de execução (para instruções) e as estruturas de dados (para os dados).

Estruturas de Controle de Fluxo de Execução:

• Sequencial;
• Condicionais;
• Iterativas;
• Chamadas a rotinas.

Estruturas de Dados:

• Primitivas: (inteiro, real, lógico, caracter);
• Compostas: 1) Homogêneas (vetores, matrizes); 2) Heterogêneas (registros, arquivos);
• Complexas: 1) Estáticas (Listas Estáticas Sequenciais, Listas Estáticas Encadeadas); 2) Dinâmicas (Listas Dinâmicas, Ponteiros, Pilhas, Filas, Árvores).

2 – Revisão de Tópicos

• Modularização;
• Variáveis Locais e Globais;
• Passagem de Parâmetros.

3 – Registros: As estruturas de dados utilizadas até o momento (vetores e matrizes) permitem o armazenamento de vários valores na mesma estrutura; porém, cada estrutura só pode ser definida para um único tipo de dados. Quando se precisou utilizar dados de diferentes tipos para a solução de problemas, foi necessário o uso de diferentes estruturas. Agora, é apresentada uma estrutura de dados em que é possível armazenar, na mesma estrutura, diversos valores de diferentes tipos de dados. Essa estrutura é chamada de Registro e, por sua característica, classificada como uma estrutura de dados heterogênea.

4 – Algoritmos de Ordenação ou Classificação

Algoritmo Bubble Sort (ou Método da Bolha): Por ser simples e de fácil implementação, o algoritmo Bubble Sort ou Método da Bolha está entre os mais conhecidos e difundidos métodos de ordenação de arranjos de dados. Mas não se trata do algoritmo mais eficiente. É estudado para desenvolvimento do raciocínio lógico e como introdução ao assunto de ordenação ou classificação de dados.

Algoritmo Selection Sort: O algoritmo do método de ordenação Selection Sort seleciona o maior elemento do arranjo e troca-o com o elemento da última posição. A cada iteração, desconsidera-se a “última” posição do vetor, fazendo com que o arranjo fique “menor”. Esse algoritmo também realiza (n-1) iterações para garantir que os elementos estejam ordenados.

Dinâmica de Funcionamento:

• Na primeira iteração, o algoritmo encontra o maior elemento do vetor e troca este elemento com o elemento que está na n-ésima posição;
• Na segunda iteração, despreza-se o n-ésimo elemento e encontra-se novamente o maior elemento (exceto o maior elemento já identificado na primeira iteração; este segundo maior é o maior entre os demais) e troca-se com o elemento que está na (n-1)-ésima posição;
• Este processo se repete até que se tenha ordenado todos os elementos do arranjo.

Algoritmo Insertion Sort: O algoritmo do método de ordenação Insertion Sort utiliza a técnica de indução algorítmica para resolver o problema de ordenação. Assim, sabendo-se resolver um problema menor, resolve-se um problema maior.

Dinâmica de Funcionamento:

Considere o vetor V assim definido: V = { V1, V2, V3, ..., Vn-1, Vn }.

Considere o vetor V' assim definido e já ordenado: V' = { V1 }.

A dinâmica consiste em comparar do segundo elemento em diante do vetor V com o elemento (sempre já ordenado) do vetor V' e inseri-los na posição correta do vetor V'.