Quick sort (Rápido)
Este es un algoritmo de ordenación basado en el paradigma de divide y vencerás. A diferencia de otros algoritmos como MergeSort, que divide los datos en mitades iguales, Quicksort utiliza un pivote para dividir el arreglo en subarreglos, reordenando los elementos de manera que todos los menores que el pivote estén a su izquierda y los mayores a su derecha. Este proceso se repite recursivamente hasta que todos los elementos estén ordenados.
Algunas de las características más importantes de este algoritmo son:
- Divide y vencerás: Aquí se aplica el concepto de dividir una tarea grande en partes más pequeñas, lo que facilita el ordenamiento.
- Ordenamiento en su lugar (in-place): Este algoritmo no requiere memoria adicional significativa, lo que lo hace eficiente en términos de uso de espacio.
- Complejidad temporal: En el mejor y promedio de los casos, el algoritmo tiene una complejidad de O(n log n). Sin embargo, en el peor de los casos, cuando el pivote se elige mal, puede degenerar a O(n²).
¿Cómo funciona?
Veamos, son pasos simples pero claros:
- Elección del pivote: El primer paso en este algoritmo es seleccionar un elemento como pivote. Este pivote puede ser el primer elemento, el último, un elemento aleatorio o incluso el valor mediano de un grupo de elementos. La elección del pivote es crucial, ya que determina cómo se dividirá el arreglo.
- Partición del arreglo: Una vez seleccionado el pivote, Quicksort reorganiza el arreglo de manera que todos los elementos menores que el pivote se coloquen a su izquierda y los mayores a su derecha. Esto crea dos subarreglos alrededor del pivote.
- Aplicación recursiva: El algoritmo se aplica recursivamente a los dos subarreglos generados. Este proceso de partición y ordenamiento recursivo continúa hasta que los subarreglos son lo suficientemente pequeños como para estar ordenados.
- Combinación implícita: A diferencia de otros algoritmos como MergeSort, Quicksort no tiene una etapa de combinación explícita, ya que los elementos se van ordenando en su lugar durante el proceso de partición.
¿En qué te beneficia Quicksort y qué problemas puedes encontrar con su uso?
Quick sort es un algoritmo preferido por muchos programadores por varias razones:
- Eficiencia promedio: En la mayoría de los casos, Quick sort es muy eficiente, con una complejidad de O(n log n), lo que lo hace ideal para ordenar grandes conjuntos de datos.
- Uso eficiente de memoria: Al ser un algoritmo que se ejecuta in-place, Quick sort no requiere espacio adicional significativo, lo que lo hace más eficiente en términos de uso de memoria en comparación con algoritmos como MergeSort.
- Velocidad en la práctica: En muchos escenarios, Quick sort tiende a ser más rápido que otros algoritmos de ordenación, especialmente cuando se implementa con una buena estrategia para elegir el pivote.
- Facilidad de implementación: La implementación de Quicksort es relativamente simple y directa, lo que lo hace fácil de entender y de adaptar a diversos lenguajes de programación.
Quicksort también tiene algunas desventajas que vale la pena mencionar:
- Sensibilidad al pivote: La eficiencia de Quicksort depende en gran medida de la elección del pivote. Si el pivote se elige mal, especialmente en casos extremos como cuando el arreglo ya está ordenado o casi ordenado, la eficiencia puede degradarse a O(n²).
- Inestabilidad: Quicksort no es estable en su implementación básica, lo que significa que no necesariamente conserva el orden relativo de los elementos con claves iguales.
- Peor caso de complejidad: Aunque en promedio Quick sort tiene una complejidad de O(n log n), en el peor de los casos puede degenerar a O(n²), lo que lo hace menos deseable en situaciones donde se requiere garantizar tiempos de ejecución consistentemente buenos.
Ejemplo:
#include<iostream>
#include<conio.h>
#include<iomanip>
using namespace std;
void quicksort(double [20],int, int);
void escribir(double [20],int );
int main() {
int i,nro; double B[20];
cout<<"ingrese la dimension del arreglo"<<endl<<endl;
cin>>nro; cout<<"ingrese elementos del arreglo"<<endl<<endl;
for(i=0;i<nro;i++) { cout<<"B["<<i<<"]= ";
cin>>B[i]; } cout<<"ARREGLO ORIGINAL"<<endl<<endl;
for(i=0;i<nro;i++) { cout<<B[i]<<setw(5);
}
quicksort(B,0,nro-1);
escribir(B,nro); getch();
//delete B; return 0;
}
void quicksort(double A[20],int primero,int ultimo)
{ int central,i,j;
double pivote;
central=(primero+ultimo)/2;
pivote=A[central]; i=primero;
j=ultimo;
do { while(A[i]<pivote) i++;
while(A[j]>pivote) j--;
if(i<=j) { double temp;
temp=A[i];
A[i]=A[j];
/*intercambia A[i] con A[j] */
A[j]=temp;
i++; j--;
}
}
while(i<=j);
if(primero<j) quicksort(A,primero,j); /*mismo proceso con sublista izquierda*/ if(i<ultimo) quicksort(A,i,ultimo); /*mismo proceso con sublista derecha*/ }
void escribir(double A[20], int n) { int i;
cout<<endl<<"ARREGLO ORDENADO POR METODO DE QUICKSORT "<<endl<<endl;
for(i=0;i<n;i++)
{ cout<<A[i]<<setw(5);
} cout<<endl<<endl;
}