Question

IN JAVA

Implement Quicksort with ‘median-of-three’ partitioning

You should be able to test a 1000, 10000 and 10000 length array with inters spanning from 1 to 10,000.

You cannot use functions from standard libraries implementing Quicksort.

Answer 1

The solution is in the code snippet below

// ArrayIns.java
// demonstrates quick sort with median-of-three partitioning
////////////////////////////////////////////////////////////////

import java.util.Scanner; 

public class ArrayIns
{
      private int[] theArray;          // ref to array theArray
      private int nElems;               // number of data items
//--------------------------------------------------------------
   public ArrayIns(int max)          // constructor
   {
      theArray = new int[max];      // create the array
      nElems = 0;                    // no items yet
   }
//--------------------------------------------------------------
   public void insert(int value)    // put element into array
   {
      theArray[nElems] = value;      // insert it
      nElems++;                      // increment size
   }
//--------------------------------------------------------------
   public void display()             // displays array contents
   {
      System.out.print("A: ");
      for(int j=0; j<nElems; j++)    // for each element,
         System.out.print(theArray[j] + " ");  // display it
      System.out.println("");
      System.out.println("");
   }
//--------------------------------------------------------------
   public void quickSort()
   {
      recQuickSort(0, nElems-1);
   }
//--------------------------------------------------------------
   public void recQuickSort(int left, int right)
   {
      int size = right-left+1;
      if(size <= 3)                  // manual sort if small
         manualSort(left, right);
      else                           // quicksort if large
      {
         long median = medianOf3(left, right);
         int partition = partitionIt(left, right, median);
         recQuickSort(left, partition-1);
         recQuickSort(partition+1, right);
      }
    }  // end recQuickSort()
//--------------------------------------------------------------
   public long medianOf3(int left, int right)
   {
      int center = (left+right)/2;
                                         // order left & center
      if( theArray[left] > theArray[center] )
         swap(left, center);
                                         // order left & right
      if( theArray[left] > theArray[right] )
         swap(left, right);
                                         // order center & right
      if( theArray[center] > theArray[right] )
         swap(center, right);

      swap(center, right-1);             // put pivot on right
      return theArray[right-1];          // return median value
    }  // end medianOf3()
//--------------------------------------------------------------
   public void swap(int dex1, int dex2)  // swap two elements
   {
      int temp = theArray[dex1];        // A into temp
      theArray[dex1] = theArray[dex2];   // B into A
      theArray[dex2] = temp;             // temp into B
   }  // end swap()
//--------------------------------------------------------------
    public int partitionIt(int left, int right, long pivot)
    {
       int leftPtr = left;             // right of first elem
       int rightPtr = right - 1;       // left of pivot

       while(true)
       {
          while( theArray[++leftPtr] < pivot )  // find bigger
             ;                                  //    (nop)
          while( theArray[--rightPtr] > pivot ) // find smaller
             ;                                  //    (nop)
          if(leftPtr >= rightPtr)      // if pointers cross,
             break;                    //    partition done
          else                         // not crossed, so
             swap(leftPtr, rightPtr);  // swap elements
       }  // end while(true)
       swap(leftPtr, right-1);         // restore pivot
       return leftPtr;                 // return pivot location
    }  // end partitionIt()
//--------------------------------------------------------------
   public void manualSort(int left, int right)
   {
      int size = right-left+1;
      if(size <= 1)
         return;         // no sort necessary
      if(size == 2)
      {               // 2-sort left and right
         if( theArray[left] > theArray[right] )
            swap(left, right);
         return;
      }
      else               // size is 3
      {               // 3-sort left, center, & right
         if( theArray[left] > theArray[right-1] )
            swap(left, right-1);                // left, center
         if( theArray[left] > theArray[right] )
            swap(left, right);                  // left, right
         if( theArray[right-1] > theArray[right] )
            swap(right-1, right);               // center, right
      }
    }  // end manualSort()
//--------------------------------------------------------------
    public static void main(String[] args) throws java.lang.Exception
    {
      int maxSize = 0;              // array size
      ArrayIns arr;                 // reference to array
      // Declare the object and initialize with 
      // predefined standard input object 
      Scanner sc = new Scanner(System.in);
      
      System.out.println("Enter The size of the array: ");
      System.out.println("");
      maxSize = sc.nextInt();
      
      arr = new ArrayIns(maxSize);  // create the array

      for(int j=0; j<maxSize; j++)  // fill array with
      {                          // random numbers from 1 to 10,000
         int n = (int)(java.lang.Math.random()*10001);
         arr.insert(n);
      }
      System.out.println("The contents before sorting  ");
      arr.display();                // display items
      arr.quickSort();              // quicksort them
      System.out.println("The contents after sorting  ");
      arr.display();                // display them again
    }  // end main()
}  // end class ArrayIns
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////

The output screenshot

For sample I have taken input size to be 20 and the numbers filled in the array are randomly generated