Metodos de ordenamiento

Métodos de ordenamiento
En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por una relación de orden, esdecir, el resultado de salida ha de ser una permutación —o reordenamiento— de la entrada que satisfaga la relación de orden dada. Las relaciones de orden más usadas son el orden numérico y el ordenlexicográfico. Ordenamientos eficientes son importantes para optimizar el uso de otros algoritmos (como los de búsqueda y fusión) que requieren listas ordenadas para una ejecución rápida. También es útilpara poner datos en forma canónica y para generar resultados legibles por humanos.
Los algoritmos de ordenamiento se pueden clasificar de las siguientes maneras:
• La más común es clasificar según ellugar donde se realice la ordenación
o Algoritmos de ordenamiento interno: en la memoria del ordenador.
o Algoritmos de ordenamiento externo: en un lugar externo como un disco duro.
• Por el tiempoque tardan en realizar la ordenación, dadas entradas ya ordenadas o inversamente ordenadas:
o Algoritmos de ordenación natural: Tarda lo mínimo posible cuando la entrada está ordenada.
o Algoritmosde 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 loselementos 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 enorden de fecha. Otro caso sería cuando no interesan las mayúsculas y minúsculas, pero se quiere que si una clave aBC estaba antes que AbC, en el resultado ambas claves aparezcan juntas y en el ordenoriginal: aBC, AbC. Cuando los elementos son indistinguibles (porque cada elemento se ordena por la clave completa) la estabilidad no interesa. Los algoritmos de ordenamiento que no son estables se...