C++: Few algorithm and How to Time a program.
#include <iostream>
#include <chrono>
using namespace std;
using namespace std::chrono;
// Algorithm A: an iterative solution
int sum_iter(int n) {
int the_sum = 0; // initialize an accumulator to 0
for(int i=1; i <= n; i++)// # iterates through the n integers
the_sum = the_sum + i; // add each integer to the accumulator
return the_sum;
}
// Algorithm B: an exact Solution (with formula)
int sum_exact(int n){
int the_sum = (n * (n + 1)) / 2;
return the_sum;
}
int Linear_Search(int A[], int size, int x)
{
int answer = -1;
for(int i=0; i<size; i++)
{
if(A[i]==x)
answer = i;
}
return answer;
}
int Better_Linear_Search(int A[], int size, int x)
{
int answer = -1;
for(int i=0; i<size; i++)
{
if(A[i]==x)
return i;
}
return answer;
}
int Better_Linear_Search_while(int A[], int size, int x)
{
int i = 0;
while(i < size)
{
if(A[i] == x)
return i;
i += 1;
}
return -1;
}
int Sentinel_Linear_Search(int A[], int size, int x)
{
int last_item = A[size-1];
A[size-1] = x;
int i = 0;
while(A[i] != x)
i += 1;
A[size -1] = last_item;
if(i<(size-1) || A[size-1] == x)
return i;
return -1;
}
int Recursive_Linear_Search(int A[], int size, int i, int x)
{
// int size = sizeof(A)/sizeof(int); // size of A
if(i > size-1)
return -1;
if(A[i] == x)
return i;
return Recursive_Linear_Search(A, size, i+1, x);
}
void InsertionSort(int A[], int size)
{
int key, i, j;
for(j=1;j<size;j++)
{
key = A[j];
i = j-1;
while((i>0) && A[i] > key)
{
A[i+1] = A[i];
i -= 1;
}
A[i+1]=key;
}
}
void InsertionSort2(int A[], int size)
{
int i,j; /* counters */
for (i=1; i < size; i++)
{
j=i;
while ((j > 0) && (A[j] < A[j-1]))
{
swap(A[j],A[j-1]); // a function that is defined in c++ std
j = j-1;
}
}
}
void SelectionSort(int A[], int size)
{
int i,j;
int min;
for (i=0; i<size; i++)
{
min=i;
for (j=i+1; j<size; j++)
if (A[j] < A[min]) min=j;
swap(A[i],A[min]);
}
}
int main()
{
// Timing a piece of code using <chrono>
int n=100000;
int sum_it, sum_e;
// Get starting timepoint
// begin = ; your code; end = ;
// elapsed = end - begin
//then print it
auto beginSumI = high_resolution_clock::now(); sum_it = sum_iter(n); auto endSumI = high_resolution_clock:
// Get duration.
auto elapsedSumI = duration_cast<nanoseconds>(endSumI - beginSumI);
cout << "Time taken by sum_iter: " << elapsedSumI.count() << " nanoseconds. " << " The sum (by iteration)
auto beginSumE = high_resolution_clock::now(); sum_e = sum_exact(n); auto endSumE = high_resolution_clock:
// Get duration.
auto elapsedSumE = duration_cast<nanoseconds>(endSumE - beginSumE);
cout << "Time taken by sum_exact: " << elapsedSumE.count() << " nanoseconds. " << " The sum (by exact sol)
//Testing SelectionSort:
//int A[] = {9,-7, 8, 0, 9, 10};
//int size = sizeof(A)/sizeof(int); // size of A
int size = 1000;
int A[size];
for (int i = 0; i<size; i++) A[i] = i+1;
//SelectionSort(A);
InsertionSort2(A, size);
cout << "[" << A[0];
for (int i = 1; i<10; i++) cout << "," << A[i];
//cout << "]" ;
cout << endl;
auto beginI = high_resolution_clock::now(); InsertionSort(A, size); auto endI = high_resolution_clock::
auto elapsedI = duration_cast<nanoseconds>(endI - beginI);
cout << "Time taken by InsertionSort(): " << elapsedI.count() << " nanoseconds. " << endl;
auto beginS = high_resolution_clock::now(); SelectionSort(A, size); auto endS = high_resolution_clock::
auto elapsedS = duration_cast<nanoseconds>(endS - beginS);
cout << "Time taken by SelectionSort(): " << elapsedS.count() << " nanoseconds. " << endl;
