Cuándo usar cada algoritmo de clasificación | conjunto 2

Ordenar es el proceso de ordenar un conjunto de datos en un orden específico, que puede ser numérico (ascendente, descendente) o lexicográfico (alfabético).

¿Por qué es necesaria la clasificación?

La clasificación es muy esencial cuando existe la necesidad de optimizar en gran medida el algoritmo de búsqueda . Por ejemplo, supongamos dos casos para buscar un determinado elemento.
Caso 1: Búsqueda de un elemento de un conjunto aleatorio de elementos. (Sin ordenar)
Caso 2: Búsqueda de un elemento de un conjunto ordenado de elementos. (Ordenados)
Es obvio que sería más fácil y rápido buscar un elemento en el caso 2, ya que los elementos están previamente ordenados, por lo que la búsqueda llevaría menos tiempo.

¿Cuándo usar cada algoritmo de clasificación?

Para la clasificación de datos, existen diferentes algoritmos disponibles que se pueden usar para clasificar los datos, pero la pregunta principal que surge es, ¿cómo seleccionar un algoritmo adecuado para lograr la mayor eficiencia posible?
Antes de seleccionar un algoritmo de clasificación, hay algunos factores a considerar:

• Tamaño de los datos: el número total de elementos o datos presentes puede ser grande o pequeño.
• Estado de los datos: si los datos son completamente aleatorios, parcialmente ordenados o casi ordenados.
• Complejidad de tiempo y espacio : la cantidad de tiempo y espacio en la que necesitamos invertir.

Echemos un vistazo a los diversos algoritmos de clasificación:

Heap Sort : crea una estructura de datos de montón binario a partir de los elementos disponibles y luego usa el montón para ordenar. Es un algoritmo de clasificación basado en comparación (en el lugar) sin tiempo de ejecución cuadrático en el peor de los casos. Heapsort se puede utilizar según las siguientes restricciones:

• Lo mejor de este algoritmo es que no requiere ninguna memoria adicional, por lo que si existe un requisito para un algoritmo sin requisitos de espacio adicional, entonces se puede optar por la ordenación en montón.
• Muestra un rendimiento constante. Por lo tanto, funciona bien en los mejores, promedios y peores casos. Por su desempeño garantizado, se utiliza en sistemas con tiempo de respuesta crítico.
• El heap sport es especialmente adecuado para clasificar una gran lista de elementos.

Complejidad del tiempo:

• Mejor caso: O(N*log N)
• Caso promedio: O(N*log N)
• Peor caso: O(N*log N)

Complejidad espacial: O(1)

Shell Sort : es una clasificación de comparación en el lugar. Este algoritmo evita grandes cambios, como en el caso de la ordenación por inserción, si el valor más pequeño está en el extremo derecho y debe moverse hacia el extremo izquierdo. La ordenación por concha es más eficiente en comparación con la ordenación por inserción o la ordenación por burbuja, y se utiliza cuando:

• Los elementos de valor más pequeño están hacia el final de la array/lista.
• Cuando hay una array/lista de gran tamaño y los elementos cercanos están muy separados, mediante este algoritmo podemos reducir la distancia entre estos elementos, por lo que se requieren menos intercambios en este caso.
• Cuando una recursión excede un límite, entonces se puede usar este algoritmo.

Complejidad del tiempo:

• Mejor caso: O(N*log N)
• Caso Promedio: Depende de la secuencia de espacios
• Peor caso: O(N*log ² N)

Complejidad espacial: O(1)

Radix Sort : Es un algoritmo de clasificación no comparativo. Evita la comparación al crear y distribuir elementos en cubos de acuerdo con la raíz. Tiene una complejidad de tiempo lineal que es mejor que O (N * log N) de algoritmos de clasificación comparativa. La clasificación Radix se puede utilizar según las siguientes restricciones:

• Cuando la repetición de elementos no es mucha en las listas dadas, pero la longitud de los elementos es del mismo rango, entonces es beneficioso usar la ordenación radix.
• Radix sort se usa ampliamente en datos que se pueden ordenar lexicográficamente.
• También se aplica para ordenar strings de forma estable.

Complejidad del tiempo:

• Mejor Caso: O(N*K)
• Caso Promedio: O(N*K)
• Peor caso: O(N*K)

Complejidad espacial: O(N + K)

Clasificación de cubeta : la clasificación de cubeta funciona distribuyendo los elementos de una array en una serie de cubetas. Luego, cada cubo se ordena individualmente y se agrega a una array. Es un algoritmo bastante estable ya que una vez que los elementos se distribuyen en cubos, cada cubo se puede procesar independientemente de los demás. El tipo de cubo se puede utilizar según las siguientes restricciones:

• Se utiliza para acelerar el proceso de clasificación porque el proceso de colocar elementos en cubos y luego clasificarlos en cantidades más pequeñas es mucho más rápido que cualquier otro algoritmo de clasificación lineal, como la clasificación de burbujas.
• Es muy útil cuando la entrada se distribuye uniformemente en un rango.
• Otra ventaja de la clasificación por cubos es que se puede utilizar como un algoritmo de clasificación externo.

Complejidad del tiempo:

Mejor caso: O(N + K)
Caso promedio: O(N)
Peor caso: O(N ² )

Complejidad espacial: O(N*K)

Clasificación por conteo : este algoritmo clasifica los elementos de una array contando el número de ocurrencias de cada elemento único en la array. A menudo se usa como una subrutina en otro algoritmo de clasificación, como la clasificación radix, que puede manejar claves más grandes de manera más eficiente. No es una especie de comparación. La ordenación por conteo se puede utilizar según las siguientes restricciones:

• Es útil cuando la diferencia entre diferentes teclas (números pequeños) no es tan grande.
• Cuando la lista/array contiene un rango limitado de números y se repite mucho, en ese caso, la ordenación por conteo será útil.
• Es un algoritmo de clasificación estable.

Complejidad del tiempo:

• Mejor caso: O (N + K)
• Caso Promedio: O(N + K)
• Peor caso: O(N + K)

Complejidad espacial: O(N + K)