#1 a) Implement a Quicksort algorithm that uses a Median of Three pivot selectio

Question

#1

a) Implement a Quicksort algorithm that uses a Median of Three pivot selection.

i. This file should be called QSMedian.java

ii. The class should have a sort method: void sort(int[] input)

b) Write classes that generate test inputs of size 10, 100, 10000, 1000000.

i. One file should be RandomGen.java

ii. One file should be FixedGen.java

iii. RandomGen should generate uniformly random integers.

iv. FixedGen should always generate a fixed input.

c) Make a driver that sorts values from your input

i. This file should be called QSDriver.java

ii. This file should output the run-time in either ns or µs

iii. it should accept command-line as follows:

java QSDriver <sort> <gen> <length> <seed>

A.<sort> is either QSNormal or QSMedian

B.<gen> is either RandomGen or FixedGen

C.<length> is the number of ints to be sorted in the input array

D.<seed> is an optional argument that lets you repeat the random seed for RandomGen (but is ignored by FixedGen)

d)Record performance times of runs for each input size specified in 1c for Quicksorts implemented in 1a using RandomGen

Explanation / Answer

// Java program for implementation of QuickSort
class QSMedian
{
  
    int partition(int arr[], int low, int high)
    {
        int pivot = medianOfThree(arr, low, high);
        int i = (low-1); // index of smaller element
        for (int j=low; j<high; j++)
        {
            // If current element is smaller than or
            // equal to pivot
            if (arr[j] <= pivot)
            {
                i++;

                // swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // swap arr[i+1] and arr[high] (or pivot)
   swap(arr, i+1, high);

        return i+1;
    }

    int medianOfThree(int[] arr,int left, int right) {
       int mid = (left + right)/2;
       if arr[right] < arr[left]
           swap(arr, left, right);
       if arr[mid] < arr[left]
           swap(arr, mid, left);
    if arr[right] < arr[mid]
           swap(arr, right, mid);
       return mid;
    }

    void swap(int[] arr,int left,int right) {
       int temp = arr[left];
       arr[left] = arr[right];
       arr[right] = temp;
    }

    /*
      low --> Starting index,
      high --> Ending index */
    void sort(int arr[], int low, int high)
    {
        if (low < high)
        {
            /* pi is partitioning index, arr[pi] is
              now at right place */
            int pi = partition(arr, low, high);

            // Recursively sort elements before
            // partition and after partition
            sort(arr, low, pi-1);
            sort(arr, pi+1, high);
        }
    }

    public static void sort(int[] arr) {
   int n = arr.length;
        QSMedian ob = new QSMedian();
   sort(arr, 0, n-1);
    }
   
}

So here you go champ. You have your code for Quicksort algorithm that uses a Median of Three pivot selection. If you need any help on this, please let me know.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.