For this lab, we compare a new algorithm for sorting that may be an improvement over Selection Sort. We will check 2 things: The time it takes to sort 100,000 integers and the number of instructions it takes to sort 10 integers.

You will need a Stack class: stack.h stack.cpp

Type in the code in these 2 images:

1) Compile with UNIT_TEST defined and then run with -d yes to see the time it takes in seconds. Report that time in submission box along with the time you found when testing Selection Sort. Which is faster?

2) Compile without UNIT_TEST so we only test with 10 numbers and count how many comparisions are done in this algorithm. (Those are conditional expressions such as <.>, Which does the fewest comparisons?

here is the code typed out

#define CATCH_CONFIG_MAIN #include #include #include #ifdef UNIT_Test #include "catch.hpp" #endif // UNIT_Test #include "stack.h" #define UNIT_TEST using namespace std;

template class SortClass { private: void swap(T &a, T&b); int split(T a[], int first, int last); public: void sort(T a[], int first, int last);

}; template int SortClass ::split (T arr[], int first, int last) { T x= arr[last]; int i= (first-1); for (int j=first; j void SortClass ::sort(T a[], int first, int last) { Stack stack; stack.push (first); stack.push (last); while (not stack.isEmpty()) { stack.pop(last); stack.pop(first); int s= split (a, first, last); if (s-1>first ) { stack.push(first); stack.push(s-1); } if (s+1 void SortClass :: swap(T &a, T &b) { T temp=a; a=b; b=temp; }

#ifndef UNIT_TEST int main () { const int N=10; int x1[N]={1,3,5,6,4,2,8,9,7}; for (auto e: x1) std:: cout s; s.sort(x1,0,N-1); for (auto e: x1) std:: cout

#ifdef UNIT_TEST using Catch:: Matchers::Equals; TEST_CASE ("A fast sort") { const int N=6; int x1[N]= {1,3,5,6,4,2}; int x2[N]={1,2,3,4,5,6}; std :: vector v1(x1,x1+N); std :: vector v2(x2, x2+N); REQUIRE_THAT (v1, not Equals (v2)); SortClass s; s.sort(x1,0, N-1); std:: vector v0(x1,x1+N); REQUIRE_THAT (vO, Equals(v2)); const int M=100000; int x3[M]; int x4[M]; std:: ifstream ifs1("numbers"); for (auto &e: x3) ifs1>> e; std:: ifstream ifs2("sorted"); for (auto &e:x4) ifs2>> e; s.sort(x3,0,M-1); std:: vector v3(x3, x3+M); std:: vector v4(x4, x4+M); REQUIRE_THAT (v3, Equals (v4)); } #endif

when I try to compile it, it is giving me errors on line 83, 84

using Catch:: Matchers::Equals; TEST_CASE ("A fast sort")

the errors are

line 83 error: use of undeclared identifier 'Catch'

line 84 error: c++ requires a type specifier for all declarations

line 84 error: expected ';' after top level declarator

How do i fix these problems and the code runs? thanks