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, May 15 '18 at 06:29

Rick_C137 · Answer 1 · 2018-05-15T09:29:54.223

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.

better answer would be explaining his mistakes rather than copypasting a ready and well-known code snippet — mangusta, May 15 '18 at 08:56
@Ashish he is trying to implement hoare's partition you have implemented lomuto partition — Guhan Nagarajan, May 15 '18 at 09:00
@GuhanNagarajan ah my bad Thanks, I didn't know about Hoare's partition method :) — Rick_C137, May 15 '18 at 09:07
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. — Rick_C137, May 15 '18 at 09:33

Java Quicksort Partition method

1 Answers1