I Unidad: ORDENAMIENTO

Objetivos:

Conocer los principales y ms usados algoritmos de ordenacin que

existen.
Diferenciar los algoritmos de ordenacin.
Desarrollar programas en Lenguaje C, en los cuales se implementen
los algoritmos de ordenacin.

Contenidos:
1.
2.
3.
4.
5.
6.
7.
1.

Introduccin.
Mtodos de Ordenacin
Ordenacin por Intercambio
Ordenacin por Insercin
Ordenacin por seleccin
Resumen
Autoevaluacin

Introduccin

El ordenamiento es una labor comn 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
informacin de una manera especial basndonos en un criterio de ordenamiento.
En la computacin el ordenamiento de datos tambin cumple un rol muy
importante, ya sea como un fin en s o como parte de otros procedimientos ms
complejos. Se han desarrollado muchas tcnicas en este mbito, cada una con
caractersticas especficas, y con ventajas y desventajas sobre las dems. Aqu
mostraremos algunas de las ms comunes, tratando de hacerlo de una manera
sencilla y comprensible.
2.

Mtodos de ordenamiento

Ordenar significa reagrupar o reorganizar un conjunto de datos u objetos en una

secuencia especfica. Los procesos de ordenacin y bsqueda son algo frecuente
en nuestras vidas. Vivimos en un mundo desarrollado, automatizado, acelerado
donde la informacin representa un elemento de vital importancia. La sociedad
debe estar informada y por lo tanto el buscar y recuperar informacin es ahora una
necesidad.
La operacin de bsqueda para recuperar informacin, normalmente se efecta
sobre elementos ordenados. Lo que demuestra que, en general, donde haya
objetos que deban buscarse y recuperarse, el proceso de ordenacin estar
presente.

Los objetos ordenados aparecen por doquier. Nmeros telefnicos, registros de

pacientes de un hospital, registros de huspedes en un hotel, ndices de libros en
una biblioteca, son tan solo unos objetos ordenados con los cuales el ser humano
se encuentra frecuentemente. Incluso y de manera informal puede sealarse que
desde nio se le ensea a ser ordenado, a poner sus cosas en orden.
Formalmente se define ordenacin de la siguiente manera:
A1,A2,A3,...AN
Ordenar significa permutar estos elementos de tal forma que los mismos queden
de acuerdo con un orden preestablecido.

ascendente : A1 A2 A3 . . . AN
descendente : A1 A2 A3 . . . AN

En el procesamiento de datos, a los mtodos de ordenacin se les clasifica en dos

categoras:

Ordenacin de arreglos
Ordenacin de archivos

La primera categora recibe tambin el nombre de ordenacin interna, ya que los

elementos o componentes del arreglo se encuentran en la memoria principal de la
computadora. La segunda categora recibe tambin el nombre de ordenacin
externa, ya que los elementos se encuentran en archivos que estn almacenados
en dispositivos de almacenamiento secundarios.
Los mtodos directos ms conocidos son:

3.

Ordenacin por intercambio

Ordenacin por insercin
Ordenacin por seleccin

Ordenacin por intercambio directo (burbuja)

El mtodo de intercambio directo, conocido como de burbuja, es el ms utilizado,

es fcil de comprender y de programar.
El mtodo de intercambio directo puede trabajar de dos maneras diferentes.
Llevando los elementos ms pequeos hacia la parte izquierda del arreglo o bien
llevando los elementos ms grandes hacia la parte derecha del mismo.
La idea bsica de este algoritmo consiste en comparar pares de elementos
adyacentes e intercambiarlos entre s hasta que todos se encuentren ordenados.
Se realizan (n 1) pasadas, transportando en cada una de las mismas el menor o

mayor elemento (segn sea el caso) a su posicin ideal. Al final de las ( n 1 )

pasadas los elementos del arreglo estarn ordenados.

Ejemplo
Supngase que deseamos ordenar los siguientes elementos del arreglo A,
transportando en cada pasada le menor elemento hacia la parte izquierda del
arreglo.
A: 15 67

