Conteúdo principal
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 . Como cada chamada a
insert
para os elementos nos índices 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 elementos, todos os 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 . Portanto, poderia levar até linhas para inserir em um subarray de elementos.
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 Suponha que em cada chamada de . A segunda vez, . A terceira, . E assim por diante, até que a última vez, quando . Portanto, o tempo gasto inserindo em um subarray ordenado é
insert
, o valor que está sendo inserido é menor que todos os elementos do subarray a sua esquerda. Quando chamamos insert
a primeira vez, Essa soma é uma série aritmética, exceto que ela vai até ao invés de . Usando nossa fórmula para séries aritméticas, concluímos que o tempo total inserindo em um array ordenado é
Usando a notação grande-Θ, nós descartamos o termo de baixa ordem e os fatores constantes e 1/2, obtendo o resultado que o tempo para a ordenação por inserção, neste caso, é .
A ordenação por inserção pode levar menos que ? 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 chamadas de , então o tempo total para a ordenação por inserção é , que é , não .
insert
leva só um tempo constante. Suponha que toda chamada deinsert
leva um tempo constante. Como há insert
, se cada chamada leva um tempo que é uma constante Qualquer uma dessas situações pode ocorrer? Can each call to . 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.
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 E quanto ao caso oposto? A call to . This situation occurs if the array starts out already sorted, and so an already-sorted array is the best case for insertion sort.
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 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 elements would slide 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 , just like the worst case.
insert
on a subarray of 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 elementos seria no máximo . Em todas as chamadas de , que é , 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.
insert
desloca no máximo 17 elementos, e o tempo para cada chamada deinsert
em um subarray de insert
, o tempo de execução seria Resumindo os tempos de execução da ordenação por inserção:
- Pior caso:
. - Melhor caso:
. - Caso médio para um arranjo aleatório:
. - Caso de arranjo "quase ordenado":
.
Se você tivesse que generalizar para todos os casos de ordenação por inserção, você teria de dizer que ela leva o tempo . Você não pode dizer que ela roda no tempo em todos os casos, já que o melhor caso roda em . E você não pode dizer que ela roda em em todos os casos, porque o pior tempo de execução é .
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.
Quer participar da conversa?
- faltam traduções nos parágrafos 7 e 9(1 voto)