Merge y Quick Sort: conozca cuál es el mejor algoritmo

Después de comprender mejor la complejidad de los algoritmos, debemos analizar y comprender las diferencias para considerar la mejor opción entre dos algoritmos igualmente complejos. Este es el caso de Merge Sort y Quick Sort.

En los artículos que se refieren a la implementación de los dos algoritmos en cuestión, notamos que ambos tienen su complejidad en O(N lg N). Pero, ¿cuestionamos la eficiencia de QuickSort en todos los escenarios? ¿Siempre funciona en O(N lg N)? Hagamos un análisis.

Recordando cómo funciona QuickSort, debemos elegir un elemento pivote para asegurar su ubicación correcta en la lista y luego revisar todos los elementos más pequeños a la izquierda y los elementos más grandes a la derecha (según el orden deseado).

Ejecutando esto recursivamente tendremos una lista correctamente ordenada.

Pero, ¿cuál sería el peor de los casos?

Construyamos sobre nuestra implementación de QuickSort, en el que siempre elegimos el elemento en el extremo inferior como pivote.

Imagine que recibimos una lista ya ordenada como entrada al algoritmo. Tenga en cuenta el siguiente comportamiento:

Notamos que en cada elección de pivote recorremos el resto de la lista en busca de su posición real. Eso nos recuerda algo, con cada iteración de elección, repasamos la lista, que nos parece un comportamiento cuadrático. Por lo tanto, en el peor de los casos, QuickSort se comporta como O(N²).

Entonces, ¿consideramos que QuickSort siempre es peor que MergeSort? ¡No necesariamente! Vimos que el peor de los casos se debía a la elección del pivote. En este mismo escenario, si elegimos el pivote como elemento central de la lista, en cada iteración ingresamos el mejor caso del algoritmo, que se ejecuta en O(N lg N) así como en el caso promedio. Y ahora nos damos cuenta de que es muy poco probable que caigamos en el peor de los casos de QuickSort.

Por lo tanto, debemos evaluar y considerar los más diversos factores y requisitos para elegir el algoritmo que mejor nos sirva.

Otras limitaciones

Ahora supongamos que estamos en un proyecto con escasos recursos de memoria volátil, lo que hace que cuidar el uso de la memoria sea un requisito no funcional (requisitos relacionados con el rendimiento, la disponibilidad, el mantenimiento y los recursos del proyecto). ¿Qué algoritmo elegir?

Hemos visto que MergeSort crea una lista temporal del mismo tamaño que la original, duplicando así la asignación de memoria. Quizás esta no era la mejor solución para este escenario, ¿no crees?

Conclusión

Hemos visto que cuando se trata de algoritmos con la misma complejidad en la mayoría de los escenarios, debemos evaluar otros factores para elegir la solución que mejor se adapte al contexto en el que nos insertaremos.

Y así finalizamos esta serie de artículos mostrando la importancia de estudiar algoritmos y cómo pueden afectar a nuestros proyectos. Espero que podamos vernos pronto, ¡hasta luego!

Brendo Rodrigo Souza de Matos

Ingeniero de Software apasionado por lo que hace, amante de los nuevos retos y sediento de conocimiento. Actualmente soy Ingeniero de Software de Plataformas en Méliuz (B3: CASH3) y estoy realizando una Maestría en Ciencias de la Computación en la Universidad Federal de Amazonas.

Este articulo fue adecuado para Alura Latam por: Wilfredo Rojas