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'
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:
- 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.
- 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.
- 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.
- 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:
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».
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.
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:
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.
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.
Dividir la lista en dos sublistas utilizando el índice medio como punto de división.
Ordenar recursivamente cada sublista utilizando el mismo método.
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:
- 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.
- 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.
- 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.
- 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
| Algoritmo | Complejidad temporal | Complejidad espacial | In-place |
|---|---|---|---|
| Heapsort | O(n * log n) | O(n) | No |
| Mergesort | O(n * log n) | O(n) | No |
| Quicksort | O(n * log n) | O(1) | Sí |
- 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.
| Algoritmo | Cuando utilizar |
|---|---|
| Heapsort | Cuando se necesita ordenar grandes conjuntos de datos formados por colecciones pequeñas. En casos donde no importa el orden relativo de los elementos. |
| Mergesort | Cuando 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). |
| Quicksort | Cuando 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. |
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.
Ordenar 1.000 Arrays de 100.000 enteros.
Ordenar 10.000 Arrays de 10.000 enteros.
Ordenar 100.000 Arrays de 1.000 enteros.
Ordenar un millón de Arrays de 100 enteros.
Ordenar 10 millones de Arrays de 10 enteros.
Ordenar 10 Arrays de 10 millones de enteros.
Ordenar 1 Array de 100 millones de enteros.
Ordenar 1 Array de 300 millones de enteros.
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í.
