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

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:

My Answer as the following :

//----------------------------------------------------------------------
//file: sortMain.cpp

#include <iostream>

#include <ctime> // Needed for the true randomization
#include <cstdlib>
#include <conio.h> //to catch the output screen

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

using namespace std;

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

   //N = 10, 100, 1000, 10000, 100000, 200000, 300000, 400000, 500000, 1000000

   const int N = 10000;
int A[N];
int randomNo;
   srand(time(0)); // This will ensure a really randomized number by help of time.

   for (int i = 0; i< N; i++) {
       randomNo = rand(); // Randomizing the number.
       A[i] = randomNo;
   // cout << " " << A[i];
   }//for

selectionSort2(A, N);

cin.get();//to keep the consol window

}//main

//----------------------------------------------------------------------
//file: selectionSort2.cpp

#include <iostream>
#include <math.h>
#include <time.h>
#include <Windows.h>

using namespace std;
//based on:
// http://stackoverflow.com/questions/19378805/measure-cpu-time-on-windows-using-getprocesstimes
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 << "cpu time = " << cpuTime << " sec" << endl;
   cout << "elapsed time = " << elapsedTime << " sec" << endl;
   cout << "operation count(outer loop) = " << count << endl;
   cout << "operation count2(inner loop) = " << count2 << endl;

///////////////////////////?????????????????????????????????////////////////////////////////////////////////////////////

cout << "# of iteration = " << count2+count << endl;

}

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

My Question is .. Am I doing the (# of iteration ) right ? if not explain the correct way to do that please . Also How can I calculate the

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

Explanation / Answer

//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;
///////////////////////////?????????????????????????????????////////////////////////////////////////////////////////////
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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