Estabilidad en los algoritmos de clasificación: un tratamiento de igualdad

Los algoritmos están en el corazón de la informática. Los algoritmos utilizados para clasificar son algunos de los más fundamentales, útiles y, en consecuencia, ubicuos.

Algoritmo: un conjunto finito de pasos inequívocos para resolver un problema específico.

Constantemente y a menudo inconscientemente clasificamos y confiamos en el orden de los objetos agrupados. Por ejemplo, clasificamos las tareas en una lista según la prioridad. Apilamos libros en estantes por su altura. Ordenamos filas en una hoja de cálculo o base de datos, o nos basamos en el orden alfabético de las palabras en un diccionario. A veces, incluso percibimos cierto tipo de belleza en arreglos ordenados.

Como programadores, saber cómo clasificamos es importante porque afecta el aspecto que podría tener una disposición ordenada. ¡No todas las clases ordenan los objetos de la misma manera! Debido a esto, los resultados de las operaciones de clasificación difieren según los algoritmos utilizados. Si esto no se reconoce, podríamos sorprendernos a nosotros mismos oa las personas que usan nuestro software.

La estabilidad de los algoritmos de clasificación es una de las propiedades distintivas entre ellos. Se trata de cómo el algoritmo trata elementos comparables con claves de clasificación iguales.

Clave de clasificación: una clave que se utiliza para determinar el orden de los elementos de una colección, por ejemplo, edad, altura, posición en el alfabeto, etc.

Un algoritmo de clasificación estable mantiene el orden relativo de los elementos con claves de clasificación iguales. Un algoritmo de clasificación inestable no lo hace. En otras palabras, cuando una colección se ordena con un algoritmo de ordenación estable, los elementos con las mismas claves de ordenación conservan su orden después de ordenar la colección.

Un ejemplo, código y una demostración

La imagen de arriba ilustra el efecto de una especie estable. A la izquierda, los datos se ordenaron alfabéticamente por Nombre. Después de ordenar los datos por grado, puede ver que el orden alfabético de los nombres se mantuvo para cada fila con el mismo grado.

Con una clasificación inestable, no hay garantía de que se mantenga el orden alfabético como se muestra en la imagen de arriba.

No siempre necesitas un tipo estable

Saber si el tipo que usa es estable o no es particularmente importante. Especialmente en situaciones en las que sus datos ya tienen algún orden que le gustaría mantener cuando los ordena por otra clave de clasificación. Por ejemplo, tiene filas en una hoja de cálculo que contienen datos de los estudiantes que, de forma predeterminada, están ordenados por nombre. También le gustaría ordenarlo por grados manteniendo el orden de clasificación de los nombres.

Por otro lado, la estabilidad de la ordenación no importa cuando las claves de ordenación de los objetos de una colección son los propios objetos (una matriz de enteros o cadenas, por ejemplo) porque no podemos diferenciar entre los objetos duplicados. llaves.

// JavaScript
// $5 bucks if you can correctly tell which 4 in the sorted// array was the first 4 when the array was unsorted.
var numbers = [5, 4, 3, 4, 9];numbers.sort(); // [3, 4, 4, 5, 9]
// A one second trip around the world, courtesy of the Flash, to// whomever correctly tells me which 'harry' in the sorted array was// the second 'harry' in the unsorted array.
var names = ['harry', 'barry', 'harry', 'cisco'];names.sort(); // ['barry', 'cisco', 'harry', 'harry']

Los géneros están en todas partes: conozca sus géneros

Es bastante fácil averiguar si el orden predeterminado en su lenguaje de programación o biblioteca es estable. La documentación debe incluir esta información. Por ejemplo, la ordenación predeterminada es estable en Python, inestable en Ruby e indefinida. en JavaScript (depende de la implementación del navegador).

A continuación, se muestran algunos algoritmos de clasificación comunes y su estabilidad:

  • Orden de inserción: estable
  • Orden de selección: inestable
  • Clasificación de burbujas: estable
  • Combinar clasificación: estable
  • Tipo de caparazón: inestable
  • Timsort - Estable

Consulte Wikipedia para obtener una lista más exhaustiva.

¿Es hora de la demostración? ‍?

Esta demostración muestra el efecto de usar un algoritmo de clasificación estable (ordenación por inserción) e inestable (ordenación por selección) para ordenar una pequeña tabla de datos. Me divertí un poco y prácticamente hice ingeniería inversa en React mientras construía esto. Eche un vistazo a la fuente.

¿Que sigue?

Si tiene sed de obtener más conocimientos sobre la estabilidad de otros algoritmos de clasificación, Wikipedia tiene una buena tabla de comparación e información adicional sobre algoritmos de clasificación bien conocidos.

Hasta la próxima, paz.

¿Aprendiste algo nuevo o disfrutaste leyendo este artículo? ¿Aplaudir?, Compártelo para que otros también puedan leer, y sigue para más Siéntete libre de dejar un comentario también.