Please help me do this. Implement a recursive version of the insertion sort for

Question

Please help me do this.

Implement a recursive version of the insertion sort for a vector, using the upcoming function description as a guide.

If first = last, simply return. If first < last, call insertionSortRerursive() with arguments v, first, and last-1. Then insert v[last-1] so that the range [first, last) is in order.

// use insertion sort to order the range [first, last)

template <typename T>

void insertionSortRecursive(vector<T>& v, int first, int last);

You are required to do the following tasks:

(1) Implement insertionSortRecursive in hw2-sort.h and compile your code with linux command:

g++ hw2-sort.cpp -o sort

(2) Use your recursive insertion sort algorithm to sort vector data of different sizes (10,000 to

100,000 with a step size of 10,000), summarize the running time statistics in a table, and provide

your observations (how the running time increases as the vector size increases) briefly. Once you

provide the implementation of function insertionSortRecursive, you can use the following

command to read and sort a vector of size 10000: ./sort 10000

Here is the code I have

int main(int argc, const char **argv)

{

vector<int> dataVector;

ifstream dataFile("hw2-data.dat");

double duration;

int n = atoi(argv[1]), count;

int value;

if (dataFile)

{

// read the elements in the file into a vector

while(dataFile>>value && count<n)

{

dataVector.push_back(value);

count++;

}

}

dataFile.close();

cout<<dataVector.size()<<" integers were read."<<endl;

//writeVector(dataVector);

clock_t start;

start = clock();

insertionSortRecursive(dataVector,0,dataVector.size());

duration = (clock() - start) / (double) CLOCKS_PER_SEC;

cout<<"Runing time is "<< duration <<" seconds."<<' ';

//writeVector(dataVector);

//cout<<dataVector.size()<<endl;

return 0;

Explanation / Answer

// hw2-sort.h

#ifndef HW2_SORT_H

#define HW2_SORT_H

#include <vector>

using namespace std;

// use insertion sort to order the range [first, last)

template <typename T>

void insertionSortRecursive(vector<T>& v, int first, int last)

{

if (first == last)

return;

if (first < last)

{

insertionSortRecursive(v, first, last-1);

int pos = last - 1;

T curr = v[last - 1];

while (pos > 0 && v[pos-1] > curr)

{

v[pos] = v[pos - 1];

pos--;

}

v[pos] = curr;

}

}

#endif

// hw2-sort.cpp: NOTE count MUST BE INITIALIZED TO 0

#include <iostream>

#include <fstream>   

#include <cstdlib>

#include "hw2-sort.h"

using namespace std;

int main(int argc, const char **argv)

{

vector<int> dataVector;

ifstream dataFile("hw2-data.dat");

double duration;

int n = atoi(argv[1]), count = 0;

int value;

if (dataFile)

{

// read the elements in the file into a vector

while(dataFile>>value && count<n)

{

dataVector.push_back(value);

count++;

}

}

dataFile.close();

cout<<dataVector.size()<<" integers were read."<<endl;

//writeVector(dataVector);

clock_t start;

start = clock();

insertionSortRecursive(dataVector,0,dataVector.size());

duration = (clock() - start) / (double) CLOCKS_PER_SEC;

cout<<"Runing time is "<< duration <<" seconds."<<' ';

//writeVector(dataVector);

//cout<<dataVector.size()<<endl;

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.