Algoritmo De Ordenamiento

CI7681 Teor´ de Algoritmos ıa

Mayo-Agosto 2002

Lecci´n 4: 10 Junio o
Profesor: Argimiro Arratia Apuntador: Juan Arismendi

4.1

Algoritmo Heap-Sort
Heap-Sort(Entrada: A[1, . . . , n]) 1. % A es un arreglo de longitud n % a ser ordenado de manera ascendente 2. Construir-Heap(A[1, . . . , n]) 3. para i := n en descenso hasta 2 hacer 4. intercambiar A[1] y A[i] 5. Filtrar(A[1, . . . , i− 1], 1) Salida: (A) Figura 4.1: Algoritmo Heap-sort.

Teorema 4.1 Heap-sort ordena arreglos de longitud n en tiempo O(n log n) Demostraci´n: Construir heap toma tiempo lineal O(n). Las l´ o ıneas 3 – 5 se ejecutan n – 1 veces. Intercambiar toma tiempo Θ(1). En el peor caso debemos filtrar A[1] hasta el nivel 0 del heap lo cual lleva ≤ c log n ejecuciones del ciclo dentro del Filtrar. Por lo tanto,el tiempo del peor caso de Heap-sort es; T (n) = Θ(n) + (n − 1)Θ(1) + (n − 1)O(log n) = O(n log n) (La complejidad espacial es Θ(1))

4.2

Algoritmo Quick-Sort

Otro algoritmo para ordenar muy popular es Quick-sort (Ordenamiento R´pido) a Idea: Se basa en el paradigma divide y conquistar´s. a Dado un arreglo A de n elementos, se escoge un elemento A[k]=p en A, el pivote, se colocan todoslos A[i] < p a la izquierda de k (la posici´n de p= A[k]) y los mayores a la derecha. Luego ordeno recursivamente o A[1, ..., k − 1] y A[k + 1, ..., n], sin necesidad de hacer Fusi´n posteriormente, ya que los elementos del primer o pedazo ya son menores que los del segundo pedazo. El proceso inicial de ordenar alrededor del pivote, lo llamaremos “pivotear”. Escoger un pivote adecuado (e.g. el valormedio) puede resultar costoso; por lo tanto, lo usual es escoger como pivote p = A[1]. Veamos como implementar Pivotear: 4-1

4-2

Lecci´n 4: 10 Junio o

Pivotear(Entrada: A[1, . . . , n], i, j ∈ {1, . . . , n}) % Permuta los elementos de A[1, . . . , j] y retorna l % tal que i ≤ l ≤ j , A[k] ≤ p % ∀i ≤ k < l, A[l] = p y A[k] > p ∀l < k ≤ j, donde inicialmente A[i] = p 1. p := A[i] 2. k :=i & l := j + 1 3. repetir k := k + 1 hata que A[k] > p o k ≥ j 4. repetir l := l − 1 hata que A[l] ≤ p 5. mientras k < l hacer 6. intercambiar A[k] y A[l] 7. repetir k := k + 1 hata que A[k] > p 8. repetir l := l − 1 hata que A[l] ≤ p 9. % fin de mientras 10. intercambiar A[i] y A[l] Salida: (A, l) Figura 4.2: Algoritmo Pivotear. Quick-Sort(Entrada: A, i, j) 1. si i < j entonces 2. A[i, . . . ,j], l ←− Pivotear(A, i, j) 3. Quick-Sort(A, i, l) 3. Quick-Sort(A, l + 1, j) Salida: (A) Figura 4.3: Algoritmo Quick-Sort. Para ordenar todo A corremos Quick-sort(A, 1, |A|) Es f´cil ver que el peor escenario es cuando A ya esta ordenado de manera ascendente. En ese caso i = 1 y a particionamos en pedazos de tama˜o 1 y j = i − 1 lo cual da origen a la recurrencia: n T (n) = T (n − 1) + cn = O(n2 )Entonces ¿Por qu´ lo denominamos Quick-sort (r´pido)? e a En promedio Quick-sort tiene comportamiento de O(n log n). Adem´s las constantes escondidas en la notaci´n asint´tica son peque˜as. Por otro lado, su complejidad a o o n espacial es constante Θ(1).

4.3

An´lisis del Caso Promedio: a

Debemos hacer una suposici´n sobre la manera como las instancias del problema pueden aparecer m´s o afrecuentemente. En el caso del problema de ordenamiento, asumiremos que:

Lecci´n 4: 10 Junio o

4-3

• Todos los arreglos tienen elementos distintos. • Para cada n la probabilidad de que cierto arreglo de longitud n ocurra, entre los n! arreglos posibles, es la misma, es decir, las instancias del problema de ordenar n elementos est´n distribuidas uniformemente. a Lo anterior implica quela probabilidad de que cierto valor i entre 1 y n sea escogido es
1 n.

Proposici´n 4.2 Sea T (n) el tiempo del caso promedio para Quick-sort, para arreglos de longitud n (diso tribuidos uniformemente). Entonces T (n) = O(n log n). Demostraci´n: Vimos que pivotear toma tiempo Θ(n) y esta rutina retorna un valor l, la posici´n del o o pivote entre 1 y n. Luego aplicamos Quick-sort a dos...