Classificação de inserção - Insertion sort

Classificação de inserção

Animação de classificação de inserção
Classe	Algoritmo de classificação
Estrutura de dados	Variedade
Desempenho de pior caso	${\ displaystyle O (n ^ {2})}$ comparações e trocas
Melhor caso de desempenho	${\ displaystyle O (n)}$comparações, trocas${\ displaystyle O (1)}$
Desempenho médio	${\ displaystyle O (n ^ {2})}$ comparações e trocas
Pior caso de complexidade de espaço	${\ displaystyle O (n)}$total, auxiliar${\ displaystyle O (1)}$

A classificação por inserção é um algoritmo de classificação simples que constrói a matriz final classificada (ou lista), um item de cada vez. É muito menos eficiente em listas grandes do que algoritmos mais avançados, como quicksort , heapsort ou merge sort . No entanto, a classificação por inserção oferece várias vantagens:

• Implementação simples: Jon Bentley mostra uma versão C de três linhas e uma versão otimizada de cinco linhas
• Eficiente para conjuntos de dados (bastante) pequenos, bem como outros algoritmos de classificação quadrática
• Mais eficiente na prática do que a maioria dos outros algoritmos quadráticos simples (ou seja, O ( n ² )), como classificação por seleção ou classificação por bolha
• Adaptativo , ou seja, eficiente para conjuntos de dados que já estão substancialmente classificados: a complexidade do tempo é O ( kn ) quando cada elemento na entrada está a não mais do que k lugares de sua posição classificada
• Estável ; ou seja, não altera a ordem relativa dos elementos com chaves iguais
• No local ; ou seja, requer apenas uma quantidade constante O (1) de espaço de memória adicional
• Online ; ou seja, pode classificar uma lista à medida que a recebe

Quando as pessoas classificam as cartas manualmente em uma mão de bridge , a maioria usa um método semelhante à classificação por inserção.

Algoritmo

Um exemplo gráfico de classificação por inserção. A lista parcial classificada (preta) contém inicialmente apenas o primeiro elemento da lista. Com cada iteração, um elemento (vermelho) é removido dos dados de entrada "ainda não verificado para pedido" e inserido no local na lista classificada.

A classificação por inserção itera , consumindo um elemento de entrada a cada repetição e aumenta uma lista de saída classificada. A cada iteração, a classificação por inserção remove um elemento dos dados de entrada, encontra o local ao qual pertence na lista classificada e o insere ali. Ele se repete até que nenhum elemento de entrada permaneça.

A classificação normalmente é feita no local, iterando o array, aumentando a lista classificada por trás dele. Em cada posição da matriz, ele verifica o valor ali em relação ao maior valor na lista classificada (que por acaso está ao lado dele, na posição da matriz anterior marcada). Se for maior, ele deixa o elemento no lugar e passa para o próximo. Se for menor, ele encontra a posição correta na lista classificada, desloca todos os valores maiores para cima para criar um espaço e insere na posição correta.

A matriz resultante após k iterações tem a propriedade em que as primeiras k + 1 entradas são classificadas ("+1" porque a primeira entrada é ignorada). Em cada iteração, a primeira entrada restante da entrada é removida e inserida no resultado na posição correta, estendendo assim o resultado:

torna-se

com cada elemento maior que x copiado para a direita quando é comparado com x .

A variante mais comum de classificação por inserção, que opera em matrizes, pode ser descrita da seguinte maneira:

1. Suponha que exista uma função chamada Insert projetada para inserir um valor em uma seqüência classificada no início de um array. Ele opera começando no final da sequência e deslocando cada elemento um lugar para a direita até que uma posição adequada seja encontrada para o novo elemento. A função tem o efeito colateral de sobrescrever o valor armazenado imediatamente após a seqüência classificada na matriz.
2. Para realizar uma classificação por inserção, comece no elemento mais à esquerda da matriz e invoque Insert para inserir cada elemento encontrado em sua posição correta. A seqüência ordenada na qual o elemento é inserido é armazenada no início da matriz no conjunto de índices já examinado. Cada inserção substitui um único valor: o valor que está sendo inserido.

Segue-se o pseudocódigo do algoritmo completo, em que as matrizes são baseadas em zero :

i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

