Universidad Nacional de Lanús – 2024 – Programación Concurrente

ANÁLISIS DE QUICKSORT – VARIANTE SECUENCIAL Y

CONCURRENTE

Datos del autor: Ulises Justo Saucedo

Repositorio con el trabajo: ulises-justo-saucedo/UNLA-TP-Programacion-Concurrente
([Link])
Video explicativo: [Link]
Email: ulisesjustosaucedo@[Link]

RESUMEN
En este informe se explicará el funcionamiento del algoritmo de ordenamiento QuickSort tanto en su
variante secuencial como concurrente. La implementación concurrente fue hecha por mí, y es una manera
simple y rápida de aplicar concurrencia a QuickSort. Por su simplicidad, no se puede obtener tanta
eficiencia como podría ser con otras implementaciones, pero pese a ello con las tablas comparativas que se
verán en este informe, se podrá ver como aun así la concurrencia acaba venciendo por mucho a la
implementación secuencial. Aunque también se verá como esto último no ocurre siempre ya que, bajo
ciertas condiciones, la implementación concurrente puede acabar perdiendo por mucho ante la secuencial.

Keywords: pivote, subarreglos, hilos, concurrencia, secuencial, eficiencia, tiempos, comparacion.

1. INTRODUCCIÓN
El pivote (en nuestro caso) es el último elemento
QuickSort es un algoritmo de ordenamiento que
del arreglo. El puntero izquierdo apunta a la
utiliza cuatro herramientas principales para realizar
primera posición del arreglo, y el puntero derecho
su tarea: un pivote, subarreglos, un puntero
apunta a la posición del pivote menos uno. Es decir,
izquierdo y un puntero derecho.
se ubica a la izquierda del pivote.
Para realizar una explicación clara sobre el
Para poner en funcionamiento al algoritmo, lo que
algoritmo, abordaré estas herramientas de la forma
se hace es que ambos punteros empiecen a
más concisa y clara posible.
“caminar” posición por posición hacia el otro; es
Por pivote refiere a un elemento cualquiera del decir, acercarlos poco a poco. Sin embargo, para
arreglo en su estado inicial (desordenado), sobre el hacer que caminen se deben cumplir ciertas
cual se realizarán las comparaciones necesarias condiciones: para empezar, únicamente se mueve al
para que, reordenando el arreglo, todos los puntero izquierdo una y solo una posición por
elementos a su izquierda sean menores a él, y los iteración. Por cada movimiento que haga, apuntará
que se encuentren a su derecha, mayores a él. Esto a distintos elementos del arreglo. Lo que se debe
se podrá lograr gracias al uso de los dos punteros. hacer es verificar si el elemento al que se encuentra
Intentemos ver esto que acabo de explicar de una apuntando es mayor que el valor de nuestro pivote;
manera más gráfica: en caso de que el valor del elemento apuntado sea
menor que nuestro pivote, no hacemos nada,
seguimos moviendo al puntero izquierdo una
posición a la derecha por iteración. Tal como se
ilustra en el siguiente gráfico:

1
 Universidad Nacional de Lanús – 2024 – Programación Concurrente

Para continuar desplazamos al puntero izquierdo

una posición a la derecha, buscando nuevamente un
elemento mayor a nuestro pivote.

Debido a que 5 es menor que el valor de nuestro

pivote (7) hacemos avanzar al puntero izquierdo.
Ahora nos encontramos con que nuestro puntero
En este caso el puntero izquierdo apunta al 9, un
izquierdo apunta a un elemento mayor a nuestro
elemento mayor a nuestro pivote. Nos detenemos y
pivote. Es tal como mencionamos antes, así que
pasamos al puntero derecho, en busca de un
ahora debemos detenernos y hacer retroceder al
elemento menor al pivote. El 8 no es menor a 7, así
puntero derecho. El mismo debe retroceder hasta
que desplazamos el puntero derecho una posición a
apuntar a un elemento menor a nuestro pivote.
la izquierda.
Como puede verse, nuestro puntero derecho ya está
apuntando a un elemento menor a nuestro pivote.
Es en este caso en que no debemos desplazar al
puntero derecho hacia la izquierda, sino realizar un
intercambio de valores. Dado que se cumplió la
condición de que el puntero izquierdo apunte a un
elemento mayor al pivote, y que el puntero derecho
apunte a un elemento menor al pivote,
intercambiamos los valores de ambos punteros. Es
decir, el 8 pasa al lugar del 1, y el 1 al lugar del 8.
Tal como se muestra en la siguiente ilustración.

