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