O loop externo passa por todos os elementos, exceto o primeiro, porque o prefixo de elemento único A[0:1]é classificado trivialmente, de modo que a invariável com que as primeiras ientradas são classificadas é verdadeira desde o início. O loop interno move o elemento A[i]para seu lugar correto para que, após o loop, os primeiros i+1elementos sejam classificados. Observe que o andoperador no teste deve usar avaliação de curto-circuito , caso contrário, o teste pode resultar em um erro de limite de array , quando j=0e tenta avaliar A[j-1] > A[j](ou seja, A[-1]falha de acesso ).

Depois de expandir a swapoperação no local como x ← A[j]; A[j] ← A[j-1]; A[j-1] ← x(onde xé uma variável temporária), uma versão um pouco mais rápida pode ser produzida que se move A[i]para sua posição de uma vez e executa apenas uma atribuição no corpo do loop interno:

i ← 1
while i < length(A)
    x ← A[i]
    j ← i - 1
    while j >= 0 and A[j] > x
        A[j+1] ← A[j]
        j ← j - 1
    end while
    A[j+1] ← x
    i ← i + 1
end while

O novo loop interno desloca elementos para a direita para liberar uma vaga x = A[i].

O algoritmo também pode ser implementado de forma recursiva. A recursão apenas substitui o loop externo, chamando a si mesma e armazenando valores sucessivamente menores de n na pilha até que n seja igual a 0, onde a função retorna para cima na cadeia de chamadas para executar o código após cada chamada recursiva começando com n igual a 1, com n aumentando em 1 conforme cada instância da função retorna à instância anterior. A chamada inicial seria insertionSortR (A, length (A) -1) .

function insertionSortR(array A, int n)
    if n > 0
        insertionSortR(A, n-1)
        x ← A[n]
        j ← n-1
        while j >= 0 and A[j] > x
            A[j+1] ← A[j]
            j ← j-1
        end while
        A[j+1] ← x
    end if
end function

Não torna o código mais curto, também não reduz o tempo de execução, mas aumenta o consumo de memória adicional de O (1) para O (N) (no nível mais profundo de recursão, a pilha contém N referências para o Aarray, cada um com o valor de acompanhamento da variável nde N até 1).

Melhores, piores e médios casos

O melhor caso de entrada é uma matriz que já está classificada. Nesse caso, a classificação por inserção tem um tempo de execução linear (ou seja, O ( n )). Durante cada iteração, o primeiro elemento restante da entrada é apenas comparado com o elemento mais à direita da subseção classificada da matriz.

A entrada de pior caso mais simples é uma matriz classificada em ordem reversa. O conjunto de todas as entradas de pior caso consiste em todas as matrizes em que cada elemento é o menor ou o segundo menor dos elementos anteriores. Nestes casos, cada iteração do loop interno varrerá e deslocará toda a subseção classificada do array antes de inserir o próximo elemento. Isso dá à classificação por inserção um tempo de execução quadrático (ou seja, O ( n ² )).

O caso médio também é quadrático, o que torna a classificação por inserção impraticável para classificar matrizes grandes. No entanto, a classificação por inserção é um dos algoritmos mais rápidos para classificar matrizes muito pequenas, ainda mais rápido do que a classificação rápida ; de fato, boas implementações de quicksort usam classificação por inserção para matrizes menores que um certo limite, também quando surgem como subproblemas; o limite exato deve ser determinado experimentalmente e depende da máquina, mas normalmente fica em torno de dez.

Exemplo: A tabela a seguir mostra as etapas para classificar a sequência {3, 7, 4, 9, 5, 2, 6, 1}. Em cada etapa, a chave em consideração é sublinhada. A chave que foi movida (ou deixada no lugar porque era a maior já considerada) na etapa anterior está marcada com um asterisco.

3  7  4  9  5  2  6  1
3* 7  4  9  5  2  6  1
3  7* 4  9  5  2  6  1
3  4* 7  9  5  2  6  1
3  4  7  9* 5  2  6  1
3  4  5* 7  9  2  6  1
2* 3  4  5  7  9  6  1
2  3  4  5  6* 7  9  1
1* 2  3  4  5  6  7  9

Relação com outros algoritmos de classificação

A classificação por inserção é muito semelhante à classificação por seleção . Como na classificação por seleção, depois que k passa pelo array, os primeiros k elementos estão em ordem de classificação. No entanto, a diferença fundamental entre os dois algoritmos é que a classificação por inserção faz a varredura para trás a partir da chave atual, enquanto a classificação por seleção faz a varredura para a frente. Isso resulta na classificação por seleção tornando os primeiros k elementos os k menores elementos da entrada não classificada, enquanto na classificação por inserção eles são simplesmente os primeiros k elementos da entrada.

