hfujdssf

Cap´
ıtulo

2

Algoritmos de Ordenaci´n
o

Es mucho m´s f´cil, y r´pido que es lo que realmente nos importa, operar la informaci´n cuando
a a
a
o
esta se encuentra almacenada siguiendo cierto orden. Por ejemplo, cuando tenemos una lista ordenada
de n elementos, la b´squeda de un elemento particular puede hacerse de manera tan eficiente como
u
O(log n), usando b´squeda binaria. Estecap´
u
ıtulo est´ dedicado al problema de ordenaci´n que se
a
o
puede definir de la siguiente manera:
Input: Una secuencia de n elementos S = s1 , s2 . . . , sn (generalemente supondremos que si ∈ Z).
Output: Una permutaci´n de S (reordenamiento), S ′ = s′ , s′ , . . . , s′ tal que s′ ≤ s′ ≤ · · · ≤ s′ .
o
n
n
1
2
1 2
Generalmente la secuencia de input la representaremos como unarreglo de n elementos, sin embargo
en algunas aplicaciones puede estar representada usando cualquier otra estructura lineal, como por
ejemplo una lista ligada.
Es importante notar que en pocas aplicaciones reales estaremos interesados en ordenar n´meros,
u
entonces debemos pensar que lo que ordenamos son claves de objetos con datos sat´lite, por ejemplo
e
ordenar un grupo de personas por sun´mero de RUT. Cuando intercambiamos un RUT de posici´n,
u
o
lo que realmente estamos haciendo es intercambiar todos los datos de la persona. Si en alguna
aplicaci´n los datos sat´lites son demasiados, entonces no los moveremos todos cuando movamos su
o
e
clave, s´lo moveremos punteros a un objeto que los contenga. Por la discusi´n anterior, al estudiar el
o
o
problema de ordenaci´n,asumiremos siempre que el input es simplemente una secuencia de n´meros.
o
u
El traspaso desde un algoritmo que ordene n´meros a otro que ordene objetos m´s grandes (o con
u
a
mayor significado) debiese no presentar demasiado problema.
Como observaci´n final, en general cuando analicemos algoritmos de ordenaci´n, nos intereo
o
sar´ saber cu´ntas comparaciones entre elementos y cuantasasignaciones se realizaron en total.
a
a

´
CAP´
ITULO 2. ALGORITMOS DE ORDENACION

2

Figura 2.1: Ejemplo de ejecuci´n de Insert-Sort
o

2.1.

Algoritmos Simples de Ordenaci´n
o

Comenzaremos el cap´
ıtulo estudiando varios algoritmos de ordenaci´n. En general ellos se aseo
mejan mucho a los m´todos que una persona usa para ordenar objetos. Supondremos en cada caso
e
que lo quese quiere ordenar es un arreglo A[0 . . n − 1] de n elementos.

Ordenaci´n por Inserci´n
o
o
El algoritmo de ordenaci´n por inserci´n utiliza la siguiente estrategia: Mantiene la parte inicial
o
o
del arreglo ordenada, digamos los valores A[0 . . j − 1] y en la siguiente iteraci´n inserta el valor A[j]
o
en la posici´n que le corresponde:
o
Insert-Sort(A)
for j := 1 to n − 1
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
La figura 2.1 muestra una ejecuci´n de ejemplo de este algoritmo para un arreglo en particular. No
o
es dif´ demostrar que en el peor caso Insert-Sort toma tiempo O(n2 ). Un punto interesante es
ıcil
que el mejor caso de Insert-Sort ocurre cuando el arreglo se encuentra ordenado, en ese caso el
tiempoes O(n).

´
2.1. ALGORITMOS SIMPLES DE ORDENACION

3

Figura 2.2: Ejemplo de ejecuci´n de Select-Sort
o

Ordenaci´n por Selecci´n
o
o
El algoritmo de ordenaci´n por selecci´n utiliza la siguiente estrategia: Mantiene la parte inicial
o
o
del arreglo ordenada, digamos los valores A[0 . . j] y en la siguiente iteraci´n selecciona el menor de
o
los valores en A[j . . n − 1] y lointercambia con A[j]:

Select-Sort(A)
for j := 0 to n − 2
do k := j
for i := j + 1 to n − 1
do if A[i] < A[k]
then k := i
intercambia(A[j], A[k])

£
£
£
£

Inicialmente k es igual a j.
Despu´s de este ciclo
e
k es el ´
ındice del menor
elemento de A[j . . n − 1].

La figura 2.2 muestra una ejecuci´n de ejemplo de este algoritmo para un arreglo en particular. Al
o
igual que...