Método Quick Sort
¿Qué es?
Quicksort es un algoritmo de ordenación rápida que funciona dividiendo una gran matriz de datos en submatrices más pequeñas. Esto implica que cada iteración divide la entrada en dos componentes, los ordena y luego los recombina. Esta técnica es muy eficiente para grandes conjuntos de datos, ya que su complejidad promedio y óptima es de O(n*logn).
Quicksort puede tener algunas desventajas, pero funciona bien en la práctica y puede superar a otros algoritmos de ordenación en velocidad y eficiencia de espacio. Quicksort fue creado por Tony Hoare en 1961 y sigue siendo uno de los algoritmos de ordenación de propósito general más rápidos y eficaces disponibles en la actualidad.
¿Cómo funciona Quicksort?
Quicksort funciona ordenando de forma recursiva las sublistas a cada lado de un pivote determinado y desplazando dinámicamente los elementos dentro de la lista alrededor de ese pivote.
Como resultado, el método Quicksort se puede resumir en tres pasos:
Seleccionar: seleccionar un elemento.
Dividir: dividir el conjunto de problemas, mover las partes más pequeñas a la izquierda del pivote y los elementos más grandes a la derecha.
Repetir y combinar: repita los pasos y combine las matrices que se han ordenado previamente.
Veamos un ejemplo para comprender mejor el algoritmo Quicksort. En este ejemplo, la siguiente matriz contiene valores sin ordenar, que ordenaremos con Quicksort.
Ejemplo en Lenguaje C:
#include <stdio.h>
// Función para intercambiar dos elementos
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
/*
Esta función toma el último elemento como pivote,
coloca el pivote en su posición correcta en la matriz ordenada,
y coloca todos los elementos más pequeños (que el pivote) a la izquierda
y todos los elementos mayores a la derecha del pivote
*/
int partition (int arr[], int low, int high) {
int pivot = arr[high]; // Pivote
int i = (low - 1); // Índice del elemento más pequeño
for (int j = low; j <= high - 1; j++) {
// Si el elemento actual es más pequeño o igual que el pivote
if (arr[j] <= pivot) {
i++; // Incrementa el índice del elemento más pequeño
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
/*
La función principal que implementa QuickSort
arr[] --> Matriz a ordenar,
low --> Índice de inicio,
high --> Índice de fin
*/
void quickSort(int arr[], int low, int high) {
if (low < high) {
/* pi es el índice de partición,
arr[pi] está ahora en el lugar correcto */
int pi = partition(arr, low, high);
// Ordenar elementos por separado antes y después de la partición
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Función para imprimir una matriz
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Programa de prueba
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Matriz original:\n");
printArray(arr, n);
quickSort(arr, 0, n - 1);
printf("Matriz ordenada:\n");
printArray(arr, n);
return 0;
}