A principal vantagem da classificação por inserção sobre a classificação por seleção é que a classificação por seleção deve sempre examinar todos os elementos restantes para encontrar o menor elemento absoluto na parte não classificada da lista, enquanto a classificação por inserção requer apenas uma única comparação quando o ( k  + 1) -st elemento é maior que o k -ésimo elemento; quando isso é frequentemente verdadeiro (como se a matriz de entrada já estiver classificada ou parcialmente classificada), a classificação por inserção é distintamente mais eficiente em comparação com a classificação por seleção. Em média (assumindo que a classificação do ( k  + 1) -ésimo elemento é aleatória), a classificação por inserção exigirá a comparação e deslocamento da metade dos k elementos anteriores , o que significa que a classificação por inserção realizará cerca de metade das comparações da classificação por seleção em média.

No pior caso de classificação por inserção (quando a matriz de entrada é classificada de forma reversa), a classificação por inserção executa tantas comparações quanto a classificação por seleção. No entanto, uma desvantagem da classificação por inserção sobre a classificação por seleção é que ela requer mais gravações devido ao fato de que, em cada iteração, inserir o ( k  + 1) -ésimo elemento na parte classificada da matriz requer muitas trocas de elemento para deslocar todos dos seguintes elementos, enquanto apenas uma única troca é necessária para cada iteração de classificação de seleção. Em geral, a classificação por inserção gravará no array O ( n ² ) vezes, enquanto a classificação por seleção gravará apenas O ( n ) vezes. Por esse motivo, a classificação por seleção pode ser preferível nos casos em que a gravação na memória é significativamente mais cara do que a leitura, como com EEPROM ou memória flash .

Enquanto alguns algoritmos de divisão e conquista , como quicksort e mergesort superam a classificação por inserção para matrizes maiores, os algoritmos de classificação não recursivos, como classificação por inserção ou seleção de seleção são geralmente mais rápidos para matrizes muito pequenas (o tamanho exato varia de acordo com o ambiente e implementação, mas é normalmente entre 7 e 50 elementos). Portanto, uma otimização útil na implementação desses algoritmos é uma abordagem híbrida, usando o algoritmo mais simples quando a matriz é dividida em um tamanho pequeno.

Variantes

DL Shell fez melhorias substanciais no algoritmo; a versão modificada é chamada de classificação Shell . O algoritmo de classificação compara elementos separados por uma distância que diminui a cada passagem. A classificação Shell melhorou nitidamente os tempos de execução no trabalho prático, com duas variantes simples exigindo tempo de execução O ( n ^3/2 ) e O ( n ^4/3 ).

Se o custo das comparações exceder o custo das trocas, como é o caso, por exemplo, de chaves de string armazenadas por referência ou com interação humana (como escolher uma de um par exibido lado a lado), então o uso de classificação por inserção binária pode resultar melhor performance. A ordenação por inserção binária emprega uma pesquisa binária para determinar a localização correta para inserir novos elementos e, portanto, realiza comparações ⌈log ₂  n ⌉ no pior caso. Quando cada elemento da matriz é pesquisado e inserido, é O ( n  log  n ). O algoritmo como um todo ainda tem um tempo de execução de O ( n ² ) em média devido à série de trocas necessárias para cada inserção.

O número de trocas pode ser reduzido calculando a posição de vários elementos antes de movê-los. Por exemplo, se a posição alvo de dois elementos for calculada antes de eles serem movidos para a posição adequada, o número de trocas pode ser reduzido em cerca de 25% para dados aleatórios. Em casos extremos, essa variante funciona de maneira semelhante à classificação por mesclagem .

Uma variante chamada classificação de mesclagem binária usa uma classificação de inserção binária para classificar grupos de 32 elementos, seguido por uma classificação final usando classificação de mesclagem . Ele combina a velocidade de classificação por inserção em pequenos conjuntos de dados com a velocidade de classificação por mesclagem em grandes conjuntos de dados.

Para evitar ter que fazer uma série de trocas para cada inserção, a entrada pode ser armazenada em uma lista encadeada , o que permite que os elementos sejam agrupados dentro ou fora da lista em tempo constante quando a posição na lista for conhecida. No entanto, pesquisar uma lista vinculada requer seguir sequencialmente os links até a posição desejada: uma lista vinculada não tem acesso aleatório, portanto, não pode usar um método mais rápido, como a pesquisa binária. Portanto, o tempo de execução necessário para a pesquisa é O ( n ) e o tempo para a classificação é O ( n ² ). Se uma estrutura de dados mais sofisticada (por exemplo, heap ou árvore binária ) for usada, o tempo necessário para pesquisa e inserção pode ser reduzido significativamente; esta é a essência da classificação de heap e da classificação de árvore binária .

