algoritmo di partizione QuickSort
Domanda
sto cercando di programmare l'algoritmo quicksort da Cormen Algoritmo Textbook. Qui di seguito è il mio codice.
class Quicksort
{
public void qSort(int[] a, int p, int r)
{
if(p<r)
{
int q = Partition(a, p,r);
qSort(a, p, q-1);
qSort(a, q+1, r);
}
}
private int Partition(int[] a, int p, int r)
{
int x = a[r];
int i = p-1;
int temp=0;
for(int j=p; j<r-1; j++)
{
if(a[j]<=x)
{
i++;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
temp = a[i+1];
a[i+1] = a[r];
a[r] = temp;
return (i+1);
}
}
public class QuickSortTest
{
public static void main(String[] args)
{
Quicksort qsort = new Quicksort();
int[] array = {5, 4, 7, 2, 1, 9, 3, 6, 10, 8};
System.out.print("Original Array : ");
for(int i=0; i<array.length;i++)
{
System.out.print(array[i] + " ");
}
int length = array.length;
qsort.qSort(array, 0, length-1);
System.out.print("Sorted Array : ");
for(int i=0; i<array.length;i++)
{
System.out.print(array[i] + " ");
}
}
}
Ma, io sono sempre un'uscita sbagliata quando eseguo questo codice.
Original Array : 5 4 7 2 1 9 3 6 10 8
Sorted Array : 1 4 5 2 6 7 3 8 9 10
Qualcuno può spiegare che cosa è sbagliato. Ho implementato questo codice esattamente come indicato in "Introduzione agli algoritmi" libro. Grazie.
Soluzione
No non hai copiato direttamente :) ho qui ...
for(int j=p; j<r-1; j++)
dovrebbe essere
for(int j=p; j<r; j++)
o
for(int j=p; j <= r-1; j++)
Il libro scrive:
for j = p to r - 1
che comprende r - 1
. E ricordate il libro ha array, che è a partire da 1 e non 0. Quindi in generale gli algoritmi del libro dovrebbero essere "copiati" con grande cura e con gli array che va da 1.
Modifica: Info su l'algoritmo per un commento L'algoritmo nel libro prende l'ultimo elemento come perno. Sarà quindi renderlo un terribile algoritmo per gli array già ordinati. Si finirà in O (n ^ 2) in modo che nessuno dovrebbe usare questo algoritmo per la produzione (a meno che non si sa cosa si sta facendo e che cosa il vostro ingresso è) come array tendono ad essere un po 'in ordine. build-in di Java algoritmo è più intelligente e si può leggere su di esso nel Javadoc
Altri suggerimenti
Se volete qualche riferimento su come implementare rapido tipo, si potrebbe provare a controllare il codice sorgente effettivo per Arrays.sort (*) nel JDK, che è una versione modificata di quick sort. ( http://www.oracle.com/technetwork/java/javase /downloads/index.html per il download se non si dispone già src.zip nell'installazione JDK).
Fornire un ulteriore implementazione in Java. Essa si basa anche sullo stesso algoritmo e si prende cura di elementi duplicati nella matrice troppo.
public void sort( int[] inputArray, int lo, int high){
int pivotIndex = partition(inputArray,lo,high);
System. out .println("Got PivotIndex as " + pivotIndex);
if (lo < pivotIndex -1)
sort(inputArray,lo,pivotIndex - 1);
if (pivotIndex+1 < high)
sort(inputArray,pivotIndex+1,high);
return ;
}
private int partition( int[] inputArray, int leftPtr,int rightPtr)
{
printArray(inputArray);
int pivot = inputArray[leftPtr];
while (leftPtr<rightPtr){
while (inputArray[leftPtr]<pivot)
leftPtr++;
while (inputArray[rightPtr]>pivot)
rightPtr--;
if (leftPtr<rightPtr)
{
exchange(inputArray,leftPtr,rightPtr);
//Cases which have repeated numbers...
if (inputArray[leftPtr] == inputArray[rightPtr])
leftPtr++;
}
}
return leftPtr;//return any one
}