Resumo de Insertion sort (ordenação por inserção)

## Ordenação por Inserção: Princípios Fundamentais A ordenação por inserção é um algoritmo simples e intuitivo para organizar elementos em uma lista. Imagine que você está organizando um baralho de cartas na sua mão: você pega uma carta nova e a insere no lugar certo entre as cartas que você já tem em ordem. É exatamente assim que a ordenação por inserção funciona! Este algoritmo é particularmente útil para listas pequenas ou para aquelas que já estão um pouco organizadas. Sua simplicidade o torna fácil de entender e implementar. ### Como Funciona a Ordenação por Inserção? O algoritmo constrói uma lista ordenada passo a passo. Ele pega um elemento por vez da parte "desordenada" da lista e o coloca na posição correta dentro da parte que já está "ordenada". Pense nisso como ter uma sublista à esquerda que sempre permanece ordenada. Vamos detalhar o processo: 1. **Início**: Consideramos que o primeiro elemento da lista (na posição $0$) já está "ordenado" por si só. Ele forma nossa primeira sublista ordenada, de tamanho $1$. 2. **Repetição**: Para cada elemento seguinte na lista (do índice $1$ até o último): a. **Escolha do Elemento**: Selecionamos o elemento atual para ser inserido. Este é o que chamamos de "chave". b. **Comparação e Deslocamento**: A chave é comparada com os elementos da sublista já ordenada, começando do último elemento ordenado e movendo para a esquerda. Se um elemento na sublista ordenada for maior que a chave, ele é deslocado uma posição para a direita para abrir espaço. c. **Inserção**: Quando encontramos uma posição onde todos os elementos à esquerda são menores ou iguais à chave, e todos os elementos à direita são maiores ou iguais à chave, inserimos a chave ali. Este ciclo continua até que todos os elementos tenham sido inseridos na sublista ordenada, resultando em uma lista completamente organizada. > **Definição**: A **chave** é o elemento atual que está sendo processado e inserido na parte ordenada da lista durante o algoritmo de ordenação por inserção. ### Exemplo Passo a Passo Vamos aplicar a ordenação por inserção à lista `[5, 2, 4, 6, 1, 3]`. **Lista Inicial:** `[5, 2, 4, 6, 1, 3]` 1. **Passo 1: Processando o valor $2$ (índice $1$)** * Sublista ordenada: `[5]`. A chave é $2$. * Comparamos $2$ com $5$. Como $2 < 5$, o $5$ é deslocado para a direita. * Inserimos $2$ na posição vazia. * **Lista Atual:** `[2, 5, 4, 6, 1, 3]` 2. **Passo 2: Processando o valor $4$ (índice $2$)** * Sublista ordenada: `[2, 5]`. A chave é $4$. * Comparamos $4$ com $5$. Como $4 < 5$, o $5$ é deslocado para a direita. * Comparamos $4$ com $2$. Como $4 > 2$, $4$ é inserido logo após o $2$. * **Lista Atual:** `[2, 4, 5, 6, 1, 3]` 3. **Passo 3: Processando o valor $6$ (índice $3$)** * Sublista ordenada: `[2, 4, 5]`. A chave é $6$. * Comparamos $6$ com $5$. Como $6 > 5$, o $6$ já está na posição correta em relação ao $5$. Não há deslocamentos. * **Lista Atual:** `[2, 4, 5, 6, 1, 3]` 4. **Passo 4: Processando o valor $1$ (índice $4$)** * Sublista ordenada: `[2, 4, 5, 6]`. A chave é $1$. * Comparamos $1$ com $6$. O $6$ é deslocado. * Comparamos $1$ com $5$. O $5$ é deslocado. * Comparamos $1$ com $4$. O $4$ é deslocado. * Comparamos $1$ com $2$. O $2$ é deslocado. * Inserimos $1$ na primeira posição. * **Lista Atual:** `[1, 2, 4, 5, 6, 3]` 5. **Passo 5: Processando o valor $3$ (índice $5$)** * Sublista ordenada: `[1, 2, 4, 5, 6]`. A chave é $3$. * Comparamos $3$ com $6$. O $6$ é deslocado. * Comparamos $3$ com $5$. O $5$ é deslocado. * Comparamos $3$ com $4$. O $4$ é deslocado. * Comparamos $3$ com $2$. Como $3 > 2$, $3$ é inserido logo após o $2$. * **Lista Final:** `[1, 2, 3, 4, 5, 6]` A lista agora está completamente ordenada! Did you know that although other sorting algorithms like QuickSort or MergeSort are generally faster for large datasets, Inse