O que é insertion sort?

Entendendo o Algoritmo de Insertion Sort: Uma Visão Completa

O insertion sort é um algoritmo de ordenação simples que constrói a lista final de forma incremental. Ele é eficiente para pequenos conjuntos de dados e é frequentemente utilizado como parte de algoritmos de ordenação mais complexos. Neste artigo, vamos explorar como o insertion sort funciona e sua relevância na programação.

Como Funciona o Insertion Sort

O insertion sort percorre o array da esquerda para a direita, construindo a ordenação à medida que avança. Ele compara cada elemento com os elementos já ordenados à sua esquerda e insere o elemento no local correto.

Vantagens e Desvantagens do Insertion Sort

Vantagens

• Eficiente para pequenos conjuntos de dados
• Requer apenas uma pequena quantidade de memória adicional

Desvantagens

• Ineficiente para grandes conjuntos de dados
• Complexidade de tempo O(n2) no pior caso

Aplicações do Insertion Sort

O insertion sort é frequentemente usado em aplicações onde o número de elementos é pequeno ou quando a estabilidade da ordenação é necessária, ou seja, quando a ordem relativa dos elementos iguais deve ser mantida.

Comparação com Outros Algoritmos de Ordenação

Diferente de algoritmos como quicksort ou mergesort, que são mais eficientes para grandes conjuntos de dados, o insertion sort se destaca pela sua simplicidade e eficiência em cenários específicos.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >=0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key