¿Cuáles son los criterios para elegir un algoritmo de clasificación?

Question

Estaba leyendo un método de clasificación que incluye sortear con burbujas, ordenar por selección, ordenar por fusión, ordenar por montones, ordenar por cubo, etc. También contienen complejidad de tiempo que nos ayuda a saber qué ordenamiento es eficiente. Entonces tuve una pregunta básica. Si contenemos datos de cómo seremos elegidos. La complejidad del tiempo es uno de los parámetros que nos ayudan a decidir el método de clasificación. ¿Pero tenemos otro parámetro para elegir el método de clasificación?

Solo intento averiguar la clasificación para una mejor comprensión.

Teniendo alguna pregunta acerca de pila de clasificación:

1. Dónde qué utilizamos pila de clasificación?

2. ¿Cuál es la mayor ventaja de la ordenación de pila (excepto la complejidad de tiempo O (n log n))?

3. ¿Qué es la desventaja del tipo de montón?

4. ¿Qué es tiempo de compilación para heap? (Escuché O (n) pero no estoy seguro.)

5. ¿Algún escenario en el que tengamos que usar la ordenación de montón o la ordenación de montón es una mejor opción (excepto la cola de prioridad)?

6. Antes de aplicar la ordenación del montón en los datos, ¿cuál es el parámetro que buscaremos en los datos?

Answer 1

Las dos principales características teóricas de los algoritmos de clasificación son la complejidad del tiempo y la complejidad del espacio.

En general, time complexity nos permite saber cómo cambia el rendimiento del algoritmo a medida que aumenta el tamaño del conjunto de datos. Aspectos a tener en cuenta:

• ¿Cuántos datos espera ordenar? Esto lo ayudará a saber si necesita buscar un algoritmo con una complejidad de tiempo muy baja.
• ¿Cómo están ordenados sus datos ya? ¿Se ordenará parcialmente? Aleatoriamente ordenado? Esto puede afectar la complejidad del tiempo del algoritmo de clasificación. La mayoría de los algoritmos tendrán el peor y el mejor de los casos: desea asegurarse de que no esté utilizando un algoritmo en el conjunto de datos del peor de los casos.
• La complejidad del tiempo no es lo mismo que el tiempo de ejecución. Recuerde que la complejidad del tiempo solo describe cómo varía el rendimiento de un algoritmo a medida que aumenta el tamaño del conjunto de datos. Un algoritmo que siempre pasa por una sola vez sobre toda la entrada sería O (n) - su rendimiento se correlaciona linealmente con el tamaño de la entrada. Pero, un algoritmo que siempre hace dos pasadas sobre el conjunto de datos también es O (n) - la correlación sigue siendo lineal, incluso si la constante (y el tiempo real de ejecución) es diferente.

De forma similar, la complejidad de espacio describe la cantidad de espacio que necesita ejecutar un algoritmo. Por ejemplo, un tipo simple como insertion sort necesita una cantidad fija adicional de espacio para almacenar el valor del elemento que se está insertando actualmente. Esta es una complejidad de espacio auxiliar de O (1) - no cambia con el tamaño de la entrada. Sin embargo, merge sort crea matrices adicionales en la memoria mientras se ejecuta, con una complejidad de espacio auxiliar de O (n). Esto significa que la cantidad de espacio adicional que requiere se correlaciona linealmente con el tamaño de la entrada.

Por supuesto, el diseño de algoritmo es a menudo una compensación entre el tiempo y el espacio: los algoritmos con poca complejidad de espacio pueden requerir más tiempo y los algoritmos con baja complejidad de tiempo pueden requerir más espacio.

Para obtener más información, puede encontrar this tutorial útil.

---

Para responder a su pregunta actualizada, puede encontrar la página de Wikipedia sobre Heap Sort útil.

Answer 2

Si se refiere a los criterios para qué tipo de orden elegir, estos son algunos otros elementos a considerar.

La cantidad de datos que tiene: tiene diez, cien, mil o millones de elementos para ordenar.

Complejidad del algoritmo: cuanto más complejas, más pruebas deberán realizarse para asegurarse de que sean correctas. Para cantidades pequeñas, una ordenación de burbujas o una ordenación rápida es fácil de codificar y evaluar, en otros versos que pueden ser excesivos para la cantidad de datos que tiene que ordenar.

Cuánto tiempo le tomará ordenar: si tiene un conjunto grande, la clasificación rápida/de burbuja llevará mucho tiempo, pero si tiene mucho tiempo, eso puede no ser un problema. Sin embargo, el uso de un algoritmo más complejo reducirá el tiempo de clasificación, pero a costa de un mayor esfuerzo de codificación y prueba, que puede valer la pena si la clasificación va de largo (horas/días) a un período de tiempo más corto.

Los datos en sí: ¿Están los datos cerca de ser iguales para todo? Para algunos tipos, puede terminar con una lista lineal, por lo que si sabe algo acerca de la composición de los datos, puede ayudar a determinar qué algoritmo elegir para el esfuerzo.

La cantidad de recursos disponibles: ¿Tiene mucha memoria en la que almacena todos los elementos, o necesita almacenar elementos en el disco. Si no todo puede caber en la memoria, la ordenación por fusión puede ser mejor, mientras que otra puede ser mejor si trabajas con todo en la memoria.