This is the Question that I am working on it : Code the selection sort in C++. C

Question

This is the Question that I am working on it :

Code the selection sort in C++. Create 3 .cpp files: sortMain.cpp, selectionSort.cpp, and insertionSort.cpp. Below is a template that you should use:

//file: sortMain.cpp

#include

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

using namespace std;
int main ( int argc, char* argv[] ) {
.
.
.
}

//----------------------------------------------------------------------
//file: selectionSort.cpp
void selectionSort ( 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 each sort in a table like the following:

selection sort

My Answer as the following :
/Programs:

//----------------------------------------------------------------------
//file: sortMain.cpp
#include <iostream>
#include <ctime> // Needed for the true randomization
#include <cstdlib>
#include <conio.h> //to catch the output screen
#include "selectionSort2.cpp"
extern void selectionSort2(int A[], int n);
using namespace std;
int main(int argc, char* argv[]) {
int N[] = {10, 100, 1000, 10000};
int randomNo;
int A[10000];
srand(time(0)); // This will ensure a really randomized number by help of time.
cout<<endl<<"REPORT";
cout<<endl<<"------------------------------------------------";
cout<<endl<<"N # tElapsed tCPU avgCPU";
cout<<endl<<"------------------------------------------------";
for(int i=0;i<4;i++)
{
for (int j= 0; j< N[i]; j++) {
randomNo = rand(); // Randomizing the number.
A[j] = randomNo;
}//for
selectionSort2(A, N[i]);
}
cout<<endl<<"------------------------------------------------";
cin.get();//to keep the console window
}//main

/*******************************************************************/

//file: selectionSort2.cpp
#include <iostream>
#include <math.h>
#include <time.h>
#include <Windows.h>
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;
}
void selectionSort2(int arr[], int n)
{
//pos_min is short for position of min
int pos_min, temp;
  
//mark start time
clock_t st = clock();
double start = cpuTime();
long count = 0, count2 = 0;
for (int i = 0; i < n - 1; i++)
{
pos_min = i;//set pos_min to the current index of array
for (int j = i + 1; j < n; j++)
{
if (arr[j] < arr[pos_min]) {
pos_min = j;
++count2; // # of iteration
}
//pos_min will keep track of the index that min is in, this is needed when a swap happens
  
}//inner for loop
//if pos_min no longer equals i than a smaller value must have been found, so a swap must occur
if (pos_min != i)
{
temp = arr[i];
arr[i] = arr[pos_min];
arr[pos_min] = temp;
} //if
  
++count; // # of iteration
}// outer loop

//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<<endl<<n<<" "<<(count2+count)<<" "<<elapsedTime<<" "<<cpuTime<<" "<<cpuTime/2;
///////////////////////////?????????????????????????????????////////////////////////////////////////////////////////////
}

My Question is: How can I calculate the AvgCPU Time do ?

- I'm thinking about dividing the cputime/n .. because the cpu will be working as long as the size of n .

- Another answer that I got from Chegg is cputime/2 and I don't have explanition for that !!

-------Any Help will be appreciated----------------

selection sort

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

Explanation / Answer

You could use this function for selection sort as well:

void selectionSort(int arr[], int n) {
      int i, j, minIndex, tmp;  
      for (i = 0; i < n - 1; i++) {
            minIndex = i;
            for (j = i + 1; j < n; j++)
                  if (arr[j] < arr[minIndex])
                        minIndex = j;
            if (minIndex != i) {
                  tmp = arr[i];
                  arr[i] = arr[minIndex];
                  arr[minIndex] = tmp;
            }
      }
}

AvgCPU time depends upon the number of iterations the program took for the portion we checked for CPU time. So it should be divided by n.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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