Pregunta
Así que estoy tratando de crear un método de clasificación rápida, sin embargo, no está ordenando correctamente. Aquí está mi entrada y la salida
matriz original:
10,0 50,0 70,0 80,0 60,0 90,0 20,0 30,0 40,0 0,0
matriz ordenada:
30,0 20,0 80,0 0,0 40,0 60,0 70,0 10,0 90,0 50,0
He intentado cambiar el bucle for a for(int i = left; i < right; i++)
pero ahora la salida es:
20,0 30,0 40,0 0,0 80,0 10,0 60,0 90,0 70,0 50,0
public static void sort(double[] a)
{
quickSort(a, 0, a.length-1);
}
public static void quickSort(double [] a, int left, int right)
{
if (left < right)
{
int pivotIndex = (left+right)/2;
int pos = partition(a,left,right,pivotIndex);
quickSort(a,left,pos-1);
quickSort(a,pos+1,right);
}
}
private static int partition(double [] a, int left,int right,int pivotIndex)
{
double temp = a[pivotIndex];
a[pivotIndex] = a[right];
a[right] = temp;
int pos = left;//represents boundary between small and large elements
for(int i = left; i < right-1; i++)
{
if (a[i] <= a[pivotIndex])
{
double temp2 = a[i];
a[i] = a[pos];
a[pos] = temp2;
pos++;
}
}
double temp3 = a[pivotIndex];
a[pivotIndex] = a[pos];
a[pos] = temp3;
return pos;
}
Solución
Esto es lo que quiere hacer:
private static void swap(double[] a, int i, int j) {
double t = a[i];
a[i] = a[j];
a[j] = t;
}
private static int partition(double [] a, int left,int right,int pivotIndex)
{
swap(a, pivotIndex, right);
int pos = left;//represents boundary between small and large elements
for(int i = left; i < right; i++)
{
if (a[i] < a[right])
{
swap(a, i, pos);
pos++;
}
}
swap(a, right, pos);
return pos;
}
I hizo que el código más claro por tener un método de ayuda swap
. Tenías 3 errores en el código original:
- El error de una sola vez en el bucle límite
- Usted está utilizando el índice incorrecto para obtener el elemento de pivote en el bucle
- intercambió elementos en los índices equivocadas después del bucle
Otros consejos
cambio
for(int i = left; i < right-1; i++)
a
for(int i = left; i < right; i++)
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow