Quicksort vs Mergesort vs Heapsort

Tabla de contenidos

Antes de empezar a ver en detalle los mejores algoritmos de ordenación, veamos una primera forma de clasificar este tipo de algoritmos.

Algoritmos 'in-place' y algoritmos 'no in-place'

Un algoritmo «no in-place» es un algoritmo que no puede realizar una operación sin necesidad de espacio adicional. Esto significa que el algoritmo requiere algún tipo de estructura de datos adicional, como una lista o una matriz, y así almacenar los datos mientras los procesa. Por ejemplo, si se tiene una lista de números y se quiere ordenar utilizando un algoritmo «no in-place», se necesitaría una lista adicional para almacenar los números mientras se van ordenando. Esto se debe a que el algoritmo no puede realizar la operación de ordenación sin modificar los datos originales y, por lo tanto, necesita un lugar adicional donde almacenar los datos mientras los procesa. En cambio, un algoritmo «in-place» es un algoritmo que puede realizar una operación sin necesidad de espacio adicional. Esto significa que el algoritmo puede procesar los datos directamente en el lugar donde se almacenan, sin necesidad de utilizar una estructura de datos adicional. Los algoritmos «in-place» son más eficientes en términos de espacio que los algoritmos «no in-place», ya que no requieren espacio adicional para realizar la operación. Sin embargo, algunos algoritmos «no in-place» pueden ser más eficientes en términos de tiempo o pueden tener otras ventajas que los hagan más adecuados para ciertas tareas. Al elegir un algoritmo para una tarea específica, es importante tener en cuenta si se necesita un algoritmo «in-place» o «no in-place» y considerar cuál de ellos es más adecuado para la tarea en cuestión.

Algoritmo Quicksort

Quicksort es un algoritmo de ordenación que fue desarrollado por Tony Hoare en 1959. Hoare es un informático y matemático británico conocido por sus importantes contribuciones a la informática y la teoría de la información. Entre sus muchos logros, Hoare es conocido por haber desarrollado Quicksort, uno de los algoritmos de ordenación más utilizados y eficientes en la actualidad. Además, Hoare también es conocido por haber inventado el algoritmo de búsqueda binaria y por haber contribuido al desarrollo del lenguaje de programación Algol.

El algoritmo funciona seleccionando un elemento del conjunto de datos llamado «pivote» y dividiendo el conjunto de datos en dos subconjuntos basándose en si los elementos son mayores o menores que el pivote. A continuación, se ordenan de forma recursiva ambos subconjuntos utilizando el mismo proceso, hasta que todos los elementos estén ordenados.

El proceso de quicksort se puede resumir en los siguientes pasos:

  1. Seleccionar un pivote: El pivote es un elemento del conjunto de datos que se utiliza como referencia para dividir el conjunto de datos en dos subconjuntos. A menudo, se elige el elemento central del conjunto de datos como pivote, aunque también se pueden utilizar otros métodos para seleccionar el pivote.
  2. Dividir el conjunto de datos: Una vez seleccionado el pivote, se dividen los elementos del conjunto de datos en dos subconjuntos basándose en si son mayores o menores que el pivote. Los elementos mayores se colocan en un subconjunto y los elementos menores se colocan en otro subconjunto.
  3. Ordenar recursivamente cada subconjunto: A continuación, se aplica el mismo proceso de forma recursiva a cada subconjunto, dividiéndolos en dos subconjuntos más pequeños y ordenándolos hasta que todos los elementos estén ordenados.
  4. Combinar los subconjuntos: Una vez que todos los subconjuntos están ordenados, se combinan en un solo conjunto ordenado.

Quicksort es un algoritmo in-place

Quicksort es un algoritmo «in-place», lo que significa que no requiere espacio adicional para ordenar los datos. Además, suele tener un rendimiento excepcional en la mayoría de los casos, con un tiempo de ejecución de O(n log n) en el caso ideal y O(n^2) en el peor caso.

