Algoritmo de ordenamiento

Algoritmo 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, dadasentradas 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 unalista 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. 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 sonindistinguibles (porque cada elemento se ordena por la clave completa) la estabilidad no interesa. Los algoritmos 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 lassiguientes características:
• Complejidad computacional (peor caso, caso promedio y mejor caso) 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²). Losalgoritmos que aprovechan la estructura de las claves de ordenamiento (p. ej. bucket sort) pueden ordenar 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).




Antes de comenzar a vercada algoritmo vamos a ponernos de acuerdo en algunos conceptos, para que no haya confusiones:
• Clave: La parte de un registro por la cual se ordena la lista. Por ejemplo, una lista de registros con campos nombre, direccion y telefono se puede ordenar alfabéticamente de acuerdo a la clave nombre. En este caso los campos direccion y telefono no se toman en cuenta en el ordenamiento.
• Criterio deordenamiento (o de comparación): EL criterio que utilizamos para asignar valores a los registros con base en una o más claves. De esta manera decidimos si un registro es mayor o menor que otro. En el pseudocódigo presentado más adelante simplemente se utilizarán los símbolos < y >, para mayor simplicidad.
• Registro: Un grupo de datos que forman la lista. Pueden ser datos atómicos (enteros,caracteres, reales, etc.) o grupos de ellos, que en C equivalen a las estructuras.
Cuando se estudian algoritmos de todo tipo, no sólo de ordenamiento, es bueno tener una forma de evaluarlos antes de pasarlos a código, que se base en aspectos independientes de la plataforma o el lenguaje. De esta manera podremos decidir cuál se adapta mejor a los requerimientos de nuestro programa. Así que veamosestos aspectos:
• Estabilidad: Cómo se comporta con registros que tienen claves iguales. Algunos algoritmos mantienen el orden relativo entre éstos y otros no. Veamos un ejemplo. Si tenemos la siguiente lista de datos (nombre, edad): "Pedro 19, Juan 23, Felipe 15, Marcela 20, Juan 18, Marcela 17", y la ordenamos alfabéticamente por el nombre con un algoritmo estable quedaría así: "Felipe 15,...