08

44

27

12

35

Las comparaciones que se realizan son las siguientes:

Primera Pasada
A[7] > A[8]
A[6] > A[7]
A[5] > A[6]
A[4] > A[5]
A[3] > A[4]
A[2] > A[3]
A[1] > A[2]

(12 > 35)

(27 > 12)
(44 >12)
(16 > 12)
(08 > 12)
(67 > 08)
(15 > 08)

No hay intercambio
Si hay intercambio
Si hay intercambio
Si hay intercambio
No hay intercambio
Si hay intercambio
Si hay intercambio

Luego de la primera pasada el arreglo queda de la siguiente forma:

A: 08 15

67

12

16

44

27

35

Observe que el elemento ms pequeo, en este caso, el 08, fue situado en

la parte izquierda del arreglo.
Segunda Pasada
A[7] > A[8]
A[6] > A[7]
A[5] > A[6]
A[4] > A[5]
A[3] > A[4]
A[2] > A[3]

(27 > 35)

(44 > 27)
(16 >27)
(12 > 16)
(67 > 12)
(15 > 12)

No hay intercambio
Si hay intercambio
No hay intercambio
No hay intercambio
Si hay intercambio
Si hay intercambio

Luego de la segunda pasa el arreglo queda de la siguiente forma:

A:

08

12

15

67

16

27

44

35

Y el segundo elemento ms pequeo del arreglo, en este caso 12, fue

situado en la segunda posicin.
A continuacin se presenta el resultado de las restantes pasadas:

Tercera pasada: 08 12 15 16 67
Cuarta pasada: 08 12 15 16 27
Quinta pasada: 08 12 15 16 27
Sexta pasada
08 12 15 16 27
Sptima pasada: 08 12 15 16 27

27
67
35
35
35

35 44
35 44
44 67
44 67
44 67

El algoritmo de ordenacin por el mtodo de intercambio directo que transporta en

cada pasada el menor elemento hacia la parte izquierda del arreglo es el
siguiente:
{ El algoritmo ordena los elementos del arreglo utilizando el mtodo de burbuja.
Transportando en cada pasada el elemento ms pequeo hacia la parte izquierda
del arreglo.
A es un arreglo de N elementos
I, J y AUX, son variables de tipo entero}
Inicio
1. Hacer Desde I = N hasta I
Inicio
Hacer Desde J = N hasta I
1.1.1 SI A[J-1] > A [J]entonces
Inicio
AUX = A[J - 1]
A[J-1] = A[J]
A[J] = AUX
Fin
Fin
Fin
Anlisis del algoritmo
ste es el anlisis para la versin no optimizada del algoritmo:

Estabilidad: Este algoritmo nunca intercambia registros con claves iguales.

Por lo tanto es estable.

Requerimientos de Memoria: Este algoritmo slo requiere de una variable

adicional para realizar los intercambios.

Tiempo de Ejecucin: El ciclo interno se ejecuta n veces para una lista de

n elementos. El ciclo externo tambin se ejecuta n veces. Es decir, la
complejidad es n * n = O(n2). El comportamiento del caso promedio
depende del orden de entrada de los datos, pero es slo un poco mejor que
el del peor caso, y sigue siendo O(n2).

Ventajas:

Fcil implementacin.

No requiere memoria adicional.

Desventajas:

4.

Muy lento.
Realiza numerosas comparaciones.
Realiza numerosos intercambios.
Ordenacin por insercin (Shaker sort)

El mtodo de shaker sort ms conocido como el mtodo de la sacudida, es una