Es especialmente adecuado en entornos con restricciones de espacio y en situaciones en las que se necesita un algoritmo rápido y eficiente para ordenar los datos. Sin embargo, es importante tener en cuenta que quicksort no es un algoritmo estable y que puede tener un rendimiento menos bueno en casos especiales, como cuando el pivote seleccionado es muchas veces el elemento más pequeño o más grande del conjunto de datos. En estos casos, puede ser más adecuado utilizar un algoritmo de ordenación diferente, como heapsort o mergesort. Al elegir un algoritmo para una tarea específica, es importante tener en cuenta las características específicas del conjunto de datos que se está ordenando y el contexto en el que se está utilizando.

Si te interesa el tema, te dejo el enlace a un vídeo de mi canal de YouTube donde explico con más detalle el funcionamiento del algoritmo.

Implementación de Quicksort en JAVA

				
					public static void quicksort(int A[], int izq, int der) {
  int pivote = A[izq];    // tomamos primer elemento como pivote
  int i = izq;     	    // i realiza la búsqueda de izquierda a derecha
  int j = der;     	    // j realiza la búsqueda de derecha a izquierda
  int aux;
 
  while(i < j){          // mientras no se crucen las búsquedas                              
 	while(A[i] <= pivote && i < j) i++;   // busca elemento mayor que pivote
 	while(A[j] > pivote) j--;       	   // busca elemento menor que pivote
 	if (i < j) {                    	   // si no se han cruzado                 	 
        aux  = A[i];                      // los intercambia
        A[i] = A[j];
        A[j] = aux;
 	}
   }   
   A[izq] = A[j];  	// se coloca el pivote en su lugar de forma que tendremos  
   A[j]   = pivote;  	// los menores a su izquierda y los mayores a su derecha   
   if(izq < j-1) quicksort(A, izq, j-1);      	// ordenamos subarray izquierdo
   if(j+1 < der) quicksort(A, j+1, der);      	// ordenamos subarray derecho   
}

				
			

Algoritmo Mergesort

Mergesort es un algoritmo de ordenación que fue desarrollado por John von Neumann en 1945. Von Neumann fue un matemático, físico y científico informático estadounidense que es considerado uno de los padres de la informática moderna. Entre sus muchos logros, von Neumann es conocido por haber contribuido al desarrollo de la teoría de la información, el cálculo de la capacidad de canal de información y el diseño de la arquitectura de la computadora moderna. Además, von Neumann también fue uno de los primeros en utilizar el término «algoritmo» para referirse a un método matemático o computarizado para resolver un problema.

Mergesort es uno de los algoritmos de ordenación más utilizados y es ampliamente conocido por su rendimiento y eficiencia. Aunque von Neumann es el inventor de mergesort, el algoritmo ha sido modificado y mejorado por muchos otros investigadores a lo largo de los años. Hoy en día, mergesort sigue siendo uno de los algoritmos de ordenación más utilizados.

El proceso de mergesort se puede resumir en los siguientes pasos:

  1. Dividir el conjunto de datos: El primer paso es dividir el conjunto de datos en subconjuntos más pequeños hasta que cada subconjunto solo tenga un elemento. Estos subconjuntos se conocen como «sublistas ordenadas».

  2. Ordenar y combinar las sublistas: A continuación, se comparan dos sublistas ordenadas y se combinan en una sola sublista ordenada. Este proceso se repite hasta que todas las sublistas hayan sido combinadas en una sola lista ordenada.

  3. Combinar los subconjuntos: Una vez que todas las sublistas están ordenadas, se combinan en un solo conjunto ordenado.

Mergesort es un algoritmo «no in-place», lo que significa que requiere espacio adicional para ordenar los datos. Además, tiene un tiempo de ejecución de O(n log n) en el caso ideal y en el peor caso. Además, mergesort es un algoritmo estable, lo que puede ser importante en algunos casos en los que se necesita mantener el orden relativo de los elementos con igual valor.

El método QuickSort divide la estructura en dos y ordena cada mitad recursivamente. El caso del mergesort es el opuesto, en este método se unen dos estructuras ordenadas para formar una sola ordenada correctamente.

Implementación de Mergesort en JAVA

