Estructura de datos: técnicas de clasificación
La clasificación se refiere a organizar los datos en un formato particular. El algoritmo de clasificación especifica la forma de organizar los datos en un orden particular. Los órdenes más comunes están en orden numérico o lexicográfico.
La importancia de la clasificación radica en el hecho de que la búsqueda de datos se puede optimizar a un nivel muy alto, si los datos se almacenan de forma ordenada. La clasificación también se utiliza para representar datos en formatos más legibles. A continuación se muestran algunos de los ejemplos de clasificación en escenarios de la vida real:
Telephone Directory - La guía telefónica almacena los números de teléfono de las personas ordenados por sus nombres, de modo que los nombres se pueden buscar fácilmente.
Dictionary - El diccionario almacena palabras en orden alfabético para que la búsqueda de cualquier palabra sea fácil.
Clasificación in situ y clasificación no in situ
Los algoritmos de clasificación pueden requerir algo de espacio adicional para la comparación y el almacenamiento temporal de algunos elementos de datos. Estos algoritmos no requieren ningún espacio adicional y se dice que la clasificación se realiza en el lugar o, por ejemplo, dentro de la propia matriz. Se llamain-place sorting. La clasificación de burbujas es un ejemplo de clasificación in situ.
Sin embargo, en algunos algoritmos de clasificación, el programa requiere un espacio mayor o igual al de los elementos que se ordenan. La clasificación que usa igual o más espacio se llamanot-in-place sorting. Merge-sort es un ejemplo de ordenación fuera de lugar.
Clasificación estable y no estable
Si un algoritmo de ordenación, después de ordenar los contenidos, no cambia la secuencia de contenido similar en el que aparecen, se llama stable sorting.
Si un algoritmo de ordenación, después de ordenar los contenidos, cambia la secuencia de contenido similar en el que aparecen, se llama unstable sorting.
La estabilidad de un algoritmo importa cuando deseamos mantener la secuencia de elementos originales, como en una tupla, por ejemplo.
Algoritmo de clasificación adaptativo y no adaptativo
Se dice que un algoritmo de clasificación es adaptativo, si aprovecha los elementos ya 'ordenados' en la lista que se va a ordenar. Es decir, mientras ordena si la lista de origen tiene algún elemento ya ordenado, los algoritmos adaptativos lo tendrán en cuenta e intentarán no reordenarlos.
Un algoritmo no adaptativo es aquel que no tiene en cuenta los elementos que ya están ordenados. Intentan obligar a reordenar cada elemento para confirmar su clasificación.
Términos importantes
Algunos términos generalmente se acuñan al discutir las técnicas de clasificación, aquí hay una breve introducción a ellos:
Orden creciente
Se dice que una secuencia de valores está en increasing order, si el elemento sucesivo es mayor que el anterior. Por ejemplo, 1, 3, 4, 6, 8, 9 están en orden creciente, ya que cada elemento siguiente es mayor que el elemento anterior.
Orden decreciente
Se dice que una secuencia de valores está en decreasing order, si el elemento sucesivo es menor que el actual. Por ejemplo, 9, 8, 6, 4, 3, 1 están en orden decreciente, ya que cada elemento siguiente es menor que el elemento anterior.
Orden no creciente
Se dice que una secuencia de valores está en non-increasing order, si el elemento sucesivo es menor o igual que su elemento anterior en la secuencia. Este orden ocurre cuando la secuencia contiene valores duplicados. Por ejemplo, 9, 8, 6, 3, 3, 1 están en orden no creciente, ya que cada elemento siguiente es menor o igual que (en el caso de 3) pero no mayor que cualquier elemento anterior.
Orden no decreciente
Se dice que una secuencia de valores está en non-decreasing order, si el elemento sucesivo es mayor o igual que su elemento anterior en la secuencia. Este orden ocurre cuando la secuencia contiene valores duplicados. Por ejemplo, 1, 3, 3, 6, 8, 9 están en orden no decreciente, ya que cada elemento siguiente es mayor o igual (en el caso de 3) pero no menor que el anterior.