need a main cpp , SelectionAlgotihm cpp and TestBed cpp In this assignment, you will write a C program that finds the k th 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 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 k th largest number and the total elapsed time for the completion of the algorithm 2) The Algorithm quickselect You will implement a variation of the quicksort algorithm to find the k th 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 , sort all the numbers (using insertion sort) and return the k th number Else, pick a pivot number, v S Partition S v into S 1 and S 2 , as done in quicksort If k 1 , then the k th largest number must be in S 1 Return quickselect(S 1 , k) If k 1 S 1 , then the pivot, v is the k th largest number Return v Otherwise, the k th largest number lies in S 2 , and it is the (k S 1 1)st largest number in S 2 Return quickselect(S 2 , k S 1 1) main cpp main modification extension if(type 4) algorithm new Algorithm SortQuick (k) cu ses TestBed algorithm Selection Algorithm execute() void set Algorithmink int, in type int) void TestBed() TestBed) Selection Algorithm k int select() int Selection Algorithm (ink int) AgorithmSortal AlgorithmSortk select() int AlgorithmsortAllink int) select() int AlgorithmSortKink int) extension AlgorithmSortQuick I select() int quickselect in numbers int, in left int, in right int, in k int) int I AlgorithmsortQuick(ink int)

The Answer is in the image, click to view ...

Answered step by step

Verified Expert Solution

Link Copied!

Question

1 Approved Answer

Posted on Sep 24, 2024

need a main.cpp , SelectionAlgotihm.cpp and TestBed.cpp In this assignment, you will write a C++ program that finds the k th largest number among a

need a main.cpp , SelectionAlgotihm.cpp and TestBed.cpp

image text in transcribed

In this assignment, you will write a C++ program that finds the k^th 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 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 k^th largest number and the total elapsed time for the completion of the algorithm.

2) The Algorithm: quickselect

You will implement a variation of the quicksort algorithm to find the k^th 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 , sort all the numbers (using insertion sort) and return the k^th number.
Else, pick a pivot number, v S.
1. Partition S {v} into S₁ and S₂, as done in quicksort.
2. If k 1|, then the k^th largest number must be in S₁. Return quickselect(S₁, k).
3. If k = 1 + | S₁|, then the pivot, v is the k^th largest number. Return v.
4. Otherwise, the k^th largest number lies in |S₂|, and it is the (k |S₁| 1)st largest number in S₂. Return quickselect(S₂, k |S₁| 1).

main.cpp main / modification/extension if(type == 4) algorithm = new Algorithm SortQuick (k); cu ses TestBed / -* algorithm: Selection Algorithm +execute():void +set Algorithmink: int, in type : int) : void +TestBed() + TestBed) ! Selection Algorithm #k: int +select(): int +Selection Algorithm (ink: int) AgorithmSortal AlgorithmSortk +select(): int +AlgorithmsortAllink: int) +select(): int +AlgorithmSortKink: int) extension AlgorithmSortQuick I select(): int +quickselect/in numbers * : int, in left : int, in right : int, in k : int): int I AlgorithmsortQuick(ink: int)