se puede implementar mergesort en Java siguiendo los siguientes pasos:

  1. Crear un método de ordenación recursivo que acepte como parámetros una lista y los índices inicial y final de la lista a ordenar.

  2. Verificar si el tamaño de la lista es menor o igual a 1. Si es así, la lista está ordenada y se puede devolver tal cual. Si no, se debe continuar con el proceso de ordenación.

  3. Dividir la lista en dos sublistas utilizando el índice medio como punto de división.

  4. Ordenar recursivamente cada sublista utilizando el mismo método.

  5. Una vez que ambas sublistas están ordenadas, combinarlas en una sola lista ordenada utilizando un proceso conocido como «fusionar».

A continuación se muestra un ejemplo de implementación de mergesort en Java:

				
					public void mergeSort(int[] list, int start, int end) {
    // Verificar si el tamaño de la lista es menor o igual a 1
    if (end - start <= 1) {
        return;
    }
    // Dividir la lista en dos sublistas
    int mid = (start + end) / 2;
    int[] left = Arrays.copyOfRange(list, start, mid);
    int[] right = Arrays.copyOfRange(list, mid, end);
    // Ordenar recursivamente cada sublista
    mergeSort(left, 0, left.length);
    mergeSort(right, 0, right.length);
    // Fusionar las sublistas ordenadas en una sola lista ordenada
    int i = 0;
    int j = 0;
    int k = start;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            list[k] = left[i];
            i++;
        } else {
            list[k] = right[j];
            j++;
        }
        k++;
    }
    // Copiar los elementos restantes de la sublista izquierda (si hay alguno)
    while (i < left.length) {
        list[k] = left[i];
        i++;
        k++;
    }
    // Copiar los elementos restantes de la sublista derecha (si hay alguno)
    while (j < right.length) {
        list[k] = right[j];
        j++;
        k++;
    }
}

				
			

En este ejemplo se ha utilizado una implementación «top-down» de mergesort, que comienza dividiendo la lista en sublistas y luego las ordena y las combina de forma recursiva. También existe una implementación «bottom-up» de mergesort, que comienza combinando sublistas de tamaño 1 y luego va combinando sublistas de tamaño cada vez mayor hasta obtener una sola lista ordenada. Ambas implementaciones tienen un tiempo de ejecución de O(n log n) en el caso ideal y en el peor caso.

Algoritmo HeapSort

Heapsort es un algoritmo de ordenación que fue desarrollado por J. W. J. Williams en 1964. Williams era un matemático y informático británico que trabajaba en el National Physical Laboratory (NPL) en Teddington, Inglaterra. Heapsort es un algoritmo de ordenación que se basa en el uso de una estructura de datos llamada «montículo» (en inglés, «heap») para ordenar un conjunto de datos.

Un montículo es un árbol binario completo en el que cada nodo cumple una de las dos propiedades siguientes:

  • Propiedad de montículo máximo: cada nodo es mayor o igual que sus hijos.
  • Propiedad de montículo mínimo: cada nodo es menor o igual que sus hijos.

Heapsort utiliza un montículo máximo para ordenar un conjunto de datos de forma ascendente o un montículo mínimo para ordenar un conjunto de datos de forma descendente. Un heap es un árbol binario en el que cada nodo cumple con la propiedad de «heap», es decir, el valor de cada nodo es mayor o igual que el valor de sus hijos. Por lo general, se implementan dos tipos de heap: max heap y min heap. En un max heap, el valor del nodo raíz es el mayor de todos los valores del heap, mientras que en un min heap, el valor del nodo raíz es el menor de todos los valores del heap.

El algoritmo heapsort comienza construyendo un heap con los elementos a ordenar. Luego, extrae el elemento máximo (en el caso de un max heap) o el elemento mínimo (en el caso de un min heap) y lo coloca al final de la lista de elementos ordenados. A continuación, vuelve a construir el heap con los elementos restantes y extrae el elemento máximo o mínimo, dependiendo del tipo de heap utilizado. Este proceso se repite hasta que se hayan extraído todos los elementos del heap y se haya completado la ordenación.

Implementación de HeapSort en JAVA

