CS201-Homework 4 Solved

Description: In this assignment, you will write a C++ program that finds the kth largest number among a set of N numbers. However, this time, you will use a variation of the quicksort algorithm to implement the program. The details can be found below.

 

 

1)  The Input and Expected Output
 

The input and the expected output of the program is the same as described in Homework 1 and 3. The program will take the type of algorithm to be applied, k (a number less than or equal to N). Then it will take N followed by a list of N numbers. As output, it will print out the kth largest number and the total elapsed time for the completion of the algorithm.

 

As the only difference from Homework 1 and 3, the algorithm type can be 1, 2, 3 or 4. You can modify and reuse the test generator program to generate test inputs. You can also just modify the sample test inputs for Homework 1 to test the same set of numbers with algorithm type being 4.

 

Your code will only be tested with algorithm type 4.

 

 

2)  The Algorithm: quickselect
 

You will implement a variation of the quicksort algorithm to find the kth largest number among a set of numbers S in O(N) time on average, where N is the total amount of numbers, i.e., |S|. The outline of the algorithm, quickselect is as follows.

 

If N <= 10, sort all the numbers (using insertion sort) and return the kth
Else, pick a pivot number, v ϵ S.
Partition S – {v} into S1 and S2, as done in quicksort.
If k <= |S1|, then the kth largest number must be in S1. Return quickselect(S1, k).
If k = 1 + | S1|, then the pivot, v is the kth largest number. Return v.
Otherwise, the kth largest number lies in |S2|, and it is the (k – |S1| – 1)st largest number in S2. Return quickselect(S2, k – |S1| – 1).
 

3)  The (Extended) Design
 

You can reuse the design of Homework 1 and/or Homework 3. You just need to add one extra class, AlgorithmSortQuick, which extends from the SelectionAlgorithm class and overwrites the select method to implement the new algorithm. The select method within the AlgorithmSortQuick class should make a call to the recursive quickselect method. It takes an array of numbers, the left and the right index of the partition of interest, and k. The overall design is depicted below.

 

 

You might need to make further small modifications in function main and the TestBed class to accept 4 as the algorithm type. This is because, previously the algorithm type was assumed to be 1, 2 or 3. For instance, you should make a modification/extension within the setAlgorithm method of the TestBed class. If the type argument is 4, an object of type AlgorithmSortQuick should be assigned to the algorithm member variable. The rest of the design and implementation can be reused as is.

 

If you have not submitted Homework 1 or Homework 3, then you have to implement at least the main method, the TestBed class and the SelectionAlgorithm class as described in the assignment description of Homework 1.