Índice analítico[Ocultar][Mostrar]
A informática trata de comprender as complexidades dos algoritmos e das estruturas de datos.
Tes unha lista de elementos que hai que ordenar, pero non tes tempo nin recursos para usar un algoritmo de clasificación máis complexo.
A clasificación por inserción é un dos algoritmos de ordenación máis sinxelos, pero pode ser lenta para listas grandes.
A fácil implementación e comprensión fixeron deste método un favorito entre os programadores. É perfecto para listas pequenas ou cando necesitas unha solución rápida.
Nesta entrada do blog, analizaremos a complexidade temporal da ordenación da inserción. Este algoritmo úsase para ordenar matrices e ten un tempo de execución de O(n2). Isto significa que a complexidade do tempo aumenta co tamaño da matriz.
Non obstante, este algoritmo pode ser máis rápido que outros algoritmos de clasificación, como a clasificación rápida.
Vexamos máis de cerca como funciona a ordenación por inserción.
Que é o algoritmo de clasificación por inserción?
Un elemento á vez, a ordenación por inserción xera unha matriz ordenable, que se denomina frecuentemente como lista.
Por exemplo, a ordenación aplícase en programas informáticos complicados como os compiladores, onde a orde dos tokens é importante para a interpretación do programa.
Como funciona a clasificación por inserción?
Cando usamos a ordenación por inserción para ordenar unha matriz, o algoritmo comeza por atopar o elemento máis pequeno da lista e inserilo na posición correcta.
Despois atopa o seguinte elemento máis pequeno e insíreo na posición correcta, etc.
O algoritmo funciona recorrendo a lista, comparando cada elemento co que lle precede.
Se os elementos están na orde incorrecta, o algoritmo intercambiaos. Despois verifica se a lista está ordenada e, se o está, o algoritmo remata.
Na práctica, a ordenación por inserción adoita implementarse usando algunhas liñas de código, polo que é unha opción popular para ordenar matrices pequenas. Non obstante, debe considerarse a complexidade do tempo ao usar este algoritmo.
Exemplo:
Aquí tes un exemplo de como funciona a ordenación por inserción. Usaremos a seguinte matriz:
1, 2, 3, 4, 5, 6
O algoritmo comeza atopando o elemento máis pequeno da lista, que é 1. Despois insíreo na posición correcta, a primeira posición. Despois atopa o seguinte elemento máis pequeno, que é 2. Insíreo na posición correcta, que é a segunda posición.
Despois atopa o seguinte elemento máis pequeno, que é 3. Insíreo na posición correcta, que é a terceira posición.
Despois atopa o seguinte elemento máis pequeno, que é 4. Insíreo na posición correcta, que é a cuarta posición, etc. A lista xa está ordenada!
Podemos ver polo exemplo que o algoritmo leva seis comparacións e intercambios para ordenar a lista. Isto é porque leva n2 comparacións e intercambios para ordenar unha lista de n elementos. Neste caso, n=6.
Como mellorar a complexidade do tempo de clasificación de inserción?
Mentres que a ordenación por inserción ten un tempo de execución de O(n2), pódese mellorar usando un mellor algoritmo de clasificación, como quicksort.
Quicksort ten un tempo de execución O(n log n), que é moito máis rápido que O(n2).
Non obstante, nalgúns casos, a clasificación por inserción pode ser máis rápida que a clasificación rápida.
Por exemplo, se a lista xa está en orde, a ordenación por inserción levará menos tempo que a clasificación rápida.
Na práctica, a ordenación por inserción adoita implementarse usando algunhas liñas de código, polo que é unha opción popular para ordenar matrices pequenas.
Non obstante, debe considerarse a complexidade do tempo ao usar este algoritmo.
Complexidades temporais
Complexidade do peor caso O(n2):
A complexidade do tempo aumenta co tamaño da matriz. Leva n2 comparacións e intercambios para ordenar unha lista de n elementos.
Por exemplo, se temos unha matriz de tamaño 1000, o algoritmo levará 1,000,000 de comparacións e intercambios para ordenar a matriz.
Complexidade do mellor caso O(n):
A complexidade do tempo é o mesmo que o tamaño da matriz de entrada. eu
t leva n comparacións e intercambios para ordenar unha lista de n elementos. Por exemplo, considere unha matriz de tamaño 5. O algoritmo levará cinco comparacións e intercambios para ordenar a matriz.
Complexidade media do caso O(n2):
Neste caso, a complexidade temporal sitúase entre o peor e o mellor dos casos.
Leva n2 comparacións e intercambios para ordenar unha lista de n elementos.
Así, a clasificación por inserción é un algoritmo de clasificación estable.
Por que a clasificación por inserción é estable?
A ordenación por inserción é estable porque conserva a orde dos elementos iguais na matriz de entrada.
Isto é importante para moitas aplicacións, como a recuperación de datos ou a análise financeira. Por exemplo, se temos dúas listas de números e queremos comparalos, debemos asegurarnos de que se conserva a orde dos elementos.
Se as listas non están ordenadas, non as compararemos con precisión.
Deixe unha resposta