From: Subject: Algoritmos de Ordenamiento Date: Fri, 21 Jul 2006 19:37:35 -0600 MIME-Version: 1.0 Content-Type: multipart/related; type="text/html"; boundary="----=_NextPart_000_0000_01C6ACFD.1DD01F80" X-MimeOLE: Produced By Microsoft MimeOLE V6.00.3790.2663 This is a multi-part message in MIME format. ------=_NextPart_000_0000_01C6ACFD.1DD01F80 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Content-Location: http://c.conclase.net/orden/index.html Algoritmos de Ordenamiento

Algoritmos de Ordenamiento

[C con Clase] [1 Burbuja] =

1. Introducci=F3n.

El ordenamiento es una labor com=FAn que realizamos continuamente. = =BFPero te has=20 preguntado qu=E9 es ordenar? =BFNo? Es que es algo tan corriente en = nuestras vidas=20 que no nos detenemos a pensar en ello. Ordenar es simplemente colocar=20 informaci=F3n de una manera especial bas=E1ndonos en un criterio de=20 ordenamiento.

En la computaci=F3n el ordenamiento de datos tambi=E9n cumple un rol = muy=20 importante, ya sea como un fin en s=ED o como parte de otros = procedimientos m=E1s=20 complejos. Se han desarrollado muchas t=E9cnicas en este =E1mbito, cada = una con=20 caracter=EDsticas espec=EDficas, y con ventajas y desventajas sobre las = dem=E1s. Aqu=ED=20 voy a mostrarte algunas de las m=E1s comunes, tratando de hacerlo de una = manera=20 sencilla y comprensible.

2. Conceptos Preliminares.

Antes de comenzar a ver cada algoritmo vamos a ponernos de acuerdo en = algunos=20 conceptos, para que no haya confusiones:

Clave: La parte de un registro = por la=20 cual se ordena la lista. Por ejemplo, una lista de registros con = campos=20 nombre, direccion y telefono se puede ordenar=20 alfab=E9ticamente de acuerdo a la clave nombre. En este caso = los campos=20 direccion y telefono no se toman en cuenta en el = ordenamiento.=20
Criterio de ordenamiento (o de=20 comparaci=F3n): EL criterio que utilizamos para asignar valores a = los=20 registros con base en una o m=E1s claves. De = esta manera=20 decidimos si un registro es mayor o menor = que=20 otro. En el pseudoc=F3digo presentado m=E1s adelante simplemente se = utilizar=E1n los=20 s=EDmbolos < y >, para mayor simplicidad.=20
Registro: Un grupo de datos = que forman=20 la lista. Pueden ser datos at=F3micos (enteros, caracteres, reales, = etc.) o=20 grupos de ellos, que en C equivalen a las estructuras.

Cuando se estudian algoritmos de todo tipo, no s=F3lo de = ordenamiento, es bueno=20 tener una forma de evaluarlos antes de pasarlos a c=F3digo, que se base = en=20 aspectos independientes de la plataforma o el lenguaje. De esta manera = podremos=20 decidir cu=E1l se adapta mejor a los requerimientos de nuestro programa. = As=ED que=20 veamos estos aspectos:

Estabilidad: C=F3mo se = comporta con=20 registros que tienen claves = iguales.=20 Algunos algoritmos mantienen el orden relativo entre =E9stos y otros = no. Veamos=20 un ejemplo. Si tenemos la siguiente lista de datos (nombre, edad): = "Pedro=20 19, Juan 23, Felipe 15, Marcela 20, Juan 18, Marcela 17", y la = ordenamos=20 alfab=E9ticamente por el nombre con un algoritmo estable = quedar=EDa as=ED:=20 "Felipe 15, Marcela 20, Marcela 17, Juan 23, Juan 18, Pedro = 19". Un=20 algoritmo no estable podr=EDa dejar a Juan 18 antes de Juan = 23, o=20 a Marcela 20 despu=E9s de Marcela 17.=20
Tiempo de = ejecuci=F3n: La=20 complejidad del algoritmo, que no tiene que ver con dificultad, sino = con=20 rendimiento. Es una funci=F3n independiente de la implementaci=F3n. Te = la voy a=20 explicar brevemente: tenemos que identificar una operaci=F3n = fundamental que=20 realice nuestro algoritmo, que en este caso es comparar. Ahora = contamos=20 cu=E1ntas veces el algoritmo necesita comparar. Si en una lista de = n=20 t=E9rminos realiza n comparaciones la complejidad es O(n). (En = realidad=20 es un poco m=E1s complicado que eso, pero lo vamos a hacer as=ED: = recuerda que=20 dije que te iba a explicar brevemente). Algunos ejemplos de = complejidades=20 comunes son:=20
- O(1) : Complejidad constante.=20
- O(n²) : Complejidad cuadr=E1tica.=20
- O(n log(n)) : Complejidad logar=EDtmica.
Ahora = podemos=20 decir que un algoritmo de complejidad O(n) es m=E1s r=E1pido que uno = de=20 complejidad O(n²). Otro aspecto a considerar es la = diferencia entre=20 el peor y el mejor caso. Cada algoritmo se comporta de modo diferente = de=20 acuerdo a c=F3mo se le entregue la informaci=F3n; por eso es = conveniente estudiar=20 su comportamiento en casos extremos, como cuando los datos est=E1n = pr=E1cticamente=20 ordenados o muy desordenados.=20
Requerimientos de = memoria: El=20 algoritmo puede necesitar memoria adicional para realizar su labor. En = general=20 es preferible que no sea as=ED, pero es com=FAn en la programaci=F3n = tener que=20 sacrificar memoria por rendimiento.

