Mejor respuesta
En primer lugar, uno debería preguntarse por qué usar un algoritmo de ordenación cuadrática cuando existen alternativas asintóticamente más rápidas, como mergesort o clasificación rápida. Para arreglos pequeños (menos de 20-30 elementos), tanto el ordenamiento por inserción como el ordenamiento por selección son típicamente más rápidos que las alternativas O (n * logn). De hecho, muchos algoritmos de ordenación basados en el paradigma de dividir y conquistar cambian al ordenamiento por inserción o al ordenamiento por selección cuando la matriz es lo suficientemente pequeña.
Entre el ordenamiento por inserción y el ordenamiento por selección, ¿cuándo usar cuál?
Por lo general, la ordenación por inserción realizará menos comparaciones que la ordenación por selección, dependiendo del grado de «ordenación» de la matriz. Mientras que la ordenación por selección debe escanear las partes restantes de la matriz al colocar un elemento, la ordenación por inserción solo escanea tantos elementos como sea necesario. Eso significa que cuando la matriz ya está ordenada o casi ordenada, la ordenación por inserción se realiza en O (n) tiempo.
Una ventaja de la ordenación por selección sobre la ordenación por inserción es que el número de escrituras (intercambios) está en O (n), mientras que en ordenación por inserción está en O (n ^ 2). Esto puede ser importante si está ordenando en memoria Flash, por ejemplo, porque las escrituras reducen la vida útil de la memoria Flash.
Respuesta
En una ordenación de selección, para cada elemento que debe Para agregarlo a la sección ordenada, debe escanear la toda parte sin clasificar de la lista para encontrar el elemento mínimo restante. En una ordenación por inserción, debe buscar la sección ordenada para averiguar dónde va el siguiente elemento, pero la búsqueda finaliza una vez que haya encontrado el punto de inserción (aproximadamente la mitad por la sección ordenada en promedio).
Por lo tanto, la ordenación por selección requiere N / 2 comparaciones en promedio para que cada elemento se agregue a la sección ordenada y la ordenación por inserción requiere N / 4 comparaciones en promedio. Sin embargo, la ordenación por inserción tiene una penalización de tiempo adicional al ordenar una matriz. Cada una de las N / 4 comparaciones (en promedio) requiere que el elemento se mueva hacia arriba, por lo que también hay N / 4 movimientos y comparaciones. La clasificación por selección solo requiere un único intercambio.
En general, la clasificación por inserción suele ganar la carrera. Esto es especialmente cierto si hay funciones rápidas de «movimiento de bloques» (para matrices).