Sorting help

Learning Goal: I’m working on a c++ multi-part question and need an explanation and answer to help me learn.

Create a class that will implement 4 different sorting algorithms. For this lab you are going to want to have overloaded constructors and mutator functions that will set the data section with a list to sort. Your class should sort a primitive array or a vector. For this assignment we want to be able to sort primitive types (int, char, double, float). So, it might be best to have your sort algorithms work on doubles. Each of your sort functions should produce a list of sorted values.

Additional Functionality

You should have a function that will return the number of iterations it took to sort the list. If I choose one of your sort algorithms I should then be able to call the function to get the number of iterations.

Timer class: Attached to this assignment is the timer class that will allow you to profile each of the sorting algorithms. Implement this class and create a function that will return the time the last sort took to sort the list of numbers. In the end you should be able to successively call each of the sort functions and produce the number of iterations and the time it took to sort.

Note: The timer class is here for you to use. You must use the timer classes given to you. If they do not meet your needs then it is up to you to make them meet your needs. Anyone who uses Data Structures functionality like linked lists, trees, graphs and in this case a timer that is built into the programming language or found online will see a grade reduction of 50%.

Testing your code

In main you should generate a large list of random doubles to be sorted ( No 10 items is not a large list. It should be more like a few thousand), use each function to sort the list, and output the iterations, and the time each algorithm took to sort your list. To get a better feel for how each of these algorithms performs you should vary the size of the list to be sorted. Try varying the size of your lists. In comments let me know which was more efficient and why you think it was.

Timer.h:

#include

class Timer
{
private:
LARGE_INTEGER start;
LARGE_INTEGER stop;
LARGE_INTEGER freq;
double PCFreq;
__int64 CounterStart;

public:
Timer();
void startTimer();
void stopTimer();
double getMilli();
double getSeconds();
double getMicro();

};
Timer code:

#include
#include “Timer.h”

using std::cout;
using std::endl;

int main()
{
Timer t;

t.startTimer();
Sleep(1000);
t.stopTimer();
cout << "In Milliseconds " << t.getMilli() << endl;
cout << "In Seconds " << t.getSeconds()<< endl;
cout << std::fixed << "In Microseconds " << t.getMicro() << endl;

return 0;
}
Timer::Timer()
{
if(!QueryPerformanceFrequency(&freq))
cout << "QueryPerformanceFrequency failed!\n";

}
void Timer::startTimer()
{

QueryPerformanceCounter(&start);

}
void Timer::stopTimer()
{
QueryPerformanceCounter(&stop);

}
double Timer::getMicro()
{
PCFreq = freq.QuadPart / 1000000.0;
return double((stop.QuadPart – start.QuadPart)) / PCFreq;
}
double Timer::getMilli()
{
PCFreq = freq.QuadPart / 1000.0;
return double((stop.QuadPart – start.QuadPart)) / PCFreq;
}
double Timer::getSeconds()
{
return double(stop.QuadPart – start.QuadPart)/ freq.QuadPart;

}
The sorting algorithms to use:

void insertionSort(double* list, int last, long long int& x)
{
double hold = 0;
int search = 0;

for (int current = 1; current = 0 && hold < list[search]; search–)
{
x++;
list[search + 1] = list[search];
}
list[search + 1] = hold;
}
return;

}

void selectionSort(double* list, int last, long long int& x)
{
int smallest = 0;
int holdData = 0;

for (int current = 0; current < last; current++)
{
smallest = current;
for (int index = current + 1; index <= last; index++)
{
x++;
if (list[index] < list[smallest])
{
smallest = index;
}
}
holdData = list[current];
list[current] = list[smallest];
list[smallest] = holdData;
}
return;
}
void shellSort(double* list, int last, long long int& x)
{
int hold;
int incre;
int index;

incre = last / 2;
while (incre != 0)
{
for (int curr = incre; curr = 0 && hold < list[index])
{
x += 2;

list[index + incre] = list[index];

index = (index – incre);
}
x++;

list[index + incre] = hold;
}

incre = incre / 2;
}
return;
}
void merge(double* a, int low, int high, int mid, long long int& x)
{
int i, j, k, c[100000];
i = low;
j = mid + 1;
k = low;
while ((i <= mid) && (j <= high))
{
x++;
if (a[i] < a[j])
{
c[k] = a[i];
k++;
i++;
}
else
{
c[k] = a[j];
k++;
j++;
}
}
while (i <= mid)
{
c[k] = a[j];
k++;
i++;
x++;
}
while (j <= high)
{
c[k] = a[i];
k++;
j++;
x++;
}
for (i = low; i < k; i++)
{
a[i] = c[i];
x++;
}
}
int mergesort(double* a, int low, int high, long long int& x)
{
int mid;
if (low < high)
{
mid = (low + high) / 2;
mergesort(a, low, mid, x);
mergesort(a, mid + 1, high, x);
merge(a, low, high, mid, x);

}
return(0);
}