Hay bastantes otros aspectos que se pueden tener en cuenta, pero = nosotros nos=20 vamos a quedar con =E9sos.

Por =FAltimo estableceremos algunas convenciones sobre el = pseudoc=F3digo:

Vamos a ordenar la lista en forma ascendiente, es decir, de menor = a mayor.=20 Obviamente es esencialmente lo mismo que hacerlo en forma inversa.=20
La forma de intercambiar los elementos depende de la estructura de = datos:=20 si es un arreglo (din=E1mico o est=E1tico) es necesario guardar una = copia del=20 primer elemento, asignarle el segundo al primero y el temporal al = segundo. La=20 variable temporal es necesaria, porque de lo contrario se perder=EDa = uno de los=20 elementos. Si la estructura es una lista din=E1mica el procedimiento = es=20 parecido, pero se utilizan las direcciones de los elementos. En el=20 pseudoc=F3digo se utilizar=E1 el primer m=E9todo.=20
La lista se manejar=E1 como un arreglo de C: si tiene TAM = elementos, el=20 primer elemento es lista[0] y el =FAltimo es lista[TAM-1]. Esto ser=E1 = as=ED para=20 todo el pseudoc=F3digo presentado en este art=EDculo.

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

3. Algoritmos m=E1s comunes.

La siguiente es una tabla comparativa de algunos algoritmos de = ordenamiento.=20 Si quieres saber m=E1s sobre alguno en particular haz un click sobre su = nombre. En=20 cada p=E1gina encontrar=E1s una descripci=F3n, pseudoc=F3digo y un = an=E1lisis sobre su=20 rendimiento, ventajas y desventajas.

(Quiz=E1s quieras bajar ahora la demostraci=F3n= para ir=20 observ=E1ndola a medida que vayas leyendo)

Tabla comparativa de algoritmos
Nombre	Complejidad	Estabilidad	Memoria adicional
Ordenamiento = Burbuja=20 (Bubblesort)	O(n²)	Estable	No
Ordenamiento = por=20 Selecci=F3n	O(n²)	No Estable	No
Ordenamiento = por=20 Inserci=F3n	O(n²)	Estable	No
Ordenamiento = R=E1pido=20 (Quicksort)	O(n * log₂(n))	No Estable	No

4. Eligiendo el m=E1s adecuado.

Ahora ya conoces una buena cantidad de algoritmos, pero... =BFc=F3mo = saber cu=E1l=20 es el que necesitas? =BFcu=E1l es EL algoritmo?

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

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

5. Demostraci=F3n y C=F3digo Fuente.

Puedes descargar dos programas de demostraci=F3n con los algoritmos = presentados=20 en este art=EDculo:

OrdWin: = En este=20 programa puedes ver una demostraci=F3n gr=E1fica de cada algoritmo. = Tambi=E9n puedes=20 experimentar ordenando listas de la longitud que quieras, observando el = tiempo=20 que demoran, la cantidad de comparaciones y de intercambios que = realizan. Fue=20 creado utilizando el compilador LccWin32 de Jacob = Navia, pero=20 el fichero descargable es un proyecto para Dev-C++. Incluye el = ejecutable, el=20 c=F3digo fuente y este art=EDculo completo.

Ordenar: = Este=20 programa es m=E1s indicado si lo que quieres es mirar c=F3digo. No hay = funciones=20 gr=E1ficas ni nada del API de Windows. Deber=EDa funcionar en cualquier = otro=20 compilador sin mayores cambios, pues est=E1 hecho en ANSI C. Fue probado = con =E9xito=20 en Turbo C++, DJGPP, LccWin32, y Dev-C++. Qued=F3 bastante feo, pero es = el precio=20 que hay que pagar por la portabilidad ;-). S=F3lo incluye el c=F3digo. =

6. Algunas palabras para terminar.

No sab=EDa si escribir este art=EDculo o no. Probablemente no sea yo = el indicado=20 para hacerlo. Despu=E9s de todo no soy ning=FAn experto ni mucho menos, = pero creo=20 que puede ayudar a alguien que sepa menos que yo (no deben ser muchos = :-)). Por=20 eso pido tu colaboraci=F3n para mejorar este documento y hacerlo algo = =FAtil. Si=20 tienes sugerencias, comentarios o correcciones por favor h=E1zmelo saber. =

