Page 67 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Si n es una potencia de 2, entonces n = 2 . Así, resolviendo por sustituciones sucesivas se tiene:
k
T(n) = 2(T(n/2) + C
n
T(n) = 2(2T(n/4) + C ) + C
n /2 n
T(n) = 2(2(2T(n/8) + C ) + C ) + C
n/4 n/2 n
T(n) = 8T(n/8) + 4C +2C + C
n/4 n/2 n

Observando que 4C ~C , y T(n/2 ) = 0, se tiene:
k
n/4 n
T(n) = 2 T(n/2 ) + kC
k
k
n
T(n) = K C .
n
Conociendo que C O(n),
n
T(n)=K O(n).

Observando que n = 2 , K= log n, por lo tanto,
k
2
T(n) = O (n log n).

Método de ordeNacIóN rápIda (quIck Sort)

Este es actualmente el más eficiente y veloz de los métodos de ordenación interna. Fue llamado de
esta forma por su autor —C. A. Hoare—, y consiste en lo consiste:

1. Se toma un elemento X de una posición cualquiera del arreglo.

2. Se trata de ubicar a X en la posición correcta del arreglo, de modo que todos
los elementos que se encuentran a la izquierda sean menores o iguales a X, y to-
dos los que se hallan a la derecha sean mayores o iguales a X.

3. Se repiten los pasos anteriores, pero ahora para los conjuntos de datos que se
encuentran a la izquierda y a la derecha de la posición X en el arreglo.

4. El proceso termina cuando todos los elementos se hallan en su posición co-
rrecta en el arreglo.

61