Diferencias entre Un Algoritmo de Ordenado Estable e Inestable

Diferencias entre Un Algoritmo de Ordenado Estable e Inestable 

Artículo - Entrevista a Javin Paul - Developer Java Code Geeks 

Recientemente en una de mis entrevistas, después de algunas de las preguntas que me hicieron acerca de los algoritmos de ordenado. Preguntas tales como cómo escribir algoritmos como QuickSort u otros diferentes entre QuickSort y MergeSort. Además, también en esa entrevista, una persona me preguntó la diferencia entre la estabilidad e inestabilidad de los algoritmos de ordenado. Estas preguntas fueron nuevas para mi lectura y le dije a él. Disculpa, nunca oí hablar de eso. La historia termina cuando el entrevistador hizo otras preguntas, como mucha de las de ustedes suelen hacerme. Haciendo una lectura de esto, hallé menos respuestas que preguntas y ultimamente, más cuando él me preguntó qué significaba la estabilidad e inestabilidad de un algoritmo de ordenado. En consecuencia, he decidido responder a esta pregunta clave a través de este artículo. 

Un algoritmo de ordenado se dice que es estable si este mantiene un orden relativo de números de registros en caso de ser iguales. O sea, si tu necesitas ordenar la serie 1 2 3..., luego si no cambias el orden de estos primeros dos números el algoritmo será estable, pero si tu intercambias a ellos luego pasarán a ser inestables, sobre todo a pesar del resultado u ordenamiento del mismo ordenado. 

Estas diferencias son más que obvias cuando tu ordenas objetos. O sea, el ordenamiento de pares clave valor. En el caso de un algoritmo estable, el orden original del par clave valor es retenido como se muestra en el siguiente ejemplo. 

Actualmente, el entrevistador me preguntó seguido a ello que no me olvide de mencionar los conceptos acerca de QuickSort versus MergeSort. Una de las principales diferencias entre QuickSort y MergeSort es que formalmente QuickSort es inestable aunque MergSort es un algoritmo de ordenamiento estable. 

Algoritmos Estables vs Inestables

Supongamos que tienes un ordenado basado en par claves valor en un orden incremental clave como: 

INPUT: (4, 5), (3, 2) (4, 3) (5, 4) (6, 4) 

Ahora, existen dos posibilidades para solucionar estos pares donde la clave es la misma, es decir (4, 5) y (4, 3) como se muestra a continuación: 

OUTPUT1: (3, 2),  (4, 5),  (4, 3),  (5, 4),  (6, 4)

OUTPUT2: (3, 2),  (4, 3),  (4, 5),  (5, 4),  (6, 4)

El ordenamiento del algoritmo que se produce en la primera salida debería saber cómo estabilizar al algoritmo de ordenamiento dado que el orden original de las claves iguales serán mantenidas, esto lo podrás ver con (4, 5) seguido anteriormente por (4, 3). 

En otra pasada, el algoritmo que produce la segunda salida será como un algoritmo de ordenamiento inestable dado que el orden de los objetos con la misma clave no es mantenida en el orden de forma ordenada. Podrás observar que en la segunda salida, el par (4, 3) es seguido anteriormente por (4, 5). 

Ahora, la gran pregunta es ¿cuáles son ejemplos de algoritmos de ordenamientos estables e inestables? La respuesta es entonces dividiéndolos a todos en algoritmos de ordenamiento bien conocidos dentro de ordenados y desordenados. Algunos ejemplos de algoritmos estables son Merge, Sort, Insertion Sort "Ordenamiento de Inserción", Bubble Sort "Ordenamiento Burbúja" y Tree Binary "Árbol Binario". Mientras que QuickSort, Heap Sort "Ordenamiento de Apilado" y Selection Sort "Ordenamiento por Selección", son algoritmos de ordenamiento inestables. 

Si tu recuerdas el método de ordenamiento de Collections.sort() de la plataforma Java Collection, este utiliza una interacción del método Merge Sort que es un algoritmo estable. Esto va más allá de las comparaciones de NLog(N) para el caso de entradas de matrices o vectores que cuentan con un proceso previo de ordenamiento parcializado. 

Si verdaderamente estás interesado acerca de estos temas, te sugiero que leas un buen libro sobre estructuras de datos y de algoritmos. Existe un autor que ha escrito un libro llamado "Introduction to Algorithms" por Thomas H. Cormen (disponible en inglés). Este libro está disponible en Amazón. Haz clic aquí si estás interesado Introduction to Algorithms.

En la siguiente figura de ejemplo se cuenta con mil palabras, en esta imagen podremos detallar cómo operan los procesos de estabilidad e inestabilidad del ordenado. 

Todo esto trata acerca de las diferencias entre algoritmos de ordenamiento estables e inestables. Recuerda, que si el ordenamiento original de claves o números iguales es mantenido en el ordenamiento saliente, luego el algortimo sabrá cómo ordenarlo. Algunos ejemplos comunes de algoritmos de ordeamiento estables son Merge Sort, Insertion Sort y el clásico Bubble Sort. 

Artículo Javin Paul - Blog de Java Code Geeks
https://www.javacodegeeks.com/2017/06/difference-stable-unstable-sorting-algorithm.html.
Traducido por Ariel Alejandro Wagner.
Muchas gracias por leer. ¡Hasta la próxima entrega!