My homework asked me to implement Quicksort algorithm exactly the same as the pseudocode in the textbook: It specifies to use HoarePartition to do the partition.
pivot <- A[leftMost]
i <- leftMost; j <- rightMost 1
and here's my code:
import java.util.Arrays;
public class Main{
public static void main(String args[]){
int[] array1 = {10, 4, 2, 8, 7, 3, 5, 9, 6, 1};
int n1 = array1.length;
System.out.print("Before sorting is: ");
System.out.println(Arrays.toString(array1));
System.out.printf("After sorting is: ");
Quicksort(array1, 0, n1 -1);
System.out.println(Arrays.toString(array1));
} //end main
public static void Quicksort(int[]array, int start, int end){
if(start<end){
int pivot = HoarePartition(array, start, end);
Quicksort(array, start, pivot-1);
Quicksort(array, pivot 1, end);
}
} //end Quicksort()
public static int HoarePartition(int[] array, int start, int end){
int pivot = array[start];
int i = start;
int j = end 1;
while(true){
while(array[i] < pivot)
i ;
do{j--}while(array[j] > pivot)
if(i <= j)
return j;
int temp = array[i];
array[i] = array[j];
array[j] = temp;
} //end while
} //end HoarePartition()
And the output is:
Before sorting is: [10, 4, 2, 8, 7, 3, 5, 9, 6, 1]
After sorting is: [1, 3, 2, 5, 7, 4, 8, 9, 6, 10]
Apparently, it's not sorted correctly, I've been thinking over and over again but still don't know which part of my algorithm is wrong...
CodePudding user response:
The two recursive calls should be:
Quicksort(array, start, pivot); // (not pivot-1)
Quicksort(array, pivot 1, end);
Classic Hoare partition
// ...
int i = start-1;
int j = end 1;
while(true){
while(array[ i] < pivot);
while(array[--j] > pivot);
// ...
CodePudding user response:
There are a few problems with the code you wrote.
In your first recursive call of
quicksort
, the pivot bound should be included instead of passingpivot-1
.In your
HoarePartition
method you forgot to move the indexesi
andj
after the swap.The returning condition should check not only whether the two indexes
i
andj
have met but also if they have crossed each otherif (i >= j) return j;
The innermost loops should be written as two
while
loops instead of awhile
and ado-while
public static void Quicksort(int[] array, int start, int end) {
if (start < end) {
int pivot = HoarePartition(array, start, end);
Quicksort(array, start, pivot);
Quicksort(array, pivot 1, end);
}
}
public static int HoarePartition(int[] array, int start, int end) {
int pivot = array[start];
int i = start;
int j = end;
//Iterating until the left index crosses the right index
while (true) {
//Looking for an element on the left side greater than the pivot
while (array[i] < pivot) i ;
//Looking for an element on the right side lower than the pivot
while (array[j] > pivot) j--;
//If the left index passed the right index, then there is no element on the left side greater then the pivot or a lower element on the right side
if (i >= j) return j;
//Swapping the elements greater than the pivot (left) and lower than the pivot (right) (the index haven't met yet)
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i ;
j--;
}
}
Output
Before sorting is: [10, 4, 2, 8, 7, 3, 5, 9, 6, 1]
After sorting is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
CodePudding user response:
Thanks! I found the mistake I did:
I set the initial value wrong in HoarePartition()
, after adjust the i, j and the loop I typed, it works correctly!
public static int HoarePartition(int[] array, int start, int end){
int pivot = array[start];
int i = start -1 ;
int j = end 1;
while(true){
do{i ;}while(array[i] < pivot);
do{j--;}while(array[j] > pivot);
if(i>=j)
return j;
/*swap(array[i], array[j])*/
swapIJ(array, i, j);
} //end while
} //end HoarePartition()