Problema de la mediana de Quicksort de 3, 5, 7 elementos.
Enfrento un gran problema con el algoritmo de Quicksort. Tengo que elegir un pivote con la mediana de 3, 5 y 7 elementos del arreglo. Lo he hecho para 3 elementos, pero no está funcionando correctamente y no sé cómo volver a hacer este código alternativamente para tomar la mediana de 5 y 7 elementos. ¿Cómo elegir un pivote a partir de la mediana de más de 3 elementos?
Por favor, no me odies, estoy intentando aprender.
Función Quicksort:
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
int pi = partition_3(arr, low , high);
quickSort(arr, low, pi);
quickSort(arr, pi + 1, high);
}
}
Partición:
int partition( int arr[], int low, int high)
{
int pivot = arr[low];
int i = low - 1, j = high + 1;
while (true) {
do {
i++;
} while (arr[i] < pivot);
do {
j--;
} while (arr[j] > pivot);
if (i >= j)
return j;
swap(arr[i], arr[j]);
}
}
Partición mediana de 3:
int partition_3(int arr[], int low, int high)
{
int tab[] = { low,(high -low) / 2,high };
sort(tab, tab + 3);
int ind = 3 / 2;
int mediana = tab[ind];
swap(arr[mediana], arr[low]);
return partition(arr, low, high);
}
davy.ai
Para elegir un pivote a partir de la mediana de más de 3 elementos, puedes seguir los siguientes pasos:
Calcula la mediana de los elementos elegidos. Esto se puede hacer ordenándolos y eligiendo el elemento que se encuentre en el medio.
Intercambia la mediana con el primer elemento del arreglo. Esto te permitirá utilizar la misma función de particionamiento que antes.
Continúa con el quicksort como de costumbre.
Para implementar esto en tu código, puedes crear una función de particionamiento separada para la mediana de 5 o 7 elementos, siguiendo un enfoque similar a la función partition_3. Finalmente, puedes modificar la función quickSort para utilizar la función de particionamiento correspondiente dependiendo del número de elementos.
Ten en cuenta que estas modificaciones pueden afectar el rendimiento del algoritmo y que existen otras formas de elegir un pivote, como la selección aleatoria o seleccionando la mediana de las medianas.