23 de dezembro de 2023
Algoritmo: Insertion Sort
Algoritmos
O que é
Insertion Sort é um algoritmo simples para ordenar itens. Ele começa comparando-os da esquerda para a direita. Funciona como ordenar um baralho na mão.
Vamos imaginar que estamos na faculdade de engenharia e precisamos jogar um truquinho. Você começa com a mão esquerda vazia e com a direita segura as cartas desordenadas na direita. A primeira carta do baralho vai para a mão esquerda. Você pega a segunda carta do baralho e a compara, do maior para o menor, com o da mão esquerda. Compare até achar a posição correta. Você faz isso até que todas as cartas da sua mão direita acabem. No final, se você fizer tudo certo, terá um baralho devidamente ordenado:
Implementação
Abaixo está a implementação em C:
1#include <stdio.h>
2#include <stdlib.h>
3
4int* insetion_sort(int numbers[], int length){
5 for (int i = 0; i < length; i++)
6 {
7 int key = numbers[i];
8 int j = i - 1;
9 while(j >= 0 && numbers[j] > key) {
10 numbers[j + 1] = numbers[j];
11 j = j - 1;
12 }
13 numbers[j + 1] = key;
14 }
15
16 return numbers;
17};Vamos rodar isso e ver o resultado:
1int main() {
2 int numbers[] = {1, 3, 2, 4, 7, 0};
3 int length = sizeof(numbers) / sizeof(numbers[0]);
4
5 int* result = insetion_sort(numbers, length);
6
7 printf("sorted: ");
8 for (int i = 0; i < length; i++) {
9 printf("%d ", result[i]);
10 }
11 printf("\\n");
12}1Output:
2sorted: 0 1 2 3 4 7
3[Done] exited with code=0 in 0.415 secondsTempo de execução
Insertion sort possui um tempo de execução de O(n²) em seu pior caso.
Referência
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd edition, MIT Press, 2009.