Find the implementation of the sorting algorithms given below. I am trying to compare the efficiency of some of the sorting algorithms. I need to implement the algorithms for insertion sort, Merge Sort and Quicksort and use timing in C++ to compare the run time of the algorithms on inputs consisting of positive integers. I want to try the algorithms on input sizes of 1000, 10,000, 50,000, 100000, 150000, 200,000, 250,000, 300,000. The input can be generated randomly using the rand() function in C++. I need to use a vector structure in C++ STL to store the integers. Tabulate the results and plot the time Vs. input size. I must use the code provided below. I need to submit code with tabulated results and plot. Implementation of additional sorting algorithms will receive extra points. When testing algorithms, I need to use a small input (size 20) and print the list to make sure the algorithm sorts the list properly.
Code is given below:
#include
#include
#include
#include
using namespace std;
const int SIZE = 20;
void initializeList(vector& l)
{
//srand(time(0));
for (int i = 0; i < SIZE; i++)
l. push_back(rand() % 500);
}
template
void printVector(const vector& l)
{
cout << "Elements of the vector: ";
for (int i = 0; i < l. size(); i++)
cout << l[i] << " ";
cout << endl;
}
template
int linearSearch(const vector& l, T key)
{
for (int i = 0; i < l. size(); i++)
if (l[i] == key)
return i; // return first instance of the key. Function terminates
return -1; // search failed, return index -1.
}
//Binary Search iterative
template
int BinarySearchIterative(const vector& numbers, int numbersSize, T key)
{
int low = 0;
int mid= 0;
int high = numbersSize - 1;
while (high >= low)
{
mid = (low + high) / 2; // index of the middle element
if (numbers[mid] < key)
low = mid + 1;
else if (numbers[mid] > key)
high = mid - 1;
else if (numbers[mid] == key)
return mid;
}
return -1; // failed
}
//Binary Search Recursive
template
int BinarySearchRec(const vector& numbers, int low, int high, T key)
{
if (high < low)
return -1;
else
{
int mid = (low + high) / 2; // index of the middle element
if (numbers[mid] < key)
return BinarySearchRec(numbers, mid + 1, high, key);
else if (numbers[mid] > key)
return BinarySearchRec(numbers, low, mid-1, key);
else if (numbers[mid] == key)
return mid;
}
}
template
void selectionSort(vector& l)
{
for (int i = 0; i < l. size() -1 ; i++)
{
int minIndex = i;
for (int j = i+1; j < l. size(); j++)
if (l[minIndex] > l[j])
minIndex = j;
//swap elements in locations i and minIndex
T temp = l[i];
l[i] = l[minIndex];
l[minIndex] = temp;
}
}