7. Bibliograf=EDa.

H.M. Deitel, P.J. Deitel: "C=F3mo programar en = C/C++".=20 Editorial Prentice Hall.=20
Charles Bowman: "Algoritmos y estructuras de datos: = Aproximaci=F3n en=20 C". Oxford University Press, 1999.=20
"Dictionary of Algorithms, = Data=20 Structures, and Problems"

[C con Clase] [Art=EDculos] [1 Burbuja] =

=A9 Diciembre de 2001 - Juli=E1n Hidalgo =

------=_NextPart_000_0000_01C6ACFD.1DD01F80 Content-Type: text/css; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Content-Location: http://c.conclase.net/orden/alg_ord.css BODY { COLOR: black; FONT-FAMILY: Verdana, Arial, Helvetica, Helv, sans-serif; = BACKGROUND-COLOR: white } H1 { FONT-SIZE: x-large; COLOR: #069; BACKGROUND-COLOR: white; TEXT-ALIGN: = center } H2 { PADDING-RIGHT: 2px; PADDING-LEFT: 2px; FONT-SIZE: large; = PADDING-BOTTOM: 2px; COLOR: #00c; PADDING-TOP: 2px; BACKGROUND-COLOR: = #8be } TABLE { BORDER-RIGHT: #069 thin solid; BORDER-TOP: #069 thin solid; = BORDER-LEFT: #069 thin solid; WIDTH: 90%; BORDER-BOTTOM: #069 thin = solid; TEXT-ALIGN: center } CAPTION { FONT-SIZE: medium; COLOR: #069; BACKGROUND-COLOR: transparent } TH { BORDER-RIGHT: black thin solid; BORDER-TOP: black thin solid; = BORDER-LEFT: black thin solid; COLOR: white; BORDER-BOTTOM: black thin = solid; BACKGROUND-COLOR: teal } TD { BORDER-RIGHT: #069 thin solid; BORDER-TOP: #069 thin solid; = BORDER-LEFT: #069 thin solid; BORDER-BOTTOM: #069 thin solid; = TEXT-ALIGN: center } B { FONT-WEIGHT: bold } PRE.pseudo { BORDER-RIGHT: black thin solid; PADDING-RIGHT: 4px; BORDER-TOP: black = thin solid; PADDING-LEFT: 4px; PADDING-BOTTOM: 4px; MARGIN-LEFT: 20%; = BORDER-LEFT: black thin solid; WIDTH: 25em; COLOR: rgb(20,0,0); = MARGIN-RIGHT: 20%; PADDING-TOP: 4px; BORDER-BOTTOM: black thin solid; = FONT-FAMILY: Verdana,Arial,Helvetica,sans-serif; WHITE-SPACE: pre; = BACKGROUND-COLOR: rgb(220,220,220) } P.ejemp { BORDER-RIGHT: black thin solid; PADDING-RIGHT: 4px; BORDER-TOP: black = thin solid; PADDING-LEFT: 4px; FONT-SIZE: medium; PADDING-BOTTOM: 4px; = MARGIN-LEFT: 30%; BORDER-LEFT: black thin solid; COLOR: rgb(20,0,0); = MARGIN-RIGHT: 30%; PADDING-TOP: 4px; BORDER-BOTTOM: black thin solid; = BACKGROUND-COLOR: rgb(220,220,220); TEXT-ALIGN: center } P.ejemp B { COLOR: #069; BACKGROUND-COLOR: transparent } P.ejemp B.div { COLOR: white; BACKGROUND-COLOR: #00c } LI P.ejemp { MARGIN-LEFT: 25%; MARGIN-RIGHT: 25% } UL { PADDING-BOTTOM: 3px; PADDING-TOP: 3px; FONT-FAMILY: Verdana, Arial, = Helvetica, Helv, sans-serif } LI { PADDING-BOTTOM: 3px; PADDING-TOP: 3px; FONT-FAMILY: Verdana, Arial, = Helvetica, Helv, sans-serif } P.barra { PADDING-RIGHT: 4px; PADDING-LEFT: 4px; FONT-WEIGHT: bold; = PADDING-BOTTOM: 4px; COLOR: maroon; PADDING-TOP: 4px; BACKGROUND-COLOR: = #00ccff; TEXT-ALIGN: center } P.nota { FONT-WEIGHT: bold; FONT-STYLE: italic } P.copyr { FONT-SIZE: x-small } P { FONT-FAMILY: Verdana, Arial, Helvetica, Helv, sans-serif } A { COLOR: #00c; BACKGROUND-COLOR: transparent; TEXT-DECORATION: none } A:hover { COLOR: maroon; BACKGROUND-COLOR: transparent; TEXT-DECORATION: none } A:visited { TEXT-DECORATION: none } A:active { COLOR: maroon; BACKGROUND-COLOR: transparent; TEXT-DECORATION: none } ------=_NextPart_000_0000_01C6ACFD.1DD01F80--