Llegados a este punto, nuestros dos punteros se han

conocido. Es decir, ambos, se encuentran
apuntando a la misma posición del arreglo. Cuando
esto ocurre debemos finalizar todas las
comparaciones pasadas e intercambiar el valor del
pivote por el de nuestros punteros. O sea,
realizamos un último intercambio de valores entre
nuestro pivote y puntero izquierdo (o derecho, la
elección da igual en este punto).

2
 Universidad Nacional de Lanús – 2024 – Programación Concurrente

algoritmo sobre el subarreglo izquierdo, y el

segundo hilo sobre el derecho. Tal como puede
verse en el siguiente método.

Posteriormente, ambos hilos inician sus respectivas

tareas: aplicar QuickSort a la parte del subarreglo
Ahora, nuestro pivote se encuentra en su posición que le tocó a cada uno.
correcta en el arreglo. Todos los elementos a su
izquierda son menores a él, y todos los que se Tal como mencioné antes, es una implementación
encuentran a su derecha mayores a él. Para que únicamente utiliza dos hilos en toda su
continuar con el algoritmo, QuickSort lo que hace ejecución para ordenar. Su escritura y lógica es
es utilizar la recursión para volver a realizar todos sencilla, ya que en todo el algoritmo la
los pasos que hicimos hasta ahora sobre los dos concurrencia únicamente aparece en su primera
nuevos subarreglos que han aparecido. llamada. En todas las llamadas recursivas
posteriores cada hilo opera QuickSort como si fuera
{5, 1} es el primer subarreglo que aparece y {8, 9} secuencial. Con la clara diferencia de la
es el segundo. Es decir, se consideran subarreglos implementación secuencial que ahora tenemos dos
aquellos elementos que hayan quedado a la hilos ordenando sus respectivos subarreglos a la
izquierda y derecha del pivote. vez.
Para ordenarlo completamente, simplemente se Para mejor entendimiento sobre cómo cada hilo
aplica QuickSort (los pasos que realizamos hasta aplica QuickSort a sus subarreglos
ahora) sobre esos subarreglos, hasta llegar a un correspondientes, a continuación muestro los
punto en que los subarreglos tengan un tamaño 1, métodos que se encargan de realizar dicho
es decir, solo quede un elemento. Es entonces algoritmo.
cuando las llamadas recursivas finalizan y el
retorno de todas ellas nos dejan nuestro arreglo Método principal donde se generan las llamadas
inicial completamente ordenado. recursivas. Se hace uso de particionarArray() para
que coloque a nuestro pivote en su posición
correcta, colocando todos los elementos menores a
él a su izquierda y los mayores a su derecha.
Posteriormente se utiliza la recursión para aplicar
2. IMPLEMENTACIÓN CONCURRENTE QuickSort a los dos subarreglos obtenidos.

Para realizar la implementación concurrente, utilicé

dos hilos en la primera partición del arreglo inicial.
Es decir, los dos primeros hilos se generan una vez Método encargado de la partición del array (uso de
generamos los dos primeros subarreglos con la puntero izquierdo, derecho y pivote). El pivote se
primer llamada a QuickSort. Es en ese entonces selecciona como el último elemento del arreglo:
donde, con ambos hilos instanciados, se les indica
que deben aplicar QuickSort a sus correspondientes
subarreglos; el primer hilo se encarga de aplicar el

3
 Universidad Nacional de Lanús – 2024 – Programación Concurrente

2. COMPARATIVA Y DESEMPEÑO
Para comparar la eficiencia de la implementación
concurrente versus la secuencial, creé cinco
escenarios de prueba que demuestran no solo las
fortalezas de la concurrencia, sino también sus
grandes debilidades.
Para hacer esta prueba se utilizó el siguiente
volumen de elementos: 1.000.000 (un millón),
Método encargado de intercambiar los valores del 500.000 (quinientos mil), 100.000 (cien mil), 1.000
arreglo en caso de que se cumplan las condiciones (mil) y 10.
de los punteros: En términos de hardware, se utilizó un CPU Ryzen
3 3200g de 4 núcleos.
Para los datos de prueba, se generaron números
aleatorios del -1000 al 1000.

