Algoritmo De Ordenación

ALGORITMOS DE ORDENACIÓN
En las ciencias de la computación y matemáticas un algoritmo de ordenación es un algoritmo que ordena los elementos de una lista o el contenido de un vector, es decir, el resultado de este ordenamiento ha de ser una permutación o reordenamiento. Para lograr esta acción se debe utilizar algún método que realice esta acción automáticamente, no importando la cantidad dedatos a ordenar.

Las relaciones de orden más utilizadas son las de orden numérico y el orden lexicográfico.

Un ordenamiento eficiente es importante para optimizar el uso de otros algoritmos, como los de búsqueda o fusión, ya que estos requieren listas ordenadas para una ejecución rápida.

Desde los comienzos de la computación, el problema del ordenamiento ha sido investigado, tal vez debidoa la complejidad de resolverlo eficientemente a pesar de su planteamiento simple y familiar. Por ejemplo, el ordenamiento de burbuja analizado desde 1956.  (http://www.cs.duke.edu/~ola/papers/bubble.pdf)

Hasta la fecha se siguen inventando nuevos métodos ya que para algunos este sistema se puede mejorar.

Los algoritmos de ordenamiento son comunes en las clases introductorias a lacomputación, donde la abundancia de algoritmos para el problema proporciona una gentil introducción a la variedad de conceptos núcleo de los algoritmos, como notación de O mayúscula, algoritmos divide y vencerás, estructuras de datos, análisis de los casos peor, mejor, y promedio, y límites inferiores.



CLASIFICACIÓN

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ínimoposible 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 loselementos cuya clave alfabética sea la misma quedarán en orden 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 orden original: aBC, AbC. Cuando los elementos son indistinguibles (porque cada elemento se ordena por la clave completa) la estabilidad no interesa. Losalgoritmos de ordenamiento que no son estables se pueden implementar para que sí lo sean. Una manera de hacer esto es modificar artificialmente la clave de ordenamiento de modo que la posición original en la lista participe del ordenamiento en caso de coincidencia.
Los algoritmos se distinguen por las siguientes características:

▪ Complejidad computacional (peor caso, caso promedio y mejorcaso) en términos de n, el tamaño de la lista o arreglo. Para esto se usa el concepto de orden de una función y se usa la notación O(n). El mejor comportamiento para ordenar (si no se aprovecha la estructura de las claves) es O(n log n). Los algoritmos más simples son cuadráticos, es decir O(n²). Los algoritmos que aprovechan la estructura de las claves de ordenamiento (p. ej. bucket sort) puedenordenar en O(kn) donde k es el tamaño del espacio de claves. Como dicho tamaño es conocido a priori, se puede decir que estos algoritmos tienen un desempeño lineal, es decir O(n).
▪ Uso de memoria y otros recursos computacionales. También se usa la notación O(n).
ESTABILIDAD

Los algoritmos de ordenamiento estable mantienen un relativo preorden total. Esto significa que un algoritmo...