Page 69 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 69
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
Para ejemplificar, en la figura 2.3, dentro de cada cuadro, se muestra la parte iterativa y cada llamada
recursiva crea un nuevo cuadro. Los números con negrita son los que se utilizan como pivote para
que sean los que se van a acomodar de tal forma que a su izquierda se coloquen los números me-
nores a él y a la derecha los números mayores a él.
Figura 2.3. Árbol recursivo utilizando quick sort
El método quick sort es el más rápido de ordenación interna que existe en la actualidad, lo cual es
sorprendente porque este tiene su origen en el método de intercambio directo, el peor de todos los
directos.
Diversos estudios realizados sobre su comportamiento demuestran que si se escoge en cada pa-
sada el elemento que ocupa la posición central del conjunto de datos a analizar, y si el tamaño del
arreglo es una potencia de 2, en la primera pasada realiza (n-1) comparaciones; en la segunda
(n-1)/2 comparaciones, pero en dos conjuntos diferentes; en la tercera (n-1)/4 comparaciones, pero
en cuatro conjuntos diferentes, y así sucesivamente. Esto produce un árbol binario recursivo. Por lo
tanto,
63
