Métodos de Ordenação

Introdução:

Algoritmos descrevem passo a passo como proceder para chegar à solução de um problema. Três são os tipos de algoritmos mais conhecidos:

- A forma de descrição narrativa, na qual se usa a linguagem nativa e convencional de quem escreve. Essa forma não segue um padrão definido e portanto pode sofrer várias interpretações por quem lê;

- Outra forma de representar um algoritmo é a de um fluxograma, uma representação visual que utiliza símbolos que são figuras geométricas, cada uma com sua função específica. Essa representação, como o próprio nome diz, mostra o fluxo do algoritmo e também elimina as várias interpretações que a descrição narrativa permitia sobre um algoritmo;

- Por último, existe a linguagem algoritma (Pseudocódigo ou “Portugol”) que é a mais parecida com uma linguagem de programação estruturada.

Um tipo comum de algoritmo que é muito utilizado na resolução de problemas computacionais são os algoritmos de ordenação. Algoritmos de ordenação servem para ordenar, ou organizar, uma lista de números ou palavras. A maioria das linguagens de programação já conta com métodos de ordenação implementados de forma nativa, porem em alguns casos pode ser que haja necessidade de modificar ou programar um novo método.

Os métodos de ordenação mais populares são Insertion sort, Selection sort, Bubble sort, Comb sort, Quick sort, Merge sort, Heap sort e Shell sort.

Esses métodos se classificam em ordenação interna e ordenação externa.

- Ordenação Interna: onde todos os elementos a serem ordenados cabem na memória principal e qualquer registro pode ser imediatamente acessado.

- Ordenação Externa: onde os elementos a serem ordenados não cabem na memória principal e os registros são acessados seqüencialmente ou em grandes blocos. A principal diferença entre os dois grupos é que no método de ordenação interna qualquer registro pode ser acessado diretamente, enquanto no método externo é necessário fazer o acesso em blocos.

Métodos de Ordenação Interna:

Durante a escolha de um algoritmo de ordenação, deve-se observar um aspecto importante: o tempo gasto durante a sua execução. Para algoritmos de ordenação interna, as medidas de complexidade relevantes contam o número de comparações entre as chaves e o número de movimentações de itens do arquivo.

Outra medida que pesa na escolha é a quantidade de memória extra utilizada pelo algoritmo. Métodos que realizam a permutação dos elementos no próprio vetor são chamados in situ, esses métodos são os preferidos. Os métodos que necessitam de memória extra para armazenar outra cópia dos itens possuem menor importância

Ordenação Externa:

Onde os elementos a serem ordenados não cabem na memória principal e os registros são acessados sequencialmente ou em grandes blocos.

Métodos de ordenação são considerados como estável se a ordem relativa dos itens iguais não se altera enquanto a ordenação está ocorrendo.

Insertion Sort

Insertion Sort ou ordenação por inserção é o método que percorre um vetor da esquerda para a direita e ordena os elementos à sua esquerda.

O funcionamento do algoritmo é simples: cada passo a partir do segundo elemento do vetor seleciona o próximo item e o coloca no local correto de acordo com o critério estabelecido para a ordenação.

Selection Sort

A ordenação por seleção ou selection sort consiste em selecionar o menor item e colocá-lo na primeira posição do vetor, selecionar o segundo menor item e colocar na segunda posição, e ir seguindo estes passos até que reste um único elemento.

Bubble Sort

Bubble sort é um algoritmo simples. O Bubble Sort compara os elementos dois a dois, por exemplo: compara-se a primeira posição do vetor com a segunda, na segunda repetição, compara-se a segunda posição do vetor com a terceira, e assim sucessivamente até que todos os elementos sejam ordenados.

Referencial Teórico:

Os métodos de ordenação, como explicado anteriormente, se dividem em Ordenação interna e Ordenação externa. Nesse trabalho utilizamos apenas os métodos internos.

Escolhemos três métodos de ordenação, o Bubble Sort, o Insertion Sort e o Selection Sort, a fim de compara-los e testar a eficácia dos 3 métodos na situação-problema apresentada no trabalho.

Bubble Sort:

Conforme citação escrita no livro “Métodos de Ordenação Interna”, O método de ordenação Bubble Sort usa uma estratégia de “comparação e troca”, que pode ser aplicada em vários vetores a ser ordenados (OLIVEIRA, 2002).

O Bubble Sort é o algoritmo mais antigo e mais simples usado para ordenações. Ele funciona comparando cada item da lista com o item do lado dele, e efetua a troca se o valor na posição que está sendo analisada for maior que o da posição após a dele. O algoritmo repete este processo até passar por todas as posições da lista. Isto faz com que os valores maiores “flutuem” para o final da lista, enquanto os valores menores “afundem” para o início da lista.

Este método tem o pior caso medido por O(n²), onde n é o número de elementos do vetor. Mesmo outros métodos como o insertion sort que tem pior caso denominado por O(n²), tendem a ter melhor desempenho que o método da bolha.

Vantagens: é um algoritmo de fácil implementação, algoritmo estável.

Limitações: É um dos métodos mais lentos.

Insertion Sort:

Dentre os métodos de inserção, o método da Inserção Direta é o mais simples, porém, é o mais rápido, entre os outros métodos considerados básicos. Neste algoritmo, o próprio vetor é utilizado no processo de ordenação, não consumindo, portanto, memória para a separação dos segmentos do vetor, é consumida um pouco de memória para armazenar as variáveis auxiliares.

Da mesma forma que o bolha o método de inserção possui o melhor caso com O(N), caso o vetor esteja totalmente ordenado, e complexidade O(N2),