158 Ordenamiento, Búsqueda e Intercalación
cual las técnicas pueden extenderse a estructuras más complicadas.Por razones de ahorro de
memoria, estudiaremos el ordenamiento de un arreglo sobre sí mismo, es decir sin emplear
arreglos auxiliares, y consideraremos sólo el ordenamiento creciente, ya que para el decreciente
bastaría cambiar el sentido de las desigualdades.
7.1.1 Ordenamiento por selección
Dado un arreglo de n componentes, el método de selección para ordenarlo en forma ascen-
dente, es el siguiente:
encontrar el menor valor del arreglo (seleccionar el valor mínimo del arreglo)
intercambiar el elemento encontrado con el primero del arreglo.
repetir estas operaciones con los n-1 elementos restantes, seleccionando, el segundo
elemento, así sucesivamente.
A continuación veremos cómo funciona el método a través de un ejemplo.
Supongamos que disponemos de un arreglo unidimensional de 8 componentes enteras
8 6 -1 2 0 3 -4 3
Determinamos la componente con valor mínimo -4 (podría eventualmente haber más de una, en
dicho caso seleccionamos la primera encontrada), y la intercambiamos con la primera compo-
nente del arreglo original. Al intercambiar resulta:
-4 | 6 -1 2 0 3 8 3
La primera componente del arreglo ha quedado ordenada, en el sentido de que es menor o
igual que todas las siguientes . Ahora se trata de reordenar las n-1 componentes que siguen a la
primera. Empleamos el mismo criterio: intercambiar la componente a ordenar con el mínimo de
las que le siguen. Es decir, para ordenar la segunda componente, el mínimo es -1 y resulta:
-4 -1 | 6 2 0 3 8 3
donde las dos primeras componentes están ordenadas.
Así seguimos hasta ordenar la componente n-1, pues al ser ésta menor o igual que las que
le siguen, la n queda también ordenada.
-4 -1 0 | 2 6 3 8 3
-4 -1 0 2 | 6 3 8 3
-4 -1 0 2 3 | 6 8 3
-4 -1 0 2 3 3 | 8 6
-4 -1 0 2 3 3 6 | 8
Veamos la implementación de un algoritmo para realizar este proceso. Para ello, sea un ar-
reglo de elementos reales a ordenar. Suponemos n < 10000 y declaramos un arreglo de tamaño
fijo de 10000 componentes, de las cuales ordenamos las n primeras.
7.1 Ordenamiento 159
AlgoritmoSeleccion
entero n, i, j ,lugar
real V[10000], min
inicio
Leer (n) ! cantidad de elementos, suponemos 0<n<=10000
Repetir Para i ← 1, n
Leer (V[i])
fin para
! Comienza el ordenamiento
RepetirPara i ← 1, n-1 ! i es la componente a ordenar
min ← V[i]
lugar ← i
RepetirPara j ← i+1, n
Si (V[j] < min) entonces
min ← V[j] ! cambiar el mínimo
lugar ← j ! posición del mínimo
fin si
fin para
V[lugar] ← V[i] ! intercambiar
V[i] ← min
fin para
Repetir Para i ← 1, n
Escribir (V[i])
fin para
fin
¿Qué sucede si n = 1? Simplemente el “Repetir Para” desde 1 hasta 0 no se ejecuta, y el
arreglo de 1 elemento queda como está.Observar que en caso de haber dos o más componentes
de igual valor mínimo, la que se selecciona es la que se encontró primero, pues la acción “si V[j]
< min” implica que no se ejecuta con valores iguales.
7.1.2 Ordenamiento por intercambio o método de la burbuja
Este método comienza comparando cada elemento del arreglo con su siguiente, e intercam-
biándolos si es necesario para que queden ordenados.
Considerando el arreglo desordenado:
8 6 -1 2 0 3 -4 3
si queremos ordenarlo de menor a mayor, comparamos el primer elemento (8) con el segundo
(6), y vemos que hay que intercambiarlos, obteniendo:
6 8 -1 2 0 3 -4 3
Luego hacemos lo mismo con el segundo (8) y el tercero (-1):