Análise do insertion sort

Assim como na ordenação por seleção, a ordenação por inserção itera pelos índices do array. Ele chama a função insert para os elementos nos índices $1,2,3,\dots ,n-1$‍. Como cada chamada a indexOfMinimum leva uma quantidade de tempo que depende do tamanho do subarray ordenado, a chamada a insert também leva. Na verdade, a palavra "leva" na frase anterior deveria ser substituída por "pode levar," e nós vamos ver o porquê.

Vamos analisar a situação onde nós chamamos insert e o valor que está sendo inserido em um subarray é menor que todos os elementos do subarray. Por exemplo, se estamos inserindo 0 no subarray [2, 3, 5, 7, 11], então todos os elementos no subarray têm de se deslocar uma posição para a direita. Então, em geral, se estamos inserindo em um subarray com $k$‍ elementos, todos os $k$‍ podem ter de se deslocar em uma posição Ao invés de contar exatamente quantas linhas de código nós precisamos para testar um elemento em relação a uma chave e deslocar o elemento, vamos concordar que é um número constante de linhas; vamos chamar essa constante de $c$‍. Portanto, poderia levar até $c\cdot k$‍ linhas para inserir em um subarray de $k$‍ elementos.

Suponha que em cada chamada de insert, o valor que está sendo inserido é menor que todos os elementos do subarray a sua esquerda. Quando chamamos insert a primeira vez, $k=1$‍. A segunda vez, $k=2$‍. A terceira, $k=3$‍. E assim por diante, até que a última vez, quando $k=n-1$‍. Portanto, o tempo gasto inserindo em um subarray ordenado é

$c\cdot 1+c\cdot 2+c\cdot 3+\cdots c\cdot (n-1)=c\cdot (1+2+3+\cdots +(n-1))$‍ .

Essa soma é uma série aritmética, exceto que ela vai até $n-1$‍ ao invés de $n$‍. Usando nossa fórmula para séries aritméticas, concluímos que o tempo total inserindo em um array ordenado é

$c\cdot (n-1+1)((n-1)/2)=c{n}^2/2-cn/2$‍ .

Usando a notação grande-Θ, nós descartamos o termo de baixa ordem $cn/2$‍ e os fatores constantes $c$‍ e 1/2, obtendo o resultado que o tempo para a ordenação por inserção, neste caso, é $\mathrm{\Theta }(n^2)$‍.

A ordenação por inserção pode levar menos que $\mathrm{\Theta }(n^2)$‍? A resposta é sim. Suponha que nós temos o array [2, 3, 5, 7, 11], onde o array ordenado são os quatro primeiros elementos, e nós estamos inserindo o valor 11. No primeiro teste, nós vemos que 11 é maior que 7, e então os elementos no subarray precisam se deslocar para a direita. Então essa chamada de insert leva só um tempo constante. Suponha que toda chamada deinsert leva um tempo constante. Como há $n-1$‍ chamadas de insert, se cada chamada leva um tempo que é uma constante $c$‍, então o tempo total para a ordenação por inserção é $c\cdot (n-1)$‍, que é $\mathrm{\Theta }(n)$‍, não $\mathrm{\Theta }(n^2)$‍.

Qualquer uma dessas situações pode ocorrer? Can each call to insert cause every element in the subarray to slide one position to the right? Can each call to insert cause no elements to slide? A resposta é sim para as duas perguntas. A call to insert causes every element to slide over if the key being inserted is less than every element to its left. So, if every element is less than every element to its left, the running time of insertion sort is $\mathrm{\Theta }(n^2)$‍. What would it mean for every element to be less than the element to its left? The array would have to start out in reverse sorted order, such as [11, 7, 5, 3, 2]. So a reverse-sorted array is the worst case for insertion sort.

E quanto ao caso oposto? A call to insert causes no elements to slide over if the key being inserted is greater than or equal to every element to its left. So, if every element is greater than or equal to every element to its left, the running time of insertion sort is $\mathrm{\Theta }(n)$‍. This situation occurs if the array starts out already sorted, and so an already-sorted array is the best case for insertion sort.

O que mais podemos dizer sobre o tempo de execução da ordenação por inserção? Suponha que o array comece com uma ordem aleatória. Then, on average, we'd expect that each element is less than half the elements to its left. In this case, on average, a call to insert on a subarray of $k$‍ elements would slide $k/2$‍ of them. The running time would be half of the worst-case running time. But in asymptotic notation, where constant coefficients don't matter, the running time in the average case would still be $\mathrm{\Theta }(n^2)$‍, just like the worst case.

E se você soubesse que o array está "quase ordenado": todo elemento começa num ponto que está no máximo um número constante de posições, digamos 17, de onde ele deve estar quando ordenado? Então cada chamada de insert desloca no máximo 17 elementos, e o tempo para cada chamada deinsert em um subarray de $k$‍ elementos seria no máximo $17\cdot c$‍. Em todas as $n-1$‍ chamadas de insert, o tempo de execução seria $17\cdot c\cdot (n-1)$‍, que é $\mathrm{\Theta }(n)$‍, da mesma forma que no melhor caso. Então a ordenação por inserção é mais rápida quando feita em um array quase ordenado.

Resumindo os tempos de execução da ordenação por inserção:

Se você tivesse que generalizar para todos os casos de ordenação por inserção, você teria de dizer que ela leva o tempo $O(n^2)$‍. Você não pode dizer que ela roda no tempo $\mathrm{\Theta }(n^2)$‍ em todos os casos, já que o melhor caso roda em $\mathrm{\Theta }(n)$‍. E você não pode dizer que ela roda em $\mathrm{\Theta }(n)$‍ em todos os casos, porque o pior tempo de execução é $\mathrm{\Theta }(n^2)$‍.

Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.