optimizacin del mtodo de intercambio directo. La idea bsica de este algoritmo
consiste en mezclar las dos formas en que se pueden realizar el mtodo de
burbuja (traslado a la parte izquierda del menor o mayor valor de los elementos del
arreglo).
En este algoritmo cada pasada tiene dos etapas. En la primera etapa de derecha
a izquierda se trasladan los elementos ms pequeos hacia la parte izquierda del
arreglo, almacenando en una variable la posicin del ltimo elemento
intercambiado. En la segunda etapa de izquierda a derecha se trasladan los
elementos ms grandes hacia la parte derecha del arreglo, almacenando en otra
variable la posicin del ltimo elemento intercambiado. Las sucesivas pasadas
trabajan con los componentes del arreglo comprendido entre las posiciones
almacenadas en las variables. El algoritmo termina cuando en una etapa no se
produce intercambio o bien, cuando el contenido de la variable que almacena el
extremo izquierdo del arreglo es mayor que el contenido de la variable que
almacena el extremo derecho.
Ejemplo
Supngase que desea ordenarse los siguientes elementos del arreglo A utilizando
el mtodo de la sacudida.
A: 15 67
08
16
44
27
12
35
Primera pasada
Primera etapa (de derecha a izquierda)
A[7] > A[8] (12 > 35)
No hay intercambio
A[6] > A[7] (27 > 12)
Si hay intercambio
A[5] > A[6] (44 >12)
Si hay intercambio
A[4] > A[5] (16 > 12)
Si hay intercambio
A[3] > A[4] (08 > 12)
No hay intercambio
A[2] > A[3] (67 > 08)
Si hay intercambio
A[1] > A[2] (15 > 08)
Si hay intercambio

ltima posicin de intercambio de derecha a izquierda: 2

Luego de la primera etapa de la primera pasada, el arreglo queda de la siguiente
forma:
A:

08

15

67

12

16

44

27

35

Segunda etapa (de izquierda a derecha)

A[2] > A[3] (15 > 67)
No hay intercambio
A[3] > A[4] (67 > 12)
Si hay intercambio
A[4] > A[5] (67 >16)
Si hay intercambio
A[5] > A[6] (67 > 44)
Si hay intercambio
A[6] > A[7] (67 > 27)
Si hay intercambio
A[7] > A[8] (67 > 35)
Si hay intercambio
ltima posicin de intercambio de izquierda a derecha:

Luego de la segunda etapa de la primera pasada, el arreglo queda de la siguiente

forma:
A: 08 15

12

16

44

27

35

67

Segunda pasada
Primera etapa ( de derecha a izquierda )
A[6] > A[7]
A[5] > A[6]
A[4] > A[5]
A[3] > A[4]
A[2] > A[3]

(27 > 35)

(44 >27)
(16 > 27)
(12 > 16)
(15 > 12)

No hay intercambio
Si hay intercambio
No hay intercambio
No hay intercambio
Si hay intercambio

ltima posicin de intercambio de derecha a izquierda: 3

A: 08 12

15

16

27

44

35

67

Segunda etapa (de izquierda a derecha)

A[3] > A[4]
A[4] > A[5]
A[5] > A[6]
A[6] > A[7]

(15 > 16)

(16 > 27)
(27 > 44)
(44 > 35)

No hay intercambio
No hay intercambio
No hay intercambio
Si hay intercambio

ltima posicin de intercambio de izquierda a derecha:

A: 08 12

15

16

27

35

44

67

Al realizar la primera etapa de la tercera pasada se observa que no se realizaron

intercambios, por lo tanto la ejecucin del algoritmo termina.
El algoritmo de ordenacin por el mtodo de la sacudida es el siguiente:
{ El algoritmo ordena los elementos del arreglo utilizando el mtodo de la
sacudida. A es un arreglo de N elementos.}
{I, IZQ, DER, K Y AUX son variables de tipo entero}
Inicio
1.
2.
3.
4.

IZQ = 2;
DER = N;
K = N;
REPETIR
Inicio

4.1 Desde I = DER Hasta IZQ Hacer

