C++, if more info is needed, please let me know
Create a class that will implement 4 different sorting algorithms of your choosing. 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.
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.
Generating Random Doubles
To generate random doubles in a range you can use the following algorithm:
double r = (((double) rand() / (double) RAND_MAX) * (max - min)) + min ;
Timer Class C++:
#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;
}
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();
};
I recommend using these sorting algorithms.
public void insertionSort(int list[], int last)
{
int hold = 0;
int search = 0;
for(int current = 1; current <= last; current++)
{
hold = list[current];
for(search = current - 1; search >= 0 && hold < list[search]; search--)
{
list[search + 1 ] = list[search];
}
list[search + 1] = hold;
}
return;
}
public void selectionSort(int list[], int last)
{
int smallest = 0;
int holdData = 0;
for(int current = 0; current < last; current++)
{
smallest = current;
for(int index = current + 1; index <= last; index++)
{
if(list[index] < list[smallest])
{
smallest = index;
}
}
holdData = list[current];
list[current] = list[smallest];
list[smallest] = holdData;
}
return;
}
void shellSort(int list[], int last)
{
int hold;
int incre;
int index;
incre = last / 2;
while (incre != 0)
{
for(int curr = incre; curr <= last; curr++)
{
hold = list[curr];
index = curr - incre;
while(index >= 0 && hold < list [index])
{
//move larger element up in list
list[index + incre] = list [index];
//Fall back one partition
index = (index - incre);
}
//Insert hold in proper position
list[index + incre] = hold;
}
//End of pass--calculate next increment.
incre = incre / 2;
}
return;
}
int mergesort(int a[], int low, int high)
{
int mid;
if(low {
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,high,mid);
}
return(0);
}
void merge(int a[], int low, int high, int mid)
{
int i, j, k, c[100];
i = low;
j = mid+1;
k = low;
while((i<=mid)&&(j<=high))
{
if(a[i] {
c[k]=a[i];
k++;
i++;
}
else
{
c[k]=a[j];
k++;
j++;
}
}
while(i<=mid)
{
c[k]=a[j];
k++;
j++;
}
while(j<=high)
{
c[k]=a[i];
k++;
j++;
}
for(i=low;i {
a[i]=c[i];
}
}