USING JAVA Implement the quicksort optimization medianofthre

USING JAVA:

Implement the quicksort optimization median-of-three, i.e., first, middle, and last, as pivot for partition. Into this working quicksort algorithm: ( the spacing is bad, sorry)

  private static void quicksort(int low, int high) {

                int i = low, j = high;

                // Get the pivot element from the middle of the list

                int pivot = arr[(high+low)/2];

                // Divide into two lists

                while (i <= j) {

                                // If the current value from the left list is smaller then the pivot

                                // element then get the next element from the left list

                                while (arr[i] < pivot) i++;

                                // If the current value from the right list is larger then the pivot

                                // element then get the next element from the right list

                                while (arr[j] > pivot) j--;

                                // If we have found a value in the left list which is larger than

                                // the pivot element and if we have found a value in the right list

                                // which is smaller then the pivot element then we exchange the

                                // values.

                                // As we are done we can increase i and j

                                if (i < j) {

                                               exchange(i, j);

                                               i++;

                                               j--;

                                } else if (i == j) { i++; j--; }

             }

                // Recursion

                if (low < j)

                               quicksort(low, j);

                if (i < high)

                               quicksort(i, high);

    }

Solution

Hi, Please find my program:

private static void quicksort(int low, int high) {

   if (low >= high)
       return;

   // Selecting the pivot
   int first = low;
   int second = arr[(high+low)/2];
   int third = arr[high];
   // median for first three
   int pivot = Math.max(
           Math.min(
                   array[first],
                   array[second]),
                   Math.min(
                       Math.max(
                               array[first],
                               array[second]
                               ),
                       array[third]
                   )
           );

   while (low <= high)
   {
       while (array[low] < pivot)
       {
           low++;
       }

       while (array[high] > pivot)
       {
           high--;
       }

       if (low <= high)
       {
           // swapping
           int temp = array[low];
           array[low] = array[high];
           array[high] = temp;
           low++;
           high--;
       }
   }

   // Recursion
   if (low < j)
       quicksort(low, j);
   if (i < high)
       quicksort(i, high);
}