algorithm - metodos - ordenamiento por seleccion java
¿Por qué la ordenación de inserción es mejor que la ordenación rápida para una pequeña lista de elementos? (5)
¿Qué tal el tipo de inserción binaria? Absolutamente puede buscar la posición para intercambiar utilizando la búsqueda binaria.
Isnt Insertion sort O (n ^ 2)> Quick sort O (nlogn) ... así que para una pequeña n, ¿no será la misma relación?
Definir "pequeño".
Al comparar los algoritmos de clasificación, descubrí que el cambio de la clasificación de ordenación rápida a la inserción, a pesar de lo que todos decían, en realidad perjudica el rendimiento (ordenación rápida recursiva en C) para matrices de más de 4 elementos. Y esas matrices se pueden clasificar con un algoritmo de clasificación óptimo que depende del tamaño.
Dicho esto, siempre tenga en cuenta que O(n...) solo es el número de comparaciones (en este caso específico), no la velocidad del algoritmo. La velocidad depende de la implementación, por ejemplo, si su pedido rápido funciona o no de forma recursiva y la rapidez con la que se tratan las llamadas de función.
Por último, pero no menos importante, la gran notación es solo un límite superior.
Si el algoritmo A requiere 10000 n log n comparaciones y el algoritmo B requiere 10 n ^ 2 , el primero es O(n log n) y el segundo es O(n ^ 2) . Sin embargo, la segunda será (probablemente) más rápida.
Es una cuestión de las constantes que están vinculadas al tiempo de ejecución que ignoramos en la notación big-oh (porque nos preocupa el orden de crecimiento). Para la ordenación por inserción, el tiempo de ejecución es O (n ^ 2), es decir, T (n) <= c (n ^ 2), mientras que para Quicksort es T (n) <= k (nlgn). Como c es bastante pequeño, para una pequeña n, el tiempo de ejecución de la ordenación por inserción es menor que el de Quicksort .....
Espero eso ayude...
La notación Big-O describe el comportamiento limitante cuando n es grande, también conocido como comportamiento asintótico. Esto es una aproximación. (Ver http://en.wikipedia.org/wiki/Big_O_notation )
La ordenación por inserción es más rápida para la n pequeña porque la ordenación rápida tiene una sobrecarga adicional por las llamadas de función recursiva. La ordenación por inserción también es más estable que la ordenación rápida y requiere menos memoria.
Esta pregunta describe algunos beneficios adicionales de la ordenación por inserción. ( ¿Hay alguna buena razón para usar el tipo de inserción? )
La notación O () se usa normalmente para caracterizar el rendimiento de grandes problemas, mientras que ignora deliberadamente los factores constantes y las compensaciones aditivas del rendimiento.
Esto es importante porque los factores constantes y la sobrecarga pueden variar mucho entre los procesadores y entre las implementaciones: el rendimiento que obtiene para un programa Basic de un solo subproceso en una máquina 6502 será muy diferente del mismo algoritmo implementado como un programa C que se ejecuta en un Intel i7 procesador de clase Tenga en cuenta que la optimización de la implementación también es un factor: la atención a los detalles a menudo puede darle un gran impulso de rendimiento, ¡incluso si todos los demás factores son los mismos!
Sin embargo, el factor constante y los gastos generales siguen siendo importantes. Si su aplicación asegura que N nunca se vuelve muy grande, el comportamiento asintótico de O (N ^ 2) en comparación con O (N log N) no entra en juego.
El orden de inserción es simple y, para las listas pequeñas, generalmente es más rápido que un quicksort o mergesort implementado de manera similar. Es por eso que una implementación de clasificación práctica generalmente se basará en algo así como la clasificación de inserción para el "caso base", en lugar de recurrir a elementos individuales.