A continuación se explica cómo funciona el algoritmo Heapsort paso a paso:

  1. Construye el montículo a partir del conjunto de datos: el algoritmo comienza construyendo un montículo a partir del conjunto de datos. Un montículo es un árbol binario que cumple ciertas propiedades. En el caso de Heapsort, se utiliza un montículo máximo o un montículo mínimo. Un montículo máximo es un árbol en el que cada nodo es mayor o igual que sus hijos, mientras que un montículo mínimo es un árbol en el que cada nodo es menor o igual que sus hijos.
  2. Elimina el elemento máximo (o mínimo) del montículo y colócalo al final del conjunto de datos ordenado: una vez construido el montículo, el algoritmo elimina el elemento máximo (si se ha utilizado un montículo máximo) o el elemento mínimo (si se ha utilizado un montículo mínimo) y lo coloca al final del conjunto de datos ordenado.
  3. Vuelve a construir el montículo: después de eliminar el elemento máximo (o mínimo), el algoritmo vuelve a construir el montículo a partir de los elementos restantes.
  4. Repite los pasos 2 y 3 hasta que todos los elementos estén ordenados. 

Ejemplo en JAVA

En el siguiente ejemplo se ha implementado Heapsort en JAVA con un montículo máximo, lo que significa que el algoritmo ordenará el conjunto de datos de forma ascendente.

  • La función heapSort( ) es la función principal del algoritmo y se encarga de realizar el proceso iterativo de eliminar el elemento máximo del montículo y volver a construirlo hasta que todos los elementos estén ordenados.
  • La función buildMaxHeap( ) se encarga de construir el montículo máximo a partir del conjunto de datos. Recorre todos los nodos que no son hojas y ajusta el montículo con la función adjustHeap().
  • La función adjustHeap( ) se encarga de hacer «descender» un elemento del montículo hasta su posición correcta. Calcula el índice del hijo izquierdo y derecho del nodo y compara el mayor de los dos hijos con el nodo. Si el hijo mayor es mayor que el nodo, intercambia los dos elementos y llama recursivamente a adjustHeap() con el hijo intercambiado como raíz del montículo.
  • La función swap( ) se encarga de intercambiar dos elementos del array.
				
					public void heapSort(int[] array) {
    // Creamos el montículo
    buildMaxHeap(array);
    // Recorremos el array desde el final hasta el principio
    for (int i = array.length - 1; i > 0; i--) {
        // Intercambiamos el elemento máximo con el último elemento
        swap(array, 0, i);
        // Ajustamos el montículo
        adjustHeap(array, 0, i);
    }
}
private void buildMaxHeap(int[] array) {
    // Calculamos el índice del primer elemento que no es hoja
    int firstNonLeaf = (array.length - 1) / 2;
    // Recorremos todos los nodos que no son hojas
    for (int i = firstNonLeaf; i >= 0; i--) {
        // Ajustamos el montículo
        adjustHeap(array, i, array.length);
    }
}
private void adjustHeap(int[] array, int root, int heapSize) {
    // Calculamos el índice del hijo izquierdo
    int leftChild = 2 * root + 1;
    // Si el hijo izquierdo es menor que heapSize, entonces el nodo tiene hijos
    if (leftChild < heapSize) {
        // Calculamos el índice del hijo derecho
        int rightChild = 2 * root + 2;
        // Si el hijo derecho es menor que heapSize, entonces el nodo tiene dos hijos
        if (rightChild < heapSize) {
            // Si el hijo derecho es mayor que el hijo izquierdo, entonces el mayor de los dos hijos es el derecho
            if (array[rightChild] > array[leftChild]) {
                leftChild = rightChild;
            }
        }
        // Si el hijo mayor es mayor que el nodo, entonces intercambiamos los dos elementos
        if (array[leftChild] > array[root]) {
            swap(array, root, leftChild);
            // Ajustamos el montículo desde el hijo intercambiado
            adjustHeap(array, leftChild, heapSize);
        }
    }
}
private void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

				
			

El algoritmo heapsort tiene un tiempo de ejecución de O(n log n), lo que lo convierte en uno de los algoritmos de ordenamiento más rápidos que existen.

Una de las ventajas de heapsort es que es muy eficiente para ordenar grandes cantidades de datos. Por un lado, es un algoritmo «no in-place», lo que significa que requiere un espacio adicional para almacenar los elementos mientras se realiza la ordenación. Además, heapsort no es tan rápido en determinadas circuntancias, y pueden haber mejores alternativas, como quicksort o mergesort.

