Write a program that compares the sorting and searchingalgorithms we learned in class to the ones in the STL.
Create a set of test a vectors, one with 10, 100, 1000, 10000,and 100000 elements.
For the sorting algorithms, compare Bubble Sort, Quick Sort, andMerge Sort to STL sort() using the random vectors.
For the searching algorithms, compare Linear and Binary Searchto STL find(); for Linear and STL find(), compare both unsorted andsorted vectors. Use the following queries for each of the randomvectors created: 15, 327, 756, 8947, and 99999.
Note: Use the randomVector() function provided inmain.cpp to generate a vector with random numbers. You may also usethe Timer class provided to time your code; use ns as the timeunit.
Print out the random vector with 10 elements before andafter sorting to verify functionality.
Code:
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <algorithm>
#include <iterator>
#include <chrono>
#include <cstdlib>
#include <ctime>
using namespace std;
using namespace chrono;
class Timer
{
private:
steady_clock::time_point tic =steady_clock::now();
steady_clock::time_point toc =steady_clock::now();
public:
Timer(){}
void start();
void stop();
uint64_t duration(string unit);
};
void Timer::start(){ tic = steady_clock::now(); }
void Timer::stop (){ toc = steady_clock::now(); }
uint64_t Timer::duration(string unit = “ns”)
{
steady_clock::duration time = toc – tic;
map<string, uint64_t> unitmap;
unitmap[“ns”] =duration_cast<nanoseconds>(time).count();
unitmap[“us”] =duration_cast<microseconds>(time).count();
unitmap[“ms”] =duration_cast<milliseconds>(time).count();
unitmap[“s” ] =duration_cast<chrono::seconds>(time).count();
if(unitmap.find(unit) == unitmap.end()){ returnunitmap[“ns”]; }
return unitmap[unit];
}
//————————————————-
void PrintVec(vector<uint64_t> vec, uint64_t width)
{
vector<uint64_t>::iterator it =vec.begin();
vector<uint64_t>::iterator end = vec.end();
for(; it != end; ++it)
{
cout << setw(width) <<*it << (it != (end – 1) ? “,” : “”) << ” “;
}
}
//————————————————-
vector<uint64_t> randomVector(uint64_thowmanyelements)
{
srand(time(NULL)); //Seed random numbergenerator with system clock
vector<uint64_t> vec(howmanyelements), rvec;uint64_t rn;
while(–howmanyelements > 0){vec[howmanyelements] = howmanyelements; }
while(!vec.empty()){ rn = rand()%(vec.size());rvec.push_back(vec.at(rn)); vec.erase(vec.begin() + rn); }
return rvec;
}
//————————————————-
//Algorithms go here.
//————————————————-
int main(int argc, char** argv)
{
}
——————————————————————————————————-
Sample:
InC++««««<< SUMMARY >>>>>>>>>>>>>>>>>>>>>>>>>>>> Test Vector number of elements: 10, 100, 1000, 10000, 100000 10, 5600, Sorting Algorithms Bubble Sort : Quick Sort Merge Sort : STL sort() : 2300, 7300, 2200, 100, 129100, 18200, 73100, 16900, 1000, 12590500, 207100, 728700, 202800, 10000, 1218218100, 2957000, 8551100, 2540600, 100000 125091376700 ns 29586200 ns 94034500 ns 31461800 ns Test Queries: 15, 327, 756, 8947, 99999 10 100, Searching Algorithms (Query: 15) Test Vector number of elements: Linear (Unsorted) Search Linear (Sorted) Search Binary Search STL find() – unsorted STL find() – sorted 1100, 800, 1200, 1000, 1100, 800, 1000, 1100, 1000, 7700, 800, 1000, 10000, 10900, 800, 1500, 8200, 900, 100000 29800 ns 800 ns 2900 ns 21900 ns 900 ns 800, 800, 5800, 800, 10 800, Searching Algorithms (Query: 327) Test Vector number of elements: Linear (Unsorted) Search Linear (Sorted) Search Binary Search STL find() – unsorted STL find() – sorted 700, 1100, 900, 700, 100, 1400, 1400, 1100, 1300, 1200, 1000, 5500, 3200, 1100, 4400, 2500, 10000, 24300, 3200, 1400, 18400, 2700, 100000 621600 ns 3100 ns 2200 ns 459300 ns 2700 ns 10, 800, 100, 1500, Searching Algorithms (Query: 756) Test Vector number of elements: Linear (Unsorted) Search : Linear (Sorted) Search Binary Search STL find() – unsorted STL find() – sorted 700, 1400, 1000, 8000, 6500, 1200, 10000, 42100, 6300, 1300, 32000, 5100, 100000 365100 ns 6800 ns 1800 ns 245900 ns 5300 ns 1100, 900, 800, 700, 6000, 1400, 1300, 5000, 1000, 10300, Searching Algorithms (Query: 8947) Test Vector number of elements: Linear (Unsorted) Search : Linear (Sorted) Search Binary Search STL find() – unsorted STL find() – sorted 10, 800, 800, 1000, 900, 800, 100, 1500, 1500, 1000, 9200, 10000, 19700, 94900, 1400, 14900, 51700, 100000 443400 ns 82500 ns 1900 ns 346400 ns 83400 ns 1100, 6700, 1400, 1300, 6600, 10, 900, Searching Algorithms (Query: 99999) Test Vector number of elements: Linear (Unsorted) Search : Linear (Sorted) Search Binary Search STL find() – unsorted STL find() – sorted 100, 1500, 1400, 1000, 10000, 79900, 87100, 700, 1100, 1000, 8700, 8600, 1200, 6700, 6600, 1400, 100000 490700 ns 814300 ns 1600 ns 368700 ns 632800 ns 900, 1400, 59600, 59200, 800, 1200, <<<< SUMMARY >>>>>>>>>>>>>>>>>>>>>>>>>>>>> Show transcribed image text ««««>>>>>>>>>>>>>>>>>>>>>>>>>> Test Vector number of elements: 10, 100, 1000, 10000, 100000 10, 5600, Sorting Algorithms Bubble Sort : Quick Sort Merge Sort : STL sort() : 2300, 7300, 2200, 100, 129100, 18200, 73100, 16900, 1000, 12590500, 207100, 728700, 202800, 10000, 1218218100, 2957000, 8551100, 2540600, 100000 125091376700 ns 29586200 ns 94034500 ns 31461800 ns Test Queries: 15, 327, 756, 8947, 99999 10 100, Searching Algorithms (Query: 15) Test Vector number of elements: Linear (Unsorted) Search Linear (Sorted) Search Binary Search STL find() – unsorted STL find() – sorted 1100, 800, 1200, 1000, 1100, 800, 1000, 1100, 1000, 7700, 800, 1000, 10000, 10900, 800, 1500, 8200, 900, 100000 29800 ns 800 ns 2900 ns 21900 ns 900 ns 800, 800, 5800, 800, 10 800, Searching Algorithms (Query: 327) Test Vector number of elements: Linear (Unsorted) Search Linear (Sorted) Search Binary Search STL find() – unsorted STL find() – sorted 700, 1100, 900, 700, 100, 1400, 1400, 1100, 1300, 1200, 1000, 5500, 3200, 1100, 4400, 2500, 10000, 24300, 3200, 1400, 18400, 2700, 100000 621600 ns 3100 ns 2200 ns 459300 ns 2700 ns
10, 800, 100, 1500, Searching Algorithms (Query: 756) Test Vector number of elements: Linear (Unsorted) Search : Linear (Sorted) Search Binary Search STL find() – unsorted STL find() – sorted 700, 1400, 1000, 8000, 6500, 1200, 10000, 42100, 6300, 1300, 32000, 5100, 100000 365100 ns 6800 ns 1800 ns 245900 ns 5300 ns 1100, 900, 800, 700, 6000, 1400, 1300, 5000, 1000, 10300, Searching Algorithms (Query: 8947) Test Vector number of elements: Linear (Unsorted) Search : Linear (Sorted) Search Binary Search STL find() – unsorted STL find() – sorted 10, 800, 800, 1000, 900, 800, 100, 1500, 1500, 1000, 9200, 10000, 19700, 94900, 1400, 14900, 51700, 100000 443400 ns 82500 ns 1900 ns 346400 ns 83400 ns 1100, 6700, 1400, 1300, 6600, 10, 900, Searching Algorithms (Query: 99999) Test Vector number of elements: Linear (Unsorted) Search : Linear (Sorted) Search Binary Search STL find() – unsorted STL find() – sorted 100, 1500, 1400, 1000, 10000, 79900, 87100, 700, 1100, 1000, 8700, 8600, 1200, 6700, 6600, 1400, 100000 490700 ns 814300 ns 1600 ns 368700 ns 632800 ns 900, 1400, 59600, 59200, 800, 1200, >>>>>>>>>>>>>>>>>>>>>>>>>
Expert Answer
Answer to Write a program that compares the sorting and searching algorithms we learned in class to the ones in the STL. Create a …