Métodos de ordenação

1. INTRODUÇÃO Ordenação corresponde ao método de rearranjar um conjunto de objetos em uma ordem crescente ou decrescente. Tem como objetivo facilitar a recuperação dos itens do conjunto, um exemplo simples é a procura de um nome em uma lista telefônica, imagine se os nomes estivessem totalmente desordenados, levaria um tempo absurdo. A atividade de colocar as coisas em ordem está presente na maioria das aplicações em que os objetos armazenados têm de ser pesquisados e recuperados. Neste trabalho, com exemplos simples e de fácil entendimento, serão apresentados quatro tipos de ordenações.

 Inserção
 Seleção
 Intercalação
 Particionamento

2. ORDENAÇÃO POR INSERÇÃO (Insertion Sort)

Eficiente para ordenar um pequeno número de elementos, sendo que demoraria muito para aplicar uma lista grande de elementos. Funciona da seguinte forma: o dado é comparado ao anterior, se o anterior for maior eles trocam de lugar, ou seja, ele vai jogando os dados menores à esquerda. Na figura abaixo temos um exemplo da ordenação por inserção.

Figura 01: Exemplo de implementação Insertion Sort

2.1. Complexidade do Caso

Pior caso: Dados completamente fora de ordem.

O(n²)

Caso médio: Dados estão em ordem aleatória.

O(n²).

Melhor caso: Dados estão ordenados.

O(n).

2.2. Vantagens e Desvantagens

Vantagens:
 Fácil implementação;
 Algoritmo Estável;
 O vetor já ordenado favorece a ordenação.

Desvantagens
 Número grande de movimentações;
 Ordem de complexidade quadrática;
 Ineficiente quando o vetor está ordenado inversamente.

2.3. Código

Figura 02: Código em linguagem C# do método Insertion Sort

3. ORDENAÇÃO POR SELEÇÃO (Selection Sort)

Algoritmo simples. Se basea em pegar o menor elemento da