Em 2006, Bender, Martin Farach-Colton e Mosteiro publicaram uma nova variante do tipo de inserção chamada library sort ou gapped insertion sort que deixa um pequeno número de espaços não utilizados (ou seja, "lacunas") espalhados por todo o array. A vantagem é que as inserções precisam apenas deslocar os elementos até que uma lacuna seja alcançada. Os autores mostram que esse algoritmo de classificação é executado com alta probabilidade em tempo O ( n  log  n ).

Se uma lista de ignorar for usada, o tempo de inserção é reduzido para O (log  n ) e as trocas não são necessárias porque a lista de ignorar é implementada em uma estrutura de lista vinculada. O tempo final de execução para a inserção seria O ( n  log  n ).

A classificação por inserção de lista é uma variante da classificação por inserção. Reduz o número de movimentos.

Código de classificação de inserção de lista em C

Se os itens forem armazenados em uma lista vinculada, a lista pode ser classificada com O (1) espaço adicional. O algoritmo começa com uma lista inicialmente vazia (e, portanto, trivialmente classificada). Os itens de entrada são retirados da lista um de cada vez e, em seguida, inseridos no local adequado na lista classificada. Quando a lista de entrada está vazia, a lista classificada tem o resultado desejado.

struct LIST * SortList1(struct LIST * pList) 
{
    // zero or one element in list
    if (pList == NULL || pList->pNext == NULL)
        return pList;
    // head is the first element of resulting sorted list
    struct LIST * head = NULL;
    while (pList != NULL) {
        struct LIST * current = pList;
        pList = pList->pNext;
        if (head == NULL || current->iValue < head->iValue) {
            // insert into the head of the sorted list
            // or as the first element into an empty sorted list
            current->pNext = head;
            head = current;
        } else {
            // insert current element into proper position in non-empty sorted list
            struct LIST * p = head;
            while (p != NULL) {
                if (p->pNext == NULL || // last element of the sorted list
                    current->iValue < p->pNext->iValue) // middle of the list
                {
                    // insert into middle of the sorted list or as the last element
                    current->pNext = p->pNext;
                    p->pNext = current;
                    break; // done
                }
                p = p->pNext;
            }
        }
    }
    return head;
}

O algoritmo abaixo usa um ponteiro final para a inserção na lista classificada. Um método recursivo mais simples reconstrói a lista a cada vez (ao invés de splicing) e pode usar o espaço de pilha O ( n ).

struct LIST
{
  struct LIST * pNext;
  int           iValue;
};

struct LIST * SortList(struct LIST * pList)
{
  // zero or one element in list
  if (!pList || !pList->pNext)
      return pList;

  /* build up the sorted array from the empty list */
  struct LIST * pSorted = NULL;

  /* take items off the input list one by one until empty */
  while (pList != NULL) {
      /* remember the head */
      struct LIST *   pHead  = pList;
      /* trailing pointer for efficient splice */
      struct LIST ** ppTrail = &pSorted;

      /* pop head off list */
      pList = pList->pNext;

      /* splice head into sorted list at proper place */
      while (!(*ppTrail == NULL || pHead->iValue < (*ppTrail)->iValue)) { /* does head belong here? */
          /* no - continue down the list */
          ppTrail = &(*ppTrail)->pNext;
      }

      pHead->pNext = *ppTrail;
      *ppTrail = pHead;
  }

  return pSorted;
}

Referências

Leitura adicional

• Knuth, Donald (1998), "5.2.1: Sorting by Insertion", The Art of Computer Programming , 3. Sorting and Searching (segunda edição), Addison-Wesley, pp. 80-105, ISBN 0-201-89685-0.

links externos

• Algoritmos de classificação animados: classificação por inserção na máquina Wayback (arquivado em 8 de março de 2015) - demonstração gráfica
• Adamovsky, John Paul, Binary Insertion Sort - Scoreboard - Complete Investigation and C Implementation , Pathcom.
• Insertion Sort - uma comparação com outros algoritmos de classificação O (n ² ) , UK : Core war.
• Insertion sort (C) (wiki), LiteratePrograms - implementações de ordenação por inserção em C e várias outras linguagens de programação