Domanda
Così sto cercando di creare un metodo Quicksort, tuttavia, non è l'ordinamento correttamente. Heres il mio ingresso e uscita
array originale:
80,0 10,0 50,0 70,0 60,0 90,0 20,0 30,0 40,0 0,0
array ordinato:
0,0 30,0 20,0 80,0 40,0 60,0 70,0 10,0 90,0 50,0
Ho provato a cambiare il ciclo for per for(int i = left; i < right; i++)
ma ora l'uscita è:
0,0 20,0 30,0 40,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;
}
Soluzione
Questo è ciò che si vuole fare:
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;
}
Ho fatto il codice più chiaro di avere un metodo di supporto swap
. Hai avuto 3 bug nel codice originale:
- L'errore di una tantum sul confine ciclo
- Si sta utilizzando l'indice sbagliato per ottenere l'elemento di rotazione nel ciclo
- scambiato elementi gli indici sbagliate dopo il ciclo
Altri suggerimenti
cambia
for(int i = left; i < right-1; i++)
a
for(int i = left; i < right; i++)
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow