Ordenamiento

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. Este cap´ 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). o Output: Una permutaci´n de S (reordenamiento), S ′ = s′ , s′ , . . . , s′ tal que s′ ≤ s′ ≤ · · · ≤ s′ . n n 1 2 1 2 Generalmente la secuencia de input la representaremos como un arreglo de n elementos, sinembargo 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 su n´mero de RUT. Cuandointercambiamos 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 simplementeuna 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 cuantas asignaciones se realizaron en total. a a

2

´ CAP´ITULO 2. ALGORITMOS DE ORDENACION

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 que se 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 tiempo es O(n).

´ 2.1. ALGORITMOS SIMPLES DE ORDENACION

3

Figura 2.2: Ejemplo deejecuci´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 lo intercambia con A[j]:

Select-Sort(A) for j := 0 to n − 2 do k := j for i := j + 1 to n − 1 do ifA[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 Insert-Sort, en el peor caso Select-Sort toma tiempo O(n2 ). Una diferencia importante es que Select-Sort no...