Please give me an explanation of the step by step.

Code the insertion sort in C++. Create 2 .cpp files: sortMain.cpp and insertionSort.cpp. Below is a template that you should use:

 //---------------------------------------------------------------------- //file: sortMain.cpp #include  extern void insertionSort ( int A[], int n ); using namespace std; int main ( int argc, char* argv[] ) { . . . return 0; } //---------------------------------------------------------------------- //file: insertionSort.cpp void insertionSort ( int A[], int n ) { . . . } 

Run the sort on input sizes of 10, 100, 1000, 10000, 100000, 200000, 300000, 400000, 500000, and 1000000 of random values. Depending upon the speed of your computer, you may only be able to run one or a few sorts for larger input sizes. Report the array size n (N), number of test iterations (#), total elapsed time (tElapsed), total CPU time (tCPU), average CPU time (avgCPU) for insertion sort in a table like the following:

Note: You may need to allocate your arrays dynamically as follows, int[] A = new int[ N ]; rather than statically as in int A[ N ];.

insertion sort
N	#	tElapsed	tCPU	avgCPU
10
100
1000
10000
100000
200000
300000
400000
500000
1000000

I have the code below. Please help me to find out where am I doing wrong. And how to print the result.

//file: sortMain.cpp #include #include #include #include

extern void insertionSort(int A[], int n);

using namespace std;

static double cpuTime(void) { FILETIME createTime, exitTime, kernelTime, userTime;

if (GetProcessTimes(GetCurrentProcess(), &createTime, &exitTime, &kernelTime, &userTime) != -1) { SYSTEMTIME userSystemTime; if (FileTimeToSystemTime(&userTime, &userSystemTime) != -1) return (double)userSystemTime.wHour * 3600.0 + (double)userSystemTime.wMinute * 60.0 + (double)userSystemTime.wSecond + (double)userSystemTime.wMilliseconds / 1000.0; } return -1; }

int main(int argc, char* argv[]) {

int N[4] = { 10, 100, 1000, 10000 };//, 100000, 200000, 300000, 400000, 500000, 1000000}; int randomNo; //srand(time(0)); // This will ensure a really randomized number by help of time. cout << endl << "REPORT"; cout << endl << "-------------------------------------"; cout << endl << "N\t#\ttElapsed\ttCPU\tavgCPU"; cout << endl << "-------------------------------------";

//mark start time clock_t st = clock(); double start = cpuTime();

//do stuff double sum = 0; for (double d = 0; d < 10000; d += 0.01) { sum += sin(d) * cos(d); } //Sleep(10); //sleep for 2 sec

for (int i = 0; i < 4; i++) { int* A = new int[N[i]]; for (int j = 0; j < N[i]; j++) { randomNo = rand(); // Randomozing the num A[j] = randomNo; } insertionSort(A, N[i]); delete[]A; } cout << endl << "-------------------------------------";

//mark end time double end = cpuTime(); clock_t et = clock();

//calc deltas double cpuTime = end - start; double elapsedTime = ((double)et - st) / CLOCKS_PER_SEC;

//report results cout << "cpu time = " << cpuTime << " sec" << endl; cout << "elapsed time = " << elapsedTime << " sec" << endl; //cin.get(); // to keep the console window }

-------------------------------------------------------------------------------------------------

//file: insertionSort.cpp

#include #include #include #include using namespace std;

void insertionSort(int A[], int n) {

int k, j; for (int i = 1; i < n; i++) { k = A[i]; //take value j = i; // Move elements of A[0..i-1], that are greater than k , to one position ahead // of their current position while (j > 0 && A[j - 1] > k) { A[j] = A[j - 1]; j--; } A[j] = k; //insert in right place } // finally array is sorted

}