Write a program to sort an array as follows. a. Use insertion sort to sort the a

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

Explanation / Answer

class Comparisons 002 { 003     public static int selectionSort( int list[]) 004     { 005         int position = 0, n = list.length, count = 0; 006         for( int j = 0; j

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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