ALGORITMOS DE ORDENAMIENTO

Los algoritmos de ordenamiento se pueden clasificar de las siguientes maneras:



La más común es clasificar según el lugar donde se realice la ordenación

• Algoritmos de ordenamiento interno: en la memoria del ordenador.
• Algoritmos de ordenamiento externo: en un lugar externo como un disco duro.

Por el tiempo que tardan en realizar la ordenación, dadas entradas ya ordenadas o inversamente ordenadas:

• Algoritmos de ordenación natural: Tarda lo mínimo posible cuando la entrada está ordenada.
• Algoritmos de ordenación no natural: Tarda lo mínimo posible cuando la entrada está inversamente ordenada.

Por estabilidad: un ordenamiento estable mantiene el orden relativo que tenían originalmente los elementos con claves iguales. Por ejemplo, si una lista ordenada por fecha se reordena en orden alfabético con un algoritmo estable, todos los elementos cuya clave alfabética sea la misma quedarán en orden de fecha.




Los algoritmos de ordenamiento estable mantienen un relativo pre-orden total. Esto significa que un algoritmo es estable solo cuando hay dos registros R y S con la misma clave y con R apareciendo antes que S en la lista original.

(4, 1)  (3, 7)  (3, 1)  (5, 6)

En este caso, dos resultados diferentes son posibles, uno de los cuales mantiene un orden relativo de registros con claves iguales, y una en la que no:

(3, 7) (3, 1) (4, 1) (5, 6) (orden mantenido)

(3, 1) (3, 7) (4, 1) (5, 6) (orden cambiado)

Los algoritmos de ordenamiento inestable pueden cambiar el orden relativo de registros con claves iguales, pero los algoritmos estables nunca lo hacen.

Los algoritmos inestables pueden ser implementados especialmente para ser estables. Una forma de hacerlo es extender artificialmente el cotejamiento de claves, para que las comparaciones entre dos objetos con claves iguales sean decididas usando el orden de las entradas original. 

 

Ordenar según una clave primaria, secundaria, terciara, etc., puede ser realizado utilizando cualquier método de ordenamiento, tomando todas las claves en consideración (en otras palabras, usando una sola clave compuesta).

 

Si un método de ordenamiento es estable, es posible ordenar múltiples ítems, cada vez con una clave distinta. En este caso, las claves necesitan estar aplicadas en orden de aumentar la prioridad.

 

Ejemplo: ordenar pares de números, usando ambos valores

(4, 1)  (3, 7)  (3, 1)  (4, 6) (original)

(4, 1)  (3, 1)  (4, 6)  (3, 7) (después de ser ordenado por el segundo valor)
(3, 1)  (3, 7)  (4, 1)  (4, 6) (después de ser ordenado por el primer valor) 

Por otro lado:

(3, 7)  (3, 1)  (4, 1)  (4, 6) (después de ser ordenado por el primer valor)
  (3, 1)  (4, 1)  (4, 6)  (3, 7) (después de ser ordenando por el segundo valor,
                                 el orden por el primer valor es perturbado)