QuestionQuestion

Overview: We are going to study the effect of choosing the pivot in the Quicksort algorithm. You will implement five different variations of the Quicksort algorithm and compare their relative speed using ten different input sequences. Test cases will measure the correctness and performance of your implementation using 50 scenarios (5 quicksort variations against 10 different sequences of numbers).

Part 1: Quicksort Implementation:

All the variations of the Quicksort should use the insertion sort algorithm once the length of the list to be sorted becomes less than six elements. Your implementation is to use recursion if the length is six or more. The input elements will be integers and your implementation should sort them in an ascending order. Implement 5 variations of the Quicksort algorithm using the five pivot choice techniques described below:

A. The pivot is the last element of the sequence.

B. The pivot is the first element of the sequence.

C. The pivot is the middle element of the sequence. (If the input sequence has N elements, the middle element is defined to be the element with the subscript of ⌊N/2⌋.). Note that ⌊x⌋ means the floor of the number x.
D. The pivot is the median value of the values of the first, middle and last elements of the sequence.
E. The pivot is the median of five elements of the sequence, chosen to be at positions of roughly 10%, 30%, 50%, 70%, and 90% in the sequence. Specifically, if the input sequence has N elements, then the pivot would be the median value of the values of the five elements having subscripts ⌊N/10⌋, ⌊(3*N)/10⌋, ⌊(5*N)/10⌋, ⌊(7*N)/10⌋, and ⌊(9*N)/10⌋. For example, if the sequence has 40 elements, the pivot would be the median of the five elements with the array indices 4, 12, 20, 28, and 36.

Part 2: Input Sequence Generation:

Generate the following 10 different input sequences to test your Quicksort implementation. Each input sequence will have N integers as follows (N is an even number given to you as input). Note: in the first 6 sequences, the N elements are all unique, but there may be repeated elements in the last 4 sequences

1. The sequence 1, 2, 3, ..., N (in increasing order). For example, if N = 1000, then the sequence would be: 1, 2, 3, 4, 5, ..., 1000.

2. The sequence N, N-1, ..., 2, 1 (in decreasing order). For example, if N = 1000, then the sequence would be: 1000, 999, ..., 2, 1.

3. The sequence 1, 3, 5, ..., N-1, 2, 4, 6, ..., N. For example, if N = 1000, then the sequence would be: 1, 3, 5, ..., 999, 2, 4, 6, ..., 1000.

4. The sequence 1, 3, 5, ..., N-3, N-1, N, N-2, N-4, ..., 4, 2. For example, if N = 1000,
then the sequence would be: 1,3,5 ...,997,999,1000,998,996, ..., 4, 2.

5. The sequence 1, N, 2, N-1, 3, N-2, 4, N-3, ..., N/2, (N/2)+1. For example, if N = 1000, then the sequence would be: 1, 1000, 2, 999, 3, 998, 4, 997, ..., 500, 501.

6. The sequence where each number is (7 + the previous number) mod N. That is, a(i) = (7 + a(i-1)) mod N. a(0)=0. For example, if N = 1000, then the sequence would be: 0, 7, 14, ..., 994, 1, 8, ..., 993.

7. The first N Fibonacci numbers modulo N: a(0) = 0; a(1) = 1; a(i) = (a(i-1) + a(i-2)) mod N for 1 < i < N.

8. The first N powers of 2 modulo N: a(0) = 1; a(i) = (2*a(i-1)) mod N for 0 < i < N.

9. The first N powers of 3 modulo N: a(0) = 1; a(i) = (3*a(i-1)) mod N for 0 < i < N.

10. A random sequence using the methods in java.util.Random: Use setSeed(long seed) to set the seed using a nine-digit integer which will be an input to your method. Use nextInt()%10000 N times to get N random integers between -9999 and 9999. Use these in the order generated as the sequence. Example:

Random generator = new Random();
generator.setSeed(123456789); // 123456789 is example, seed will be input
int num = generator.nextInt()%10000; // call this N times to complete the sequence

Implementation Guidelines:

Each quicksort method will take an input sequence as an array and return the number of comparisons required to sort it, rather than returning the sorted array.

Return the count only of the number of comparisons between two elements of the array being sorted, arr[ ], and do not count other comparisons, such as of indices and between array elements and non-array elements. Thus the comparisons in (j > 0 && arr[j - 1] > newValue) are not counted. Note that the pivot in Quicksort is an array element. The comparisons between array elements performed by Insertion sort must be counted, also. For all quicksort variants, make sure to use the partitioning function

described in the lectures (i.e., Slide 44 in Sorting Part 1). This will make your comparisons counting identical to ours.

For the variants D and E, use the following median definition in your implementation: “The median of a set of numbers is the value of the number at the middle position when the numbers are arranged in order from smallest to largest”. For example, to compute the median of {3,1,6,4,5}. First sort it => {1,3,4,5,6} and the median value is: 4.

However, you must use a stable sorting algorithm to handle the cases of duplicate values among the three or five values chosen. A stable sorting algorithm operates such that if two equal values appear in a particular order in the input, then they should appear in the same order in the sorted output. This will make your comparisons counting identical to ours. For instance, in variant D the pivot is chosen to be the median of the values of the first, middle and last elements of the sequence.

Example: consider three repeated values, {1a, 1b, 1c}, where the a, b, and c allow repeated items to be tracked. After stable sorting we have {1a,1b,1c}, the median value is 1b= 1, and the index of the pivot is the index of the middle item, 1b. The same concept can be applied for Variant E.

In addition, each input sequence method will take one argument N to generate the input sequence. The last input sequence method will take an additional parameter RNG. Each method should return an int array of size N, containing the input sequence to be used in the sorting. There are two input numbers:

1. Integer N which is an even number corresponds to the number of elements in a sequence. You will be using it for generating the input sequences according to the definitions above.

2. A nine-digit number which is used as the random seed for input sequence.

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

public class QuickSort
{
    private static class Comparision{
       int count = 0;

       public int getCount() {
            return count;
       }

       public void increment() {
            this.count++;
       }
    }

    public static class ArrayItem{
       public int value;
       public int pos;

       public ArrayItem(int value, int pos) {
            this.value = value;
            this.pos = pos;
       }

       @Override
       public String toString() {
            return ""+ value + ": " + pos;
       }
    }

    public int QuickSortPivotA(int [] array)
    {
       /*
       Implement the quicksort with pivot as the last element of the sequence.
       The method to sort array in place in ascending order
       the method is to return the number of comparisons required to complete the sorting.
       */
       Comparision comparision = new Comparision();
       quickSortA(array, 0, array.length-1, comparision);
       return comparision.getCount();
    }

    public void quickSortA(int [] array, int left, int right, Comparision comparision){
       if(left < right){
            int len = right - left +1;
            if(len >= 6){
                int partition = partition(array, left, right, right, comparision);
                if(left <= partition && partition <= right) {
                   quickSortA(array, left, partition - 1, comparision);
                   quickSortA(array, partition + 1, right, comparision);
                }
            }else {
                insertionSort(array, left, right, comparision);
            }
       }
    }...

By purchasing this solution you'll be able to access the following files:
Solution.java.

50% discount

Hours
Minutes
Seconds
$35.00 $17.50
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats