Write a program to sort an array as follows. a. Use insertion sort to sort the a
ID: 3693003 • Letter: W
Question
Write a program to sort an array as follows. a. Use insertion sort to sort the array. Print the number of comparisons and the number of item movements. b. Use Shellsort to sort the array using the function shellSort given in this chapter. Print the number of comparisons and the number of item movements. c. Test your program on a list of 1,000 elements and on a list of 10,000 elements.
Here is my code :
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
class IntTracer {
public:
static int assignmentCount;
static int lessCompareCount;
IntTracer(int n = 0) : data(n) {}
bool operator<(const IntTracer& rhs)const
{
++lessCompareCount; return data < rhs.data;
}
IntTracer& operator=(const IntTracer& rhs)
{
if (this == &rhs) return *this;
++assignmentCount;
data = rhs.data;
return *this;
}
friend std::ostream& operator<<(std::ostream& out, const IntTracer& n)
{
return out << n.data;
}
private:
int data;
};
int IntTracer::assignmentCount = 0;
int IntTracer::lessCompareCount = 0;
template <typename T> void insertionSort(T* a, int N);
template <typename T> void shellSort(T* a, int N);
void testSorts(int N);
int main()
{
srand(time(0));
testSorts(1000);
std::cout << " ";
testSorts(10000);
}
void testSorts(int N)
{
IntTracer a[1000];
IntTracer b[10000];
for (int i = 0; i < N; ++i) a[i] = i + 1;
std::random_shuffle(a, a + N);
for (int i = 0; i < N; ++i) b[i] = a[i];
IntTracer::assignmentCount = 0;
std::cout << "Insertion Sort " << N << " items ";
insertionSort(a, N);
std::cout << "Number of compares: " << IntTracer::lessCompareCount << " ";
std::cout << "Number of assignment: " << IntTracer::assignmentCount << " ";
std::cout << "Number of swap: " << IntTracer::assignmentCount / 2 << " ";
IntTracer::assignmentCount = 0;
IntTracer::lessCompareCount = 0;
std::cout << " Shell Sort " << N << " items ";
shellSort(b, N);
std::cout << "Number of compares: " << IntTracer::lessCompareCount << " ";
std::cout << "Number of assignment: " << IntTracer::assignmentCount << " ";
std::cout << "Number of swap: " << IntTracer::assignmentCount / 2 << " ";
}
template <typename T> void exch(T& a, T& b)
{
T temp = a;
a = b;
b = temp;
}
template <typename T> void insertionSort(T* a, int N)
{
for (int i = 0; i < N; i++)
for (int j = i; j > 0; j--)
if (a[j] < a[j - 1]) exch(a[j], a[j - 1]);
else break;
}
template <typename T> void shellSort(T* a, int N)
{
int h = 1;
while (h < N / 3) h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, ...
while (h >= 1)
{ // h-sort the array.
for (int i = h; i < N; i++)
{
for (int j = i; j >= h && (a[j] < a[j - h]); j -= h)
exch(a[j], a[j - h]);
}
h = h / 3;
}
}
could you fix this so that I wont get an error