Algoritmo Ordenamiento

Capítulo 6

Algoritmos de Ordenamiento
6.1 Concepto de Ordenamiento
DEFINICIÓN.
Entrada: Una secuencia de n números , usualmente en la
forma de un arreglo de n elementos.
Salida: Una permutación de la secuencia de entrada tal
que a’1 = a’2 = … = a’n.
CONSIDERACIONES. Cada número es normalmente una clave que forma
parte de un registro; cada registro contiene además datos satélites quese
mueven junto con la clave; si cada registro incluye muchos datos satélites,
entonces movemos punteros a los registros (y no los registros).
Un método de ordenación se denomina estable si el orden relativo de los
elementos no se altera por el proceso de ordenamiento. (Importante cuanto
se ordena por varias claves).
Hay dos categorías importantes y disjuntas de algoritmos de ordenación:
•Ordenación interna: La cantidad de registros es suficientemente
pequeña y el proceso puede llevarse a cabo en memoria.

•

Ordenación externa: Hay demasiados registros para permitir
ordenación interna; deben almacenarse en disco.

Por ahora nos ocuparemos sólo de ordenación interna.
Los algoritmos de ordenación interna se clasifican de acuerdo con la
cantidad de trabajo necesaria paraordenar una secuencia de n elementos:
¿Cuántas comparaciones de elementos y cuántos movimientos de
elementos de un lugar a otro son necesarios?
Empezaremos por los métodos tradicionales (inserción y selección). Son
fáciles de entender, pero ineficientes, especialmente para juegos de datos
grandes. Luego prestaremos más atención a los más eficientes: heapsort y
quicksort.

Página 63

6.2Ordenamiento por Inserción
Este es uno de los métodos más sencillos. Consta de tomar uno por uno los
elementos de un arreglo y recorrerlo hacia su posición con respecto a los
anteriormente ordenados. Así empieza con el segundo elemento y lo ordena
con respecto al primero. Luego sigue con el tercero y lo coloca en su posición
ordenada con respecto a los dos anteriores, así sucesivamente hastarecorrer
todas las posiciones del arreglo.
Este es el algoritmo:
Sea n el número de elementos en el arreglo A.
I NSERTION-SORT(A) :
{Para cada valor de j, inserta A[j] en la posición que le corresponde en la
secuencia ordenada A[1 .. j – 1]}
for j ← 2 to n do
k ← A[j]
i← j–1
while i > 0 ∧ A[i] > k do
A[i + 1] ← A[i]
i← i–1
A[i + 1] ← k
Análisis del algoritmo:
Número decomparaciones: n(n-1)/2 lo que implica un T(n) = O(n2 ). La
ordenación por inserción utiliza aproximadamente n2 /4 comparaciones y
n2 /8 intercambios en el caso medio y dos veces más en el peor de los casos.
La ordenación por inserción es lineal para los archivos casi ordenados.
6.3 Ordenamiento por Selección
El método de ordenamiento por selección consiste en encontrar el menor de
todos los elementosdel arreglo e intercambiarlo con el que está en la primera
posición. Luego el segundo más pequeño, y así sucesivamente hasta ordenar
todo el arreglo.
SELECTION-SORT(A) :
{Para cada valor de j, selecciona el menor elemento de la secuencia no
ordenada A[j .. n] y lo intercambia con A[j]}
for j ← 1 to n – 1 do
k←j
for i ← j + 1 to n do
if A[i] < A[k] then k ← i
intercambie A[j] ↔ A[k]Página 64

Análisis del algoritmo:
La ordenación por selección utiliza aproximadamente n2 /2 comparaciones y
n intercambios, por lo cual T(n) = O(n2 ).
6.4 Ordenamiento de la Burbuja (Bubblesort)
El algoritmo bubblesort, también conocido como ordenamiento burbuja,
funciona de la siguiente manera: Se recorre el arreglo intercambiando los
elementos adyacentes que estén desordenados. Se recorre elarreglo tantas
veces hasta que ya no haya cambios que realizar. Prácticamente lo que hace es
tomar el elemento mayor y lo va recorriendo de posición en posición hasta
ponerlo en su lugar.
Procedimiento BubbleSort
for (i = n; i >= 1; i--)
for (j = 2; j A[j]) then intercambie(A, j-1, j);
}
Análisis del algoritmo:
La ordenación de burbuja tanto en el caso medio como en el peor de los...