Lista desordenada imperfecta, pero no demasiado lejos.
int partition(std::vector& tab, int size){
int pivot = rand() % size;
std::swap(tab[pivot], tab[0]);
int i = 1;
for(int j = 1; j < size; j++){
if(tab[j] < tab[0]){
std::swap(tab[i], tab[j]);
i++;
}
}
std::swap(tab[0], tab[i-1]);
return i-1;
}
Este código se acerca bastante a darme una lista de enteros bien ordenada, pero aún no es perfecto hasta ahora. Simplemente no entiendo dónde está el error.
¿Cómo puedo modificar partition() para que los resultados desordenados se ordenen bien?
davy.ai
La función partition() se utiliza en realidad en el algoritmo quicksort para ordenar una lista de enteros. La implementación actual de la función partition() elige un elemento aleatorio como pivote, lo cambia con el primer elemento y luego divide la lista en dos partes de modo que todos los elementos menores que el pivote estén a su izquierda, y todos los elementos mayores que el pivote estén a su derecha.
Para modificar la función partition() y ordenar mejor la lista, necesitamos modificar la forma en que se elige el elemento pivote. Una idea puede ser elegir la mediana de tres elementos seleccionados aleatoriamente como pivote. Esto reduciría la posibilidad de rendimiento en el peor de los casos y mejoraría el rendimiento general del algoritmo quicksort.
Otra modificación que podríamos hacer es usar un enfoque de particionamiento diferente llamado “algoritmo de la bandera nacional holandesa”. Este algoritmo divide la lista en tres partes: elementos menores que el pivote, elementos iguales al pivote y elementos mayores que el pivote. Este enfoque podría ser más eficaz en caso de que haya pocos elementos repetidos muchas veces en la lista.
En resumen, podemos modificar la función partition() mediante el uso de una estrategia de selección de pivote mejor, o mediante el uso de un algoritmo de particionamiento diferente, como el algoritmo de la bandera nacional holandesa.