Melhor resposta
Em primeiro lugar, deve-se perguntar por que usar um algoritmo de classificação quadrática quando existem alternativas assintoticamente mais rápidas, como mergesort ou quicksort. Para matrizes pequenas (menos de 20-30 elementos), a classificação por inserção e a classificação por seleção são normalmente mais rápidas do que as alternativas O (n * logn). Na verdade, muitos algoritmos de classificação baseados no paradigma dividir e conquistar mudam para classificação por inserção ou classificação por seleção quando a matriz é pequena o suficiente.
Entre classificação por inserção e classificação por seleção, quando usar quais?
Normalmente, a classificação por inserção realizará menos comparações do que a classificação por seleção, dependendo do grau de “classificação” da matriz. Embora a ordenação por seleção deva varrer as partes restantes da matriz ao colocar um elemento, a ordenação por inserção examina apenas quantos elementos forem necessários. Isso significa que quando a matriz já está classificada ou quase classificada, a classificação por inserção é executada no tempo O (n).
Uma vantagem da classificação por seleção sobre a classificação por inserção é que o número de gravações (trocas) está em O (n), enquanto na classificação por inserção está em O (n ^ 2). Isso pode ser importante se você estiver classificando na memória Flash, por exemplo, porque as gravações reduzem a vida útil da memória Flash.
Resposta
Em uma classificação de seleção, para cada elemento que deve ser adicionado à seção classificada, você deve examinar inteira a parte não classificada da lista para encontrar o elemento mínimo restante. Em uma classificação por inserção, você deve pesquisar a seção classificada para descobrir para onde vai o próximo elemento, mas a pesquisa termina assim que você encontrar o ponto de inserção (cerca de metade na média da seção classificada).
Portanto, a classificação por seleção requer N / 2 comparações em média para cada elemento a ser adicionado à seção classificada e a classificação por inserção exige N / 4 comparações em média. No entanto, a classificação por inserção tem uma penalidade de tempo adicional ao classificar uma matriz. Cada uma das comparações N / 4 (em média) requer que o elemento seja deslocado para cima, de forma que também haja N / 4 movimentos, bem como comparações. A ordenação por seleção requer apenas uma única troca.
No geral, a ordenação por inserção geralmente vence a corrida. Isso é especialmente verdadeiro se houver funções rápidas de “movimentação de bloco” (para matrizes).