Inicio
4.1.1 SI A[ I - 1 ]>A [ I ] ENTONCES
INICIO
AUX = A[ I 1];
A[ I 1] = A[I];
A[I] = AUX;
K = I;
Fin { condicional 4.1.1}
Fin { Del paso 4.1 }
IZQ = K + 1;
4.2 Desde I = IZQ Hasta DER Hacer
Inicio
4.2.1 Si A[ I 1] > A[I] Entonces
Inicio
AUX=A[I 1];
A[I 1 ] = A[ I ];
A[ I ] = AUX;
K = I;
Fin [ Condicional 4.2.1}
Fin {Del paso 4.2}
DER = K 1;
Fin { Del paso }
Hasta que IZQ > DER
Fin { Del algoritmo }

Anlisis de eficiencia del mtodo de la sacudida

El anlisis del mtodo de la sacudida y en general el de los mtodos mejorados y
logartmicos son muy complejos. Para el anlisis de este mtodo es necesario
tener en cuenta tres factores que afectan directamente al tiempo de ejecucin del
algoritmo: las comparaciones entre las claves, los intercambios entre las mismas y
las pasadas que se realizan. Encontrar frmulas que permitan calcular cada uno
de estos factores es una tarea muy difcil de realizar.
Los estudios que se han efectuado sobre el mtodo de la sacudida demuestra
que en el mismo, slo pueden reducirse las dobles comparaciones entre claves;
pero debe recordarse que la operacin de intercambio es una tarea ms
complicada y costosa que la de comparacin. Por lo tanto, es posible afirmar que
las hbiles mejoras realizadas sobre el mtodo de intercambio directo slo
producen resultados apreciables si el arreglo est parcialmente ordenado (lo cual
resulta difcil saber de antemano), pero si el arreglo est desordenado el mtodo
se comporta, incluso, peor que otros mtodos directos como los de insercin y
seleccin.

5.

Ordenacin por Seleccin Directa

El mtodo de ordenacin por seleccin directa es ms eficiente que los mtodos

analizados anteriormente. Pero, aunque su comportamiento es mejor y su
programacin es fcil y comprensible, no es recomendable utilizarlo cuando el
nmero de elementos del arreglo es medio o grande.
La idea bsica de este algoritmo consiste en buscar el menor elemento del arreglo
y colocarlo en la primera posicin. Luego se busca el segundo elemento ms
pequeo del arreglo y se le coloca en la segunda posicin. El proceso contina
hasta que todos los elementos del arreglo hayan sido ordenados. El mtodo se
basa en los siguientes principios:
1.
2.
3.

Seleccionar el menor elemento del arreglo

Intercambiar dicho elemento con el primero
Repetir los pasos anteriores con los ( n 1 ), ( n 2 )
elementos y as sucesivamente hasta que slo quede el elemento mayor.

Ejemplo
Supngase que desea ordenarse los siguientes elementos del arreglo A utilizando
el mtodo de seleccin directa.

A: 15 67

08

16

44

27

12

35

Las comparaciones que se realizan son las siguientes:

Primera pasada
Se realiza la siguiente asignacin Menor = A[1] (15)
(Menor < A[2]) (15 < 67 )
(Menor < A[3]) (15 < 08 )
(Menor < A[4])
(Menor < A[5])
(Menor < A[6])
(Menor < A[7])
(Menor < A[8])

Si se cumple la condicin
No se cumple la condicin
Menor = A[3] (08)
Si se cumple la condicin
Si se cumple la condicin
Si se cumple la condicin
Si se cumple la condicin
Si se cumple la condicin

(08 < 16 )
(08 < 44 )
(08 < 27 )
(08 < 12 )
(08 < 35 )

Luego de la primera pasada, el arreglo queda de la siguiente forma:

A: 08 67

15

16

44

27

12

35

Obsrvese que el menor elemento del arreglo, A[3] (08), se intercambi con el
primer elemento, A[1] (15), realizando solamente un movimiento.
Segunda pasada
Se realiza la siguiente asignacin Menor = A[2] (67)
(Menor < A[3]) (67 < 15 )
(Menor < A[4])
(Menor < A[5])
(Menor < A[6])
(Menor < A[7])

No se cumple la condicin
Menor = A[3] (15)
Si se cumple la condicin
Si se cumple la condicin
Si se cumple la condicin
No se cumple la condicin
Menor = A[7] (12)
Si se cumple la condicin