Comparativa de ambos algoritmos

Algoritmo 1.000.000 500.000 100.000 1000 10 elementos
elementos elementos elementos elementos
QuickSort 1.438 691 37 44.600 500
secuencial milisegundos milisegundos milisegundos nanosegundos nanosegundos
QuickSort 686 252 10 210.800 252.200
concurrente milisegundos milisegundos milisegundos nanosegundos nanosegundos

tiempo contra la secuencial, tardando 300 veces

4. CONCLUSIÓN
más.
Estos resultados se deben a dos motivos. Uno de
Tras haber visto la comparativa entre QuickSort ellos es el hecho del tiempo de inicialización de los
secuencial y QuickSort concurrente, queda en hilos; para pocos elementos, en lo que la
evidencia no solo la fortaleza de la concurrencia, implementación concurrente inicia los hilos con sus
siendo capaz de ordenar un millón de elementos en correspondientes tareas, la versión secuencial ya
menos de la mitad de tiempo que su versión está ordenando todo su arreglo finalizando mucho
secuencial, sino también su gran flaqueza. La antes.
implementación concurrente decae en eficiencia a
El segundo motivo, y válido para el algoritmo sobre
medida que la cantidad total de elementos es cada
el cual se trata este informe, trata sobre el
vez menor. Siendo el ejemplo más extremo 10
comportamiento de QuickSort con los datos de
elementos, donde la versión concurrente perdió en
entrada. Para la versión concurrente, es muy

4
 Universidad Nacional de Lanús – 2024 – Programación Concurrente

importante que los datos de entrada sean lo más

variados posible. ¿Por qué? Bien, esto es así en
gran medida por la concurrencia. Al utilizar solo
dos hilos, es muy importante tener en cuenta la
carga de trabajo. Dado que tratamos con valores de
entrada aleatorios, por cada testeo que se hace, se
está poniendo a prueba la eficiencia del algoritmo
no solo por ser concurrente, sino también por como
se distribuye la carga de trabajo entre los dos hilos.
Esto último es, cuántos elementos debe ordenar
cada hilo.
Por la aleatoriedad, en la primer partición del
arreglo, pueden quedarnos a lo mejor 100.000 (cien
mil) elementos a la izquierda del pivote, y 900.000
(novecientos mil) a su derecha. Esto es un punto de
partida muy malo para nuestra versión concurrente,
ya que el 2do hilo realizará nueve veces el trabajo
del otro. Significa entonces que no podríamos
aprovechar la concurrencia al máximo.
Para esta versión concurrente de QuickSort lo
mejor que puede ocurrirle con los datos de entrada
es que cada hilo ordene la mitad del arreglo. Quiero
decir, que cada hilo obtenga una carga de trabajo lo
más aproximada posible a la mitad del tamaño del
arreglo, así puede aprovechar la concurrencia al REFERENCIAS
máximo.
John Marty. (2021). Quicksort Sort Algorithm in
Solo para dar prueba de esto último, QuickSort Java - Full Tutorial With Source.
concurrente llegó a darme resultados mucho peores [Link]
que su versión secuencial a la hora de ordenar sd1Ws
1.000.000 (un millón) de elementos. Esto es así ya
que la carga de trabajo, completamente aleatoria, Baeldung. (2024). Quicksort Algorithm
no era equitativa para cada hilo; llegué a obtener Implementation in Java.
tiempos de casi 2.000 (dos mil) milisegundos solo [Link]
porque el segundo o primer hilo debían de realizar
la gran mayoría del ordenamiento, mientras que el
restante ordenaba una pequeña cantidad del total de
elementos.

Podemos concluir entonces que, QuickSort en su

versión concurrente, es un muy poderoso algoritmo
de ordenamiento, llegando a obtener tiempos muy
buenos respecto a su versión secuencial a la hora de
ordenar muchísimos elementos. Sin embargo, no
hay que perder de vista su flaqueza frente a la carga
desequilibrada de trabajo y la poca cantidad de
elementos a ordenar. Aunque esto último es algo
que afecta a casi todos los algoritmos de
ordenamiento concurrentes.