Existem vários algoritmos básicos para resolver o problema de ordenar um array. Um dos mais famosos entre eles é a ordenação por inserção. Devido à sua clareza e simplicidade, mas baixa eficiência, este método é utilizado principalmente no ensino de programação. Ele permite que você entenda os mecanismos básicos de classificação.
Descrição do algoritmo
A essência do algoritmo de ordenação por inserção é que um segmento ordenado corretamente é formado dentro do array inicial. Cada elemento é comparado um a um com a peça marcada e inserido no lugar certo. Assim, após percorrer todos os elementos, eles se alinham na ordem correta.
A ordem de seleção dos elementos pode ser qualquer, eles podem ser selecionados arbitrariamente ou de acordo com algum algoritmo. Na maioria das vezes, a enumeração sequencial é usada a partir do início do array, onde um segmento ordenado é formado.
O início da ordenação pode ser assim:
- Pegue o primeiro elemento do array.
- Como não há nada para comparar, pegue o próprio elemento conforme ordenadosequência.
- Vá para o segundo item.
- Compare-o com o primeiro com base na regra de classificação.
- Se necessário, troque os elementos nos lugares.
- Tome os dois primeiros elementos como uma sequência ordenada.
- Vá para o terceiro item.
- Compare com o segundo, troque se necessário.
- Se a substituição for feita, compare-a com a primeira.
- Tome três elementos como uma sequência ordenada.
E assim sucessivamente até o final do array original.
Ordenação por inserção na vida real
Para maior clareza, vale a pena dar um exemplo de como esse mecanismo de classificação é usado na vida cotidiana.
Tome, por exemplo, uma carteira. Notas de cem, quinhentos e mil dólares estão em desordem no compartimento de notas. Isso é uma bagunça, em tal confusão é difícil encontrar imediatamente o pedaço de papel certo. A matriz de notas deve ser ordenada.
A primeira é uma nota de 1000 rublos, e imediatamente depois - 100. Pegamos cem e colocamos na frente. O terceiro consecutivo é de 500 rublos, o lugar certo para isso é entre cem e mil.
Da mesma forma que ordenamos as cartas recebidas ao jogar o "Tolo" para facilitar a navegação.
Operadores e funções auxiliares
O método de ordenação por inserção recebe como entrada um array inicial a ser ordenado, uma função de comparação e, se necessário, uma função que determina a regra de enumeração de elementos. Mais frequentemente usado em vezinstrução de loop regular.
O primeiro elemento é um conjunto ordenado, então a comparação começa a partir do segundo.
O algoritmo geralmente usa uma função auxiliar para trocar dois valores (swap). Ele usa uma variável temporária adicional, que consome memória e torna o código um pouco mais lento.
Uma alternativa é deslocar em massa um grupo de elementos e então inserir o atual no espaço livre. Nesse caso, a transição para o próximo elemento ocorre quando a comparação deu um resultado positivo, o que indica a ordem correta.
Exemplos de implementação
A implementação específica depende muito da linguagem de programação usada, sua sintaxe e estruturas.
Implementação clássica do C usando uma variável temporária para trocar valores:
int i, j, temp; for (i=1; i =0; j--) { if (array[j] < temp) break; matriz[j + 1]=matriz[j]; array[j]=temp; } }
Implementação do PHP:
function insert_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Aqui, primeiro, todos os elementos que não correspondem à condição de classificação são deslocados para a direita e, em seguida, o elemento atual é inserido no espaço livre.
Código Java usando loop while:
public static void insertSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } } }
O significado geral do código permanece in alterado: cada elemento do array é comparado sequencialmente com os anteriores e trocado com eles se necessário.
Tempo de execução estimado
Obviamente, na melhor das hipóteses, a entrada do algoritmo será um array já ordenado da maneira correta. Nessa situação, o algoritmo simplesmente terá que verificar cada elemento para garantir que esteja no lugar certo sem fazer trocas. Assim, o tempo de execução dependerá diretamente do comprimento do array original O(n).
O pior caso de entrada é um array ordenado em ordem inversa. Isso exigirá um grande número de permutações, a função de tempo de execução dependerá do número de elementos ao quadrado.
O número exato de permutações para um array completamente não ordenado pode ser calculado usando a fórmula:
n(n-1)/2
onde n é o comprimento do array original. Assim, seriam necessárias 4950 permutações para organizar 100 elementos na ordem correta.
O método de inserção é muito eficiente para ordenar arrays pequenos ou parcialmente ordenados. No entanto, não é recomendado aplicá-lo em todos os lugares devido à alta complexidade dos cálculos.
O algoritmo é usado como auxiliar em muitos outros métodos de ordenação mais complexos.
Ordenar valores iguais
O algoritmo de inserção pertence às chamadas ordenações estáveis. Isso significa,que não troca elementos idênticos, mas preserva sua ordem original. O índice de estabilidade é, em muitos casos, importante para a ordenação correta.
O exemplo acima é um ótimo exemplo visual de ordenação por inserção em uma dança.