(15 < 16 )
(15 < 44 )
(15 < 27 )
(15 < 12 )

(Menor < A[8]) (12 < 35 )

Luego de la segunda pasada, el arreglo queda de la siguiente forma:

A: 08 12

15

16

44

27

67

35

Obsrvese que el segundo elemento ms pequeo del arreglo, A[7]

intercambi con el segundo elemento, A[2] (67).

(12), se

En la siguiente tabla se localiza el resultado de las restantes pasadas:

Tercera pasada: 08 12 15 16 44
Cuarta pasada: 08 12 15 16 44
Quinta pasada: 08 12 15 16 27
Sexta pasada
08 12 15 16 27
Sptima pasada: 08 12 15 16 27

27
27
44
35
35

67 35
67 35
67 35
67 44
44 67

El algoritmo de ordenacin por el mtodo de seleccin directa es el siguiente:

SELECCIN (A,N)
{Este algoritmo ordena los elementos del arreglo utilizando el mtodo de seleccin
directa. A es un arreglo de N elementos}
{ I, Menor, K y J son variables de tipo entero}
1.
Desde I = 1 hasta N 1 hacer
Inicio
Menor = A[I];
K = I;
1.1 Desde J = I + 1 hasta N hacer
Inicio
Si A[J] < Menor entonces
Inicio
Menor =A[J];
K = J;
Fin {Fin del ciclo del paso 1.1}
A[K]=A[I];
A[I]= Menor;
Fin {Del paso 1}
Fin {Del algoritmo}

Anlisis del algoritmo.

Estabilidad: si se tienen dos registros con claves iguales, el que ocupe la

posicin ms baja ser el primero que sea identificado como menor. Es
decir que ser el primero en ser desplazado. El segundo registro ser el
menor en el siguiente ciclo y quedar en la posicin adyacente. Por lo tanto
se mantendr el orden relativo. Lo que podra hacerlo inestable sera que

el ciclo que busca el elemento menor revisara la lista desde la ltima

posicin hacia atrs.

Requerimientos de Memoria: Al igual que el ordenamiento burbuja, este

algoritmo slo necesita una variable adicional para realizar los intercambios.
Tiempo de Ejecucin: El ciclo externo se ejecuta n veces para una lista
de n elementos. Cada bsqueda requiere comparar todos los elementos no
clasificados. Luego la complejidad es O(n2). Este algoritmo presenta un
comportamiento constante independiente del orden de los datos. Luego la
complejidad promedio es tambin O(n2).

Ventajas:
Fcil implementacin.
No requiere memoria adicional.
Realiza pocos intercambios.
Rendimiento constante: poca diferencia entre el peor y el mejor caso.
Desventajas:
Lento.
Realiza numerosas comparaciones.
6.
Resumen
Ahora ya conoces una buena cantidad de algoritmos, pero... cmo saber cul es
el que necesitas? cul 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. Slo existe el mejor para cada caso particular. Debes conocer a
fondo el problema que quieres resolver, y aplicar el ms adecuado. Aunque hay
algunas preguntas que te pueden ayudar a elegir:

Qu grado de orden tendr la informacin que vas a manejar? Si la

informacin 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( Se utiliza con memoria dinmica ) puede ser el ms indicado. Y
si no puedes hacer una presuncin sobre el grado de orden de la
informacin, 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 pequea, no

es necesario utilizar un algoritmo complejo, y es preferible uno de fcil
implementacin. Una cantidad muy grande puede hacer prohibitivo utilizar
un algoritmo que requiera de mucha memoria adicional.

Qu tipo de datos quieres ordenar? Algunos algoritmos slo funcionan

con un tipo especfico de datos (enteros, enteros positivos, etc.) y otros son
generales, es decir, aplicables a cualquier tipo de dato.

Qu tamao tienen los registros de tu lista? Algunos algoritmos

realizan mltiples intercambios (burbuja, insercin). Si los registros son de
gran tamao estos intercambios son ms lentos.