Entre la ordenación rápida, la ordenación por inserción y la ordenación en montón, ¿cuál es la mejor para clasificar datos y por qué?

Ninguno. Elegiste tres algoritmos diferentes para ordenar los datos. Cada uno de ellos tiene sus ventajas y desventajas. Éstos son algunos de ellos:

Tipo de inserción:

• (+) más rápido para entradas pequeñas
• (-) cuadrático para la mayoría de las entradas grandes

Ordenación rápida:

• (+) rápido para la mayoría de las entradas
• (+) compatible con caché
• (-) la versión más simple tiene un peor caso cuadrático
• (-) la versión garantizada n-log n tiene un rendimiento mucho peor en la práctica
• (-) la versión aleatoria es solo O (n log n) con alta probabilidad, no ciertamente

HeapSort:

• (+) O garantizado (n log n)
• (+) funciona en su lugar, es decir, con O (1) memoria adicional
• (-) casi siempre se ejecuta en Theta (n log n), incluso si la entrada está ordenada
• (-) peor rendimiento práctico que QuickSort

Afortunadamente, en la práctica, nadie te obliga a elegir uno de estos tres. En la actualidad, muchas bibliotecas estándar implementan IntroSort como su algoritmo de clasificación predeterminado. Esto resulta ser una combinación de estos tres algoritmos:

• Comience con QuickSort.
• En cada rama que resulta ser demasiado profunda (por ejemplo, más profunda que 2 lg n), cambie a HeapSort.
• En cada rama que sea lo suficientemente corta, termine la clasificación ejecutando InsertSort.

De esta manera, IntroSort suele ser rápido en la práctica y, al mismo tiempo, le ofrece el rendimiento garantizado O (n log n) en el peor de los casos.

La ordenación por inserción es muy sencilla de implementar, no es recursiva, es estable y tiene una complejidad lineal de mejor tiempo ([matemática] \ Omega (n) [/ matemática]) (los valores ya están ordenados). Pero su complejidad promedio es [matemática] O (n ^ 2) [/ matemática] haciéndola inútil para cualquier cosa que no sean pequeños arreglos.

La ordenación del montón es [matemática] \ Theta (n \ lg n) [/ matemática] porque no le importa el estado inicial de la matriz. Su principal ventaja es que puede funcionar en el lugar e implementarse de forma iterativa, sin requisitos de memoria adicionales. En ciertas situaciones de tiempo crítico, su complejidad fija puede ser útil.

La ordenación rápida está en su lugar, pero requiere una pila porque es un algoritmo de divide y vencerás. Es nominalmente [matemática] O (n \ lg n) [/ matemática] pero hay entradas patológicas que pueden ser [matemática] O (n ^ 2) [/ matemática].

No existe un “mejor” algoritmo: cada uno tiene sus ventajas y desventajas. La complejidad puede ser una medición pobre, ya que a menudo los factores constantes dominan para entradas pequeñas. La memoria también es un factor, como lo es la recursividad. Además, todas estas complejidades se basan en un modelo de procesador único: agregar procesadores adicionales (hilos) puede cambiar las complejidades significativamente.

Si los valores de entrada tienen un rango fijo y el rango es pequeño en comparación con el número de elementos, los tipos de no comparación como radix pueden superar a todos estos. Y si tienes una computadora, el tipo ladrillo los avergüenza a todos.

Por otro lado, hay una serie de “peores” algoritmos: la clasificación del sueño y la clasificación de Bogo vienen a la mente. Pero esos son intencionalmente malos.

Como la complejidad temporal de un algoritmo cuantifica la cantidad de tiempo que tarda un algoritmo en ejecutarse en función de la longitud de la entrada y, de manera similar, la complejidad espacial de un algoritmo cuantifica la cantidad de espacio o memoria que un algoritmo necesita para ejecutarse como una función de la entrada lengyb, por lo tanto, en un logaritmo de clasificación, es la manera de poner los elementos de una lista en un cierto orden. La clasificación de inserción es la mejor información de clasificación porque, a pesar de ser el algoritmo de clasificación menos eficiente, se está compensando por su adaptabilidad.