hexadecimal

Algoritmos iterativos de ordenamiento1
El proceso de ordenar una lista de objetos de acuerdo a algún orden lineal, por ejemplo ≤
para números, es tan fundamental y se realiza tan frecuentemente, que el tema merece ser
estudiado en esta parte del curso.
El problema de ordenamiento consiste en organizar una secuencia de registros tal que
los valores de sus campos llave forman una secuencia nodecreciente. Es decir, dados
los registros r1, r2, …, rn, con llaves k1, k2, …, kn, respectivamente, debemos producir los
mismo registros en un orden ri1, ri2, …, rin, tal que ki1 ≤ ki2 ≤ ⋯ ≤ kin. Los registros registros no
necesariamente tienen valores diferentes, ni requerimos que los registros con la misma llave
aparezcan en algún orden en particular.
En este tema estudiaremos algunosalgoritmos de ordenamiento, tanto iterativos como
recursivos, y utilizaremos un arreglo de registros genéricos que tienes la forma siguiente:
registro RegistroT
comienza
tipoLlave llave
info datos
fin
El campo llave, que puede ser un tipo de datos para el cual exista un operador de orden lineal,
será el campo mediante el cual realizaremos el ordenamiento y el campo datos podría contenercualquier tipo de información e incluso podría ser otro registro.
También utilizaremos la siguiente función que intercambia la información de dos registros:
función intercambiar (RegistroT *x, RegistroT *y)
RegistroT aux
comienza
aux ← x
x ← y
y ← aux
fin
Se debe tomar en cuenta que los parámetros de entrada x y y se pasan por referencia, de ahí
que se marcan con un *.

Bubble sort
Estemétodo de ordenamiento es probablemente el más sencillo. La idea básica es imaginar
que los registros que se van a ordenar están contenidos en un arreglo vertical. Los registros
con una llave menor son “ligeros” y suben como burbujas hacia arriba. Hacemos varias
iteraciones sobre el arreglo desde el fondo hasta la superficie. MIentras hacemos esto,
si dos registros adyacentes no están ordenados,es decir, si el “ligero” está debajo, los
1

Tomado principalmente de: A.V. Aho, J.E. Hopcorft y J.D. Ullman, Data structures and
algorithms.Addison-Wesley, 1987.

invertimos. El efecto de esta operación es que en la primera iteración el registro “más ligero”,
es decir, el registro con la llave más pequeña, sube hasta la primera posición. En la segunda
iteración, el registro con lasegunda llave más pequeña sube hasta la segunda posición y así
sucesivamente.
función bubblesort (RegistroT *a[], entero n)
entero i, j
comienza
para i ← 1 hasta n-1 hacer
para j ← n hasta i+1 hacer
si a[j].llave < a[j-1].llave entonces
intercambiar (a[j], a[j-1])
fin si
fin para
fin para
fin
Ejemplo: Aplicar bubble sort para ordenar alfabéticamente la siguiente lista de volcanes.
NombreVesubio
Popocatépetl
Sta. Helena
Pelée
Etna
Krakatoa

Año de erupción
79
1947
1980
1902
1669
1883

En este caso, los registros a ordenar tendrán la siguiente estructura:
registro Volcan
comienza
carácter llave[] // El nombre del volcán
entero año
fin
i=1
inicio

j=6

j=5

j=4

j=3

j=2

Vesubio
Popocatépetl
Sta. Helena
Pelée
Etna
Krakatoa

VesubioPopocatépetl
Sta. Helena
Pelée
Etna
* Krakatoa

Vesubio
Popocatépetl
Sta. Helena
Etna
* Pelée
Krakatoa

Vesubio
Popocatépetl
Etna
* Sta. Helena
Pelée
Krakatoa

Vesubio
Etna
* Popocatépetl
Sta. Helena
Pelée
Krakatoa

Etna
* Vesubio
Popocatépetl
Sta. Helena
Pelée
Krakatoa

i=2
inicio

j=6

j=5

j=4

j=3

Etna
Vesubio
Popocatépetl
Sta. Helena
Pelée
KrakatoaEtna
Vesubio
Popocatépetl
Sta. Helena
Krakatoa
* Pelée

Etna
Vesubio
Popocatépetl
Krakatoa
* Sta. Helena
Pelée

Etna
Vesubio
Krakatoa
* Popocatépetl
Sta. Helena
Pelée

Etna
Krakatoa
* Vesubio
Popocatépetl
Sta. Helena
Pelée

i=3
inicio

j=6

j=5

j=4

Etna
Krakatoa
Vesubio
Popocatépetl
Sta. Helena
Pelée

Etna
Krakatoa
Vesubio
Popocatépetl
Pelée...