QuickSort
¡Qué feo es el quicksort y cómo corre! :P
Si tenéis que realizar muchas operaciones de ordenación sobre arrays (o sobre le mismo array muchas veces, como es mi caso) Sin duda la recomendación es el QuickSort. Es el método de ordenación con mejor tiempo empírico (teóricamente, en el peor de los casos el orden del quicksort es cuadrático -n^2- pero esto solo ocurre cuando el array se encuentra ordenado en orden inverso…) dado que utiliza muy pocas operaciones de comparación e intercambio. Al principio es complicado de pillar, es engorroso de escribir, pero es una alegría verlo funcionar:
(La imagen la he tomado prestada de la wiki, pero por favor, no la consultéis, al menos en español, en este caso: no queda la cosa nada clara…)
Os dejo mi implementación del QuickSort en C para el proyecto… bueno, he cambiado los arrays para que estuviera algo más claro ;)
void quicksort(int individuos[M], int inicio, int fin){
int pivote, i, j, mitad;
bool hayCambio;
//caso base: si inicio>=fin hemos terminado con esta sección, no hacemos nada
if(inicio < fin){
pivote = individuos[inicio];
i = inicio+1;
j = fin;
hayCambio = true;
while(hayCambio){
while((individuos[i] >= pivote)&&(i < fin ))i++;
while((individuos[j] < pivote)&&(j > inicio))j–;
if(i < j){ //intercambiamos las casillas
individuos[i] ^= individuos[j];
individuos[j] ^= individuos[i];
individuos[i] ^= individuos[j];
}else{
hayCambio = false;
}
}
//ponemos el pivote en su posición
if(individuos[j][0] > pivote){
individuos[j] ^= individuos[inicio];
individuos[inicio] ^= individuos[j];
individuos[j] ^= individuos[inicio];
}
//llamadas recursivas para las dos mitades
quicksort(individuos, inicio, j-1);
quicksort(individuos, j+1, fin);
}
}
¿A que es mono?
Dead Channel
lo has hecho de cabeza el quickshort o con alguna ayuda? (a ver si me voy poniendo a programar algo yo)
Comment by The_IBITH — 22 June, 2007 @ 12:47
Con ayuda, pero al final valía más la cabeza, porque las explicaciones y los códigos que hay por ahí…
PD:(en el mio hay un fallillo, en el tercer while, al final, la j tiene que tener dos menos detrás igual que la i tiene dos más, no sé xq lo quita cuando en el editor está puesto…)
Comment by Juanmi — 22 June, 2007 @ 13:26