Algoritmo de clasificación más rápido en C++

1. Algoritmo de clasificación más rápido en C++
2. Hoja de referencia de la complejidad del algoritmo

Este artículo explicará qué algoritmo de clasificación funcionará mejor en qué condiciones. Las condiciones incluyen el tipo de estructura de datos, el tamaño de los datos que se ordenan, la disposición de los datos y el rango de los elementos de datos.

Primero expliquemos el algoritmo de clasificación; luego, explicaremos el desempeño de varios algoritmos en las diferentes estructuras de datos.

Algoritmo de clasificación más rápido en C++

El algoritmo de clasificación es un método para organizar el elemento almacenado en cualquier estructura de datos.

La idoneidad de cualquier algoritmo de clasificación depende del tamaño de los datos de entrada, el tipo de estructura de datos, la disposición de los datos, las complejidades de tiempo y espacio y el rango de los datos.

Algunos algoritmos de clasificación funcionan mejor en estructuras de datos de matriz, mientras que otros funcionan mejor en montones. Además, algunos algoritmos son rápidos si la clave integral más significativa de los registros es mucho más pequeña que el número de registros (por ejemplo, clasificación por conteo).

Entonces, ¿cuál es el algoritmo más rápido? Aunque la respuesta parece simple, vea la tabla de complejidad y elija una con la complejidad de tiempo más baja (es decir, crecimiento asintótico).

Sin embargo, en realidad, no podemos decir directamente que el algoritmo A funcionará mejor que el algoritmo B o viceversa en datos dados sin ver las propiedades estructurales de los datos subyacentes.

Por lo tanto, intentaremos responder a la respuesta discutiendo los algoritmos de clasificación con su idoneidad particular en diferentes escenarios sobre una estructura de datos subyacente determinada.

Estructura de datos - Lista enlazada

La lista de enlaces es una estructura de datos lineal que almacena datos en el nodo. Un nodo es un bloque de construcción fundamental de la lista de enlaces que contiene datos y un puntero al siguiente nodo.

El mejor algoritmo de ordenación para ordenar una lista de enlaces es la ordenación por combinación. La ordenación por combinación funciona mejor en listas vinculadas que en matrices, ya que no se requiere una matriz auxiliar para almacenar el resultado de la operación de combinación.

A diferencia de las matrices, no es necesario que los nodos de la lista enlazada sean contiguos en la memoria. En cambio, los nodos pueden estar dispersos en diferentes ubicaciones de memoria.

Además, en contraste con una matriz, podemos poner un valor en el centro de una lista enlazada en el espacio adicional O(1) y el tiempo O(1).

Como resultado, no se requiere espacio de crecimiento asintótico adicional para implementar la operación de combinación del ordenamiento de combinación mientras se ordena la lista de enlaces. Por lo tanto, la ordenación por fusión ordenará la lista de enlaces en (nlog n).

Puede encontrar la implementación del ordenamiento por fusión aquí.

Estructura de datos: matriz

La matriz es la estructura de datos lineal que almacena datos en una ubicación de memoria consecutiva. El tipo de datos debe ser el mismo en una matriz.

Aquí hay una lista de los diversos algoritmos de clasificación y su idoneidad.

• La ordenación por inserción se puede elegir cuando la matriz está casi ordenada porque rara vez mueve elementos al agregar un nuevo elemento en la región ordenada de la matriz.

  La complejidad temporal de una ordenación por inserción en una matriz ordenada es O(n), pero la complejidad temporal de una ordenación rápida en la misma matriz es O(n^2). Puedes encontrar más información aquí].

• Dado que Quick Sort realiza la clasificación en el lugar, es adecuado para matrices. Además, el algoritmo de clasificación rápida no requiere espacio adicional durante el procedimiento de clasificación.

• En el caso de merge sort, el espacio adicional debe adquirirse y liberarse. Por lo tanto, se incrementará el tiempo de ejecución del algoritmo de clasificación por fusión.

  En promedio, la combinación y la ordenación rápida tienen una complejidad de tiempo O(nlogn), pero la clasificación por fusión ocupa un espacio O(n) adicional. Aquí, la n es el tamaño de la matriz que se va a ordenar. Puede encontrar más información al respecto aquí.

• Cuando queremos ordenar los datos (como números enteros, palabras y cadenas con caracteres de tamaño fijo) almacenados en una matriz en orden “lexicográfico”, usamos la ordenación radix. Radix sort funciona cuando se usan máquinas paralelas.

• La ordenación por conteo se usa cuando la clave integral más grande de los registros es mucho más pequeña que el número de registros.

• La ordenación de cubos es más eficiente cuando los datos almacenados en una matriz se distribuyen de manera justa dentro de un rango.

Estructura de datos - Árbol

El árbol es una estructura de datos no lineal que almacena datos en los nodos. El nodo superior se denomina nodo raíz. El nodo raíz se adjunta además a los nodos secundarios.

Hay muchos tipos de árboles, pero aquí solo hablaremos del árbol de búsqueda binaria (BST).

La clasificación de árboles se considera el mejor algoritmo de clasificación para BST. Además, el recorrido en orden de BST nos da los elementos ordenados. De manera similar, Heap sort es mejor para ordenar los elementos almacenados en un montón.

Recuerde, también podemos analizar todos los algoritmos de clasificación en otros tipos de estructuras de datos como tablas hash, árboles rojo-negro y mucho más.

La siguiente sección presenta una hoja de trucos que describe las complejidades y la estabilidad de varios algoritmos de clasificación.

Hoja de referencia de la complejidad del algoritmo

Antes de mirar la tabla, analicemos las terminologías comunes asociadas con los algoritmos de clasificación.

Clasificación estable

Un algoritmo es estable si, en caso de empate entre las claves, conserva el orden original de las claves. Por ejemplo, supongamos que la secuencia S tiene los siguientes pares:

S = <(1,"Alex"), (3,"Bill"),(2,"Ananth"), (1, "Jack")>

Ahora, supongamos que queremos ordenar la secuencia anterior por claves integrales. Luego, un algoritmo de clasificación estable ordenará la secuencia anterior como:

Stably Sorted S = <(1,"Alex"),(1, "Jack"),(2,"Ananth"),(3,"Bill")>

Mira, el tipo estable conservó el orden original de los pares (1, "Alex") y (1, "Jack"). Sin embargo, una ordenación inestable no garantiza eso.

Clasificación en el lugar

Una clasificación está en su lugar si requiere una cantidad constante de memoria auxiliar. Significa que los requisitos de memoria adicional no aumentan con el aumento del tamaño del problema.

Por ejemplo, todos los tipos en la siguiente hoja de trucos con complejidad de espacio O(1) están en su lugar.

Después de tener suficientes antecedentes sobre las terminologías básicas de clasificación, veamos la tabla de complejidad para los algoritmos de clasificación. Esta tabla puede ayudar a nuestra decisión de elegir el algoritmo de clasificación más adecuado en un contexto de problema particular.