El ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n. Esta es la técnica de ordenamiento más rápida conocida. Fue desarrollada por C. Antony R. Hoare en 1960. El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos).
Los pasos del algoritmos son los siguientes:
- Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote. Para elegir el pivote podemos obtener el promedio de los datos y así obtener un valor que este muy cerca de uno de los elementos a ordenar y elegirlo como pivote.
- Resituar los demás elementos de la lista a cada lado del pivote, de manera que en el lado izquierdo queden todos los menores que él, y en el lado derecho los mayores. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
- La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
- Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados. Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.
- En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n log n).
- En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de 0(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas.
- En el caso promedio, el ordenamiento es O(n·log n).
Ahora un ejemplo de la ejecución del algoritmo:
5 86 68 73 11 17 1 74 34 3
Primer paso elegir un pivote:
5 86 68 73 11 17 1 74 34 3
Segundo paso mover los elementos menores al pivote a la izquierda y los mayores a la derecha:
5 1 3 11 17 34 86 68 73 74
Después elegimos un elemento pivote de cada lado del pivote original :
Del lado izquierdo elegimos el 5 y del lado derecho el 74 y movemos los números menores a 5 y 74 a su izquierda y los mayores a su derecha:
5 1 3 11 17 34 86 68 73 74
1 3 5 11 17 34 68 73 74 86
El arreglo quedaría de esta forma: 1 3 5 11 17 34 68 73 74 86
Excelente, ahora le entendi al quicksort, pero para ayudarte un poco mas he aqui un pseudocodigo a ver si te gusta.
ResponderEliminarint colocar(int *v, int b, int t)
{
int i;
int pivote, valor_pivote;
int temp;
pivote = b;
valor_pivote = v[pivote];
for (i=b+1; i<=t; i++){
if (v[i] < valor_pivote){
pivote++;
temp=v[i];
v[i]=v[pivote];
v[pivote]=temp;
}
}
temp=v[b];
v[b]=v[pivote];
v[pivote]=temp;
return pivote;
}
void Quicksort(int* v, int b, int t)
{
int pivote;
if(b < t){
pivote=colocar(v, b, t);
Quicksort(v, b, pivote-1);
Quicksort(v, pivote+1, t);
}
}
ammm yo tengo una duda que paso con el 11?
ResponderEliminarya esta arreglado el problema con el 11 ;)
ResponderEliminary gracias por el pseudocódigo (Y)
Me parece excelente, las gráficas fueron un muy buen detalle al igual que el arreglo que nos muestras.
ResponderEliminarPodríamos probar el orden de ejecución en el mejor caso de la siguiente manera:
Vamos a suponer que el número total de elementos a ordenar es potencia de dos, es decir, n = 2k. de aquí podemos ver que k = log2(n), donde k es el número de divisiones que realizará el algoritmo.
En la primera fase del algoritmo habrán n comparaciones, en la segunda fase el algoritmo creará dos sublistas aproximadamente de tamaño n/2. El número total de comparaciones de estas dos sublistas es: 2(n/2) = n. En la tercera fase el algoritmo procesará 4 sublistas más, por tanto el número total de comparaciones en esta fase es 4(n/4) = n.
En conclusión, el número total de comparaciones que hace el algoritmo es:
n + n + n + ..... + n = kn, donde k = log2(n), por tanto el tiempo de ejecución del algoritmo en el mejor caso es O(n.log2n)
que es en resúmen todo lo que nos demuestras
muy bien (Y)
Muy bien con la grafica queda clarisimo basicamente selecciona el pivote y ordenas todos los numeros que esten atras de el si son mayores los pasa al otro lado donde el proximo pivote hara lo mismo de esta forma se van ordenando por secciones talvez lo unico que faltaria para estar todo claro podrian ser algunos ejemplos en la vida diaria lo que se me ocurre seria algo asi como ordenar por estaturas pero me gustaria un ejemplo mas relacionado con ingenieria :D saludos..
ResponderEliminar