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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

En este caso, para la programación del algoritmo, el elemento X será el primer elemento de la lista.
Se empieza a recorrer el arreglo de derecha a izquierda comparando si los elementos son mayores o
iguales a X. Si un elemento no cumple con esta condición, se intercambian aquellos y se almacena
en una variable la posición del elemento intercambiado —se acota el arreglo por la derecha—. Se
inicia nuevamente el recorrido, pero ahora de izquierda a derecha, comparando si los elementos son
menores o iguales a X. Si un elemento no cumple con esta condición, entonces se intercambian
aquellos y se almacena en otra variable la posición del elemento intercambiado —se acota el arreglo
por la izquierda—. Se repiten los pasos anteriores hasta que el elemento X encuentra su posición
correcta en el arreglo. En este momento, dependiendo del lugar que ocupe el valor de X, se hará
una recursividad izquierda tomando solo los primeros elementos del subarreglo hasta el vecino a la
izquierda de X o una recursividad a la derecha del vecino más cercano a la derecha de X hasta el final
del subarreglo. A continuación, se muestra el algoritmo 2.6 en lenguaje de programación C.

Algoritmo 2.6. Método quick sort

62