Java Quicksort Partition method

Question

I am writing a Java quicksort method. my code currently is as follows

    public class Quicksort {

   public static void main(String[ ] args)
   {
      final String BLANKS = "  "; // A String of two blanks
      int i;                      // Array index

      int[ ] data = { 1000, 80, 10, 50, 70, 60, 90, 20, 30, 40, 0, -1000 };

      // Print the array before sorting:
      System.out.println("Here is the entire original array:");
      for (i = 0; i < data.length; i++)
         System.out.print(data[i] + BLANKS);
      System.out.println( );

      // Sort the numbers, and print the result with two blanks after each number.
      quicksort(data, 1, data.length-2);
      System.out.println("I have sorted all but the first and last numbers.");
      System.out.println("The numbers are now:");
      for (i = 0; i < data.length; i++)
         System.out.print(data[i] + BLANKS);
      System.out.println( );
   }

Quicksort Method

    public static void quicksort(int[ ] data, int first, int n)
   {
      int pivotIndex; // Array index for the pivot element
      int n1;         // Number of elements before the pivot element
      int n2;         // Number of elements after the pivot element

      if (n > 1)
      {
         // Partition the array, and set the pivot index.
         pivotIndex = partition(data, first, n);

         // Compute the sizes of the two pieces.
         n1 = pivotIndex - first;
         n2 = n - n1 - 1;

         // Recursive calls will now sort the two pieces.
         quicksort(data, first, n1);
         quicksort(data, pivotIndex + 1, n2);
      }
   }

Partition Method

   private static int partition(int[ ] data, int first, int n){ 
      int low = first;
      int high = n;
      int pivot = data[low];

      while(low < high){
         low ++;

         while(low <= high && data[low] < pivot){
            low ++;
         }
         while(high >= low && data[high] > pivot){
            high--;
         }
         if(low<=n && low < high){
            int temp = data[low];
            data[low] = data[high];
            data[high] = temp;
         }
      }
      return low;  
   }//end partition

}//end class

When I currently run the program i get a result of 1000 80 0 10 70 60 90 20 30 40 50 -1000 After several different attempts and rewrites of the partition method I still cannot get the array to sort properly. The task is to have the whole array sorted except the first and last numbers.

Get any reliable implementation of partition. Yours contains a lot of mistakes. Omits the first element, uses n=subarray size as right index and so on. — MBo
– MBo, Commented May 15, 2018 at 6:29

Rick_C137 · Accepted Answer · 2018-05-15 09:29:54Z

2

Quicksort Method

public static void quicksort(int[ ] data, int first, int last){
          if (last-first > 1){
             // Partition the array, and set the pivot index.
             pivotIndex = partition(data, first, n);
             //n1 = pivotIndex - first; //problem is here 
             //  n2 = n - n1 - 1;       // and here 
             // Recursive calls will now sort the two pieces.
             quicksort(data, first, pivotIndex);
             quicksort(data, pivotIndex + 1, last);
          }
       }

Partition Method actual Hoare's partition.

  private static int partition(int[ ] data, int first, int last){ 
  int low = first-1;
  int high = n+1;
  int pivot = data[low];

    while (true) {

        do {
            low++;
        }
        while (data[low] < pivot);

        do {
            high--;
        }
        while (data[j] > pivot);

        if (low < high) {
            int temp = data[low];
            data[low] = data[high];
            data[high] = temp;
        } else {
            return high;
        }
    }

}

I have updated both the functions now you just need to call.

int[ ] data = { 1000, 80, 10, 50, 70, 60, 90, 20, 30, 40, 0, -1000 };
quicksort(data, 1, data.length-2);

Here is a good explanation of Hoare partition.

edited May 15, 2018 at 9:29

answered May 15, 2018 at 8:20

Rick_C137

1421 silver badge12 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

mangusta Over a year ago

better answer would be explaining his mistakes rather than copypasting a ready and well-known code snippet

Guhan Nagarajan Over a year ago

@Ashish he is trying to implement hoare's partition you have implemented lomuto partition

Rick_C137 Over a year ago

@GuhanNagarajan ah my bad Thanks, I didn't know about Hoare's partition method :)

Rick_C137 Over a year ago

Thanks for comments I have updated the answer. The problem was in quicksort method only, will test partition method and update my answer once I find the issue in it . until then I have given correct partition method from the answer in a link.

Collectives™ on Stack Overflow

Java Quicksort Partition method

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related