Qué algoritmo es mejor?

Es difícil decir cuál de estos algoritmos es «mejor» en general, ya que depende de las características específicas del conjunto de datos que se esté ordenando y del contexto en el que se esté utilizando. En general, quicksort suele ser más rápido que mergesort en la mayoría de los casos, especialmente para conjuntos de datos de tamaño mediano a grande. Sin embargo, hay algunos casos en los que mergesort puede ser más adecuado.

Uno de los principales puntos a favor de quicksort es que es un algoritmo «in-place», lo que significa que no requiere espacio adicional para ordenar los datos. Esto puede ser importante en entornos con restricciones de espacio, como en sistemas embebidos o en plataformas móviles. Además, quicksort suele tener un rendimiento muy bueno en la mayoría de los casos, con un tiempo de ejecución de O(n log n) en el caso ideal y O(n^2) en el peor caso.

Por otro lado, mergesort es un algoritmo estable, lo que significa que mantiene el orden relativo de los elementos con igual valor. Esto puede ser importante en algunos casos. Sin embargo, mergesort puede tener un rendimiento ligeramente peor que quicksort en algunos casos debido a la necesidad de realizar copias adicionales de los datos durante el proceso de ordenación.

Por otro lado, heapsort es un algoritmo «no in-place», lo que significa que requiere espacio adicional para ordenar los datos. Además, aunque su tiempo de ejecución es también de O(n log n).

Heapsort vs Mergesort vs Quicksort

AlgoritmoComplejidad temporalComplejidad espacialIn-place
HeapsortO(n * log n)O(n)No
MergesortO(n * log n)O(n)No
QuicksortO(n * log n)O(1)
  • Complejidad temporal: se refiere al tiempo que tarda el algoritmo en ordenar un array de tamaño n.
  • Complejidad espacial: se refiere al espacio adicional que necesita el algoritmo para ordenar un array de tamaño n.
  • Estable: indica si el algoritmo mantiene el orden original de los elementos con el mismo valor en el resultado final.
  • In-place: indica si el algoritmo necesita un espacio adicional para ordenar un array.
Al elegir entre estos algoritmos, es importante tener en cuenta estas diferencias y considerar cuál de ellos es más adecuado para la tarea específica que se esté realizando. En la siguiente tabla, se indican algunas situaciones en las que cada algoritmo puede ser más adecuado:
AlgoritmoCuando utilizar
HeapsortCuando se necesita ordenar grandes conjuntos de datos  formados por colecciones pequeñas. En casos donde no importa el orden relativo de los elementos.
MergesortCuando se necesita un algoritmo estable que mantenga el orden relativo de los elementos con igual valor y tenga una coste temporal constante O(n * log n).
QuicksortCuando se necesita un algoritmo rápido y eficiente para ordenar conjuntos de datos de tamaño mediano a grande. Cuando se necesita un algoritmo «in-place» debido a restricciones de espacio.
Es importante tener en cuenta que esta tabla es solo una guía y que no existe un algoritmo de ordenación que sea «mejor» en todos los casos. Al elegir entre estos algoritmos, es importante tener en cuenta las características específicas del conjunto de datos que se está ordenando y el contexto en el que se está utilizando. Por ejemplo, si se está ordenando un conjunto de datos muy grande y se dispone de espacio para almacenar los datos mientras se ordenan, heapsort puede ser una buena opción debido a su eficiencia. Sin embargo, si se está trabajando con un conjunto de datos más pequeño y se necesita mantener el orden relativo de los elementos con igual valor, mergesort puede ser una mejor opción debido a su estabilidad.

Casos de prueba

Lo mejor para comparar el rendimiento de estos algoritmos es meternos en el barro y empezar a hacer todo tipo de pruebas con Arrays de distintos tamaños, para ello he realizado muchos tests de prueba con Arrays de enteros de muchos tamaños. Todos los elementos de los Arrays se han generado de forma completamente aleatoria.

Ordenar 100 Arrays de un millón de enteros.
1 s
Quicksort
1 s
Heapsort
1 s
Mergesort
Ordenar 1.000 Arrays de 100.000 enteros.
1 s
Quicksort
1 s
Heapsort
1 s
Mergesort
Ordenar 10.000 Arrays de 10.000 enteros.
1 s
Quicksort
1 s
Heapsort
1 s
Mergesort
Ordenar 100.000 Arrays de 1.000 enteros.
1 s
Quicksort
1 s
Heapsort
1 s
Mergesort
Ordenar un millón de Arrays de 100 enteros.
1 s
Quicksort
1 s
Heapsort
1 s
Mergesort
Ordenar 10 millones de Arrays de 10 enteros.
1 s
Quicksort
1 s
Heapsort
1 s
Mergesort
Ordenar 10 Arrays de 10 millones de enteros.
1 s
Quicksort
1 s
Heapsort
1 s
Mergesort
Ordenar 1 Array de 100 millones de enteros.
1 s
Quicksort
1 s
Heapsort
1 s
Mergesort
Ordenar 1 Array de 300 millones de enteros.
1 s
Quicksort
1 s
Heapsort
1 s
Mergesort

Como se puede observar, en prácticamente todas las pruebas quicksort ofrece un rendimiento superior en la mayoría de pruebas. Únicamente cuando se trata de Arrays muy pequeños (hasta 100 elementos), quicksort es superado ligeramente por Heapsort. Entonces, cómo se explican estas diferencias entre 3 algoritmos que teóricamente son iguales de eficientes?, mas si cabe, teniendo en cuenta que el peor caso de quicksort es mucho peor que los otros dos.

El secreto de Quicksort

¿Cómo puede ser tan bueno Quicksort respecto al resto, si los 3 tienen una complejidad temporal de O(n * log n)?

El secreto de Quicksort es que prácticamente no hace intercambios innecesarios. El intercambio de elementos en una colección es una operación que demanda muchos más recursos que una simple comparación. Heapsort y Mergesort hacen muchos intercambios, además de las comparaciones. Esto hace que su ejecución requiera más tiempo.

Con Heapsort, incluso si todos sus datos ya están ordenados, intercambiará el 100% de los elementos para ordenar.

Con Mergesort, es aún peor. Vas a escribir el 100% de los elementos en otra colección y tiene que volver a escribirla en la colección original, incluso si los datos ya están ordenados.

Con Quicksort no intercambias lo que no es necesario. Si sus datos están completamente ordenados, prácticamente no hay intercambios. Aunque se habla mucho sobre el peor de los casos O(n^2), una pequeña mejora en la elección del pivote, puede evitarlo. Además, es un caso altamente improbable sobre colecciones de medianas a grandes.

Lo que hace superior a Quicksort no es el peor de los casos, sino que aunque la complejidad temporal es la misma en el caso promedio, es mucho más eficiente. En el mejor de los casos, hace la misma cantidad de comparaciones, pero no intercambia casi nada. En el caso promedio, intercambia parte de los elementos, pero no todos los elementos, como en Heapsort y Mergesort. Esto es lo que le proporciona Quicksort esa ventaja. Menos intercambios, más velocidad. En general, quicksort suele ser la elección más común para ordenar conjuntos de datos de tamaño mediano a grande debido a su rendimiento. 

Sin embargo, en algunos casos específicos, heapsort o mergesort pueden ser opciones viables debido a sus características específicas. Al elegir entre estos algoritmos, es importante tener en cuenta las necesidades y restricciones específicas de la tarea que se esté realizando.

Espero que te haya gustado el artículo. Si tienes cualquier duda o aporte adicional estaré encantado de leerte en los comentarios. Gracias por haber llegado hasta aquí.

ÚLTIMAS PUBLICACIONES
Icono cookies
Icono cookies

Utilizamos cookies para asegurar que damos la mejor experiencia al usuario. Si continúa navegando, consideramos que acepta nuestro uso de Cookies. Puede obtener más información en nuestra política de Cookies

Utilizamos cookies para asegurar que damos la mejor experiencia al usuario. Si continúa navegando, consideramos que acepta nuestro uso de Cookies. Puede obtener más información en nuestra política de Cookies