Algoritmos de ordenamiento

1. Introducción.

El ordenamiento es una labor común que realizamos continuamente. ¿Pero te has preguntado qué es ordenar? ¿No? Es que es algo tan corriente en nuestras vidas que no nos detenemos a pensar en ello. Ordenar es simplemente colocar información de una manera especial basándonos en un criterio de ordenamiento.

En la computación el ordenamiento de datos también cumple un rol muy importante, ya sea como un fin en sí o como parte de otros procedimientos más complejos. Se han desarrollado muchas técnicas en este ámbito, cada una con características específicas, y con ventajas y desventajas sobre las demás. Aquí voy a mostrarte algunas de las más comunes, tratando de hacerlo de una manera sencilla y comprensible.

2. Conceptos Preliminares.

Antes de comenzar a ver cada 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 de ordenamiento (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 veamos estos 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, Marcela 20, Marcela 17, Juan 23, Juan 18, Pedro 19". Un algoritmo no estable podría dejar a Juan 18 antes de Juan 23, o a Marcela 20 después de Marcela 17.
  • Tiempo de ejecución: La complejidad del algoritmo, que no tiene que ver con dificultad, sino con rendimiento. Es una función independiente de la implementación. Te la voy a explicar brevemente: tenemos que identificar una operación fundamental que realice nuestro algoritmo, que en este caso es comparar. Ahora contamos cuántas veces el algoritmo necesita comparar. Si en una lista de n términos realiza n comparaciones la complejidad es O(n). (En realidad es un poco más complicado que eso, pero lo vamos a hacer así: recuerda que dije que te iba a explicar brevemente). Algunos ejemplos de complejidades comunes son:
    • O(1) : Complejidad constante.
    • O(n2) : Complejidad cuadrática.
    • O(n log(n)) : Complejidad logarítmica.
    Ahora podemos decir que un algoritmo de complejidad O(n) es más rápido que uno de complejidad O(n2). Otro aspecto a considerar es la diferencia entre el peor y el mejor caso. Cada algoritmo se comporta de modo diferente de acuerdo a cómo se le entregue la información; por eso es conveniente estudiar su comportamiento en casos extremos, como cuando los datos están prácticamente ordenados o muy desordenados.
  • Requerimientos de memoria: El algoritmo puede necesitar memoria adicional para realizar su labor. En general es preferible que no sea así, pero es común en la programación tener que sacrificar memoria por rendimiento.

Hay bastantes otros aspectos que se pueden tener en cuenta, pero nosotros nos vamos a quedar con ésos.

Por último estableceremos algunas convenciones sobre el pseudocódigo:

  • Vamos a ordenar la lista en forma ascendiente, es decir, de menor a mayor. Obviamente es esencialmente lo mismo que hacerlo en forma inversa.
  • La forma de intercambiar los elementos depende de la estructura de datos: si es un arreglo (dinámico o estático) es necesario guardar una copia del primer elemento, asignarle el segundo al primero y el temporal al segundo. La variable temporal es necesaria, porque de lo contrario se perdería uno de los elementos. Si la estructura es una lista dinámica el procedimiento es parecido, pero se utilizan las direcciones de los elementos. En el pseudocódigo se utilizará el primer método.
  • La lista se manejará como un arreglo de C: si tiene TAM elementos, el primer elemento es lista[0] y el último es lista[TAM-1]. Esto será así para todo el pseudocódigo presentado en este artículo.

Bien, ahora que ya tenemos todo claro vamos a lo que nos interesa...

3. Algoritmos más comunes.

La siguiente es una tabla comparativa de algunos algoritmos de ordenamiento. Si quieres saber más sobre alguno en particular haz un click sobre su nombre. En cada página encontrarás una descripción, pseudocódigo y un análisis sobre su rendimiento, ventajas y desventajas.

(Quizás quieras bajar ahora la demostración para ir observándola a medida que vayas leyendo)

Tabla comparativa de algoritmos
Nombre Complejidad Estabilidad Memoria adicional
Ordenamiento Burbuja (Bubblesort) O(n2) Estable No
Ordenamiento por Selección O(n2) No Estable No
Ordenamiento por Inserción O(n2) Estable No
Ordenamiento Rápido (Quicksort) O(n * log2(n)) No Estable No

4. Eligiendo el más adecuado.

Ahora ya conoces una buena cantidad de algoritmos, pero... ¿cómo saber cuál es el que necesitas? ¿cuál es EL algoritmo?

Cada algoritmo se comporta de modo diferente de acuerdo a la cantidad y la forma en que se le presenten los datos, entre otras cosas. No existe EL algoritmo de ordenamiento. Sólo existe el mejor para cada caso particular. Debes conocer a fondo el problema que quieres resolver, y aplicar el más adecuado. Aunque hay algunas preguntas que te pueden ayudar a elegir:

  • ¿Qué grado de orden tendrá la información que vas a manejar? Si la información va a estar casi ordenada y no quieres complicarte, un algoritmo sencillo como el ordenamiento burbuja será suficiente. Si por el contrario los datos van a estar muy desordenados, un algoritmo poderoso como Quicksort puede ser el más indicado. Y si no puedes hacer una presunción sobre el grado de orden de la información, lo mejor será elegir un algoritmo que se comporte de manera similar en cualquiera de estos dos casos extremos.
  • ¿Qué cantidad de datos vas a manipular? Si la cantidad es pequeña, no es necesario utilizar un algoritmo complejo, y es preferible uno de fácil implementación. Una cantidad muy grande puede hacer prohibitivo utilizar un algoritmo que requiera de mucha memoria adicional.
  • ¿Qué tipo de datos quieres ordenar? Algunos algoritmos sólo funcionan con un tipo específico de datos (enteros, enteros positivos, etc.) y otros son generales, es decir, aplicables a cualquier tipo de dato.
  • ¿Qué tamaño tienen los registros de tu lista? Algunos algoritmos realizan múltiples intercambios (burbuja, inserción). Si los registros son de gran tamaño estos intercambios son más lentos.

5. Demostración y Código Fuente.

Puedes descargar dos programas de demostración con los algoritmos presentados en este artículo:


  Nombre Fichero Fecha Tamaño Contador Descarga
D OrdWin Ord_Win10.zip 2001-12-01 174791 bytes 8701

OrdWin: En este programa puedes ver una demostración gráfica de cada algoritmo. También puedes experimentar ordenando listas de la longitud que quieras, observando el tiempo que demoran, la cantidad de comparaciones y de intercambios que realizan. Fue creado utilizando el compilador LccWin32 de Jacob Navia, pero el fichero descargable es un proyecto para Dev-C++. Incluye el ejecutable, el código fuente y este artículo completo.


  Nombre Fichero Fecha Tamaño Contador Descarga
D Ordenar Ordenar.zip 2001-12-01 2781 bytes 7419

Ordenar: Este programa es más indicado si lo que quieres es mirar código. No hay funciones gráficas ni nada del API de Windows. Debería funcionar en cualquier otro compilador sin mayores cambios, pues está hecho en ANSI C. Fue probado con éxito en Turbo C++, DJGPP, LccWin32, y Dev-C++. Quedó bastante feo, pero es el precio que hay que pagar por la portabilidad ;-). Sólo incluye el código.

6. Algunas palabras para terminar.

No sabía si escribir este artículo o no. Probablemente no sea yo el indicado para hacerlo. Después de todo no soy ningún experto ni mucho menos, pero creo que puede ayudar a alguien que sepa menos que yo (no deben ser muchos :-)). Por eso pido tu colaboración para mejorar este documento y hacerlo algo útil. Si tienes sugerencias, comentarios o correcciones por favor házmelo saber.

7. Bibliografía.

Comentarios de los usuarios (12)

Victor Hugo Mena Garzon
2010-09-03 05:40:25

Hola Buenas noches,

El siguiente es para saber si hay algun algoritmo que realice la siguiente comparacion en una matriz.

1 2 3 4 5 6

1 o 8 5 8 9 7

2 4 o 5 6 4 1

3 1 9 o 8 8 7

4 3 8 3 o 8 5

5 4 7 5 2 o 3

6 4 5 5 7 6 o

1) por cada una de las iteraciones debe selecconar fila

y columna.

2) Ahora de recorrer la matriz en este caso Iteracion uno selecciona fila 1 columna 1 y empieza en la posicion [2][2],[2][3],... recorre hasta [2][5] luego, fila 2 columna 2 [3][3], [3][4]..recorre hasta[3][5]y asi sucesivamente. ahora en el recorrido verificar si la suma de sus componetes es mayor a el numero en que se encuentra.

ejemplo:

seleciona fila 1 columna 1 .. inicia a recorrer posicion [2][2].. como esta la dioganal de ceros no se hace nada.. continua [2][3], \"evalua sus componentes\" 3+2 es > 5 si es mayor lo cambia si no continua... hasta terminar la matriz..

lo debo hacer en C no se si tengan algo que me sirva, de todas formas mucha gracia por la atencion prestada...

Ariel Ponce
2010-12-08 19:25:03

Hola, al querer descargar los ejemplos me direcciona a una pagina de error. Hay algun link opcional?

Gracias. Muy bueno el curso

unpocolocos
2011-06-02 20:12:20

No funcionan los links de descarga de los ejemplos de algoritmos de ordenamiento. ¿Se podrían volver a subir?

PS: Felicidades por este gran curso y esta gran pagina

carlos
2011-07-06 19:11:08

Vuelvo a dejar un comentario diciendo lo mismo que mis compañeros, los links no funcionan, ¿alguna otra forma de descargar los programas?

Salvador Pozo
2011-07-07 09:49:14

Hola:

Ya está resuelto el problema con las descargas.

Gracias por vuestro interés.

Curro Amado
2011-12-29 13:34:56

enhorabuena por el articulo, me ha sido muy util.

un saludo

Diego
2012-03-15 03:19:13

He programado todos los algoritmos de ordenamiento.

El burbuja lo sabía por mi universidad, pero nunca me gustó porque se notaba que era lento.

El de selección yo mismo lo deducí, fue lo primero que se me vino a la mente para ordenar un arreglo.

El de inserción lo ocupo en las cartas (sin saber que estaba haciendo este algoritmo) aunque nunca se me hubiera ocurrido implementarlos en programación.

El quicksort lo aprendi aquí y es realmente increible.

Hize un test para probar cuanto se demoraban en ordenar un arreglo de 100.000 enteros (int) con valores generados aleatoramiente, no los imprimí en pantalla obviamente porque de ser así, no podría medir correctamente los tiempos, en fin, los resultados fueron los siguientes:

Burbuja: 59 segundos.

Selección: 21 segundos.

Inserción: 28 segundos.

Quicksort: Menos de un segundo (Abro el programa y ya está todo ordenado)

Es un algoritmo muy rápido y relativamente sencillo, solo me ocupa 15 lineas de código.

Es el mejor :)

Gracias por enseñar!

Steven R. Davidson
2012-03-15 12:25:13

Hola Diego,

Me alegro que te guste este tema. La verdad es que hay varios algoritmos más de ordenación. Podrías echar un vistazo al algoritmo de ordenación por cuenta (o tanteo) que a veces también se llama ordenación por ránking (o por clasificación). Tenemos un artículo escrito acerca del algoritmo en nuestro apartado de artículos. Puedes dirigirte a: http://articulos.conclase.net/?tema=ordenacion&art=cuenta&pag=000 Es muy curioso porque no usa ninguna comprobación, pero sólo sirve para ordenar números enteros. La ordenación radical (radix sort, en inglés) también es bastante rápida. Este algoritmo tiene relación con la ordenación por casilleros o por cubos (bucket sort, en inglés), que también es interesante. Existen varios algoritmos más.

Los algoritmos que hay aquí en este curso se basan en una lista secuencial (un array). Los algoritmos algo más "interesantes" se basan en una estructura específica, como por ejemplo, listas dinámicamente enlazadas, árboles, y grafos. Claro está, no todos los algoritmos de ordenación se basan en ordenar de menor a mayor o de mayor a menor.

Hasta pronto,

Steven

Nicolás
2012-04-06 00:09:28

Muchas gracias por la publicación, no solamente hay que saber, si no que hay que saber compartirlo, el conocimiento guardado no sirve de nada.

Saludos.

Luis ruelas
2013-11-14 09:29:42

Ocupo un programa

que al introducirle una serie de 20 numeros me imprima la lista y despliegue en pantalla tres opciones de ordenamiento por SELECCION, INTERCAMBIO E INSERCION

alguien me puede ayudar

carolina
2014-03-20 00:28:18

holaa quería saber si me puedes ayudar a encontrar una idea de como hacer un algoritmo, me explico en clase me dieron el sgte problema:

tengo cinco cartas del naipe sin saber cuales son los números debo ordenarlas del menos al mayor

me podrias dar una idea de como empezar porfaa soy nueva en esto y de verdad me ha costado mucho entender u.u de ante manos muchas gracias :)

jessica
2014-04-15 22:19:59

hola quiisera que me ayudaras conel metodo de burbuja , para realizar el ordenamiento de manera ascendente de 250 letras introducidos por el usuario