Quicksort using HoarePartition got incorrect output

user_19169227 0
Viewed 38

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...

partition quicksort output algorithm java
3 Answers

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);
      // ...
user_32820560

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 passing pivot-1.

  • In your HoarePartition method you forgot to move the indexes i and j after the swap.

  • The returning condition should check not only whether the two indexes i and j have met but also if they have crossed each other if (i >= j) return j;

  • The innermost loops should be written as two while loops instead of a while and a do-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]
user_44156250

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()
user_191692270
Related