you will be writing two objects to heuristically compare the performance of the
ID: 3777062 • Letter: Y
Question
you will be writing two objects to heuristically compare the performance of the bubble sort, selection sort, and insertion sort algorithms. To do this, a Timer object will be created and compositionally related to a storage class that will load the file contents, execute the sorts in an unbiased manner, handle any memory allocations that need to be made in order to do this, and report back the execution times of each algorithm on the provided input files for that machine.
Overview In this assignment, the student will write a C++ program that heuristically compares the execution time of bubble sort selection sort, and insertion sort using file sizes of various input sizes When completing this assignment, the student should demonstrate mastery of the following concepts Sorting Algorithms Bubble Sort Sorting Algorithms Selection Sor Sorting Algorithm Insertion Sort Timers Fast Clock Heuristic Algorithm Analys Object Composition File I/O Dynamic Memory and Stack Limitations Assignment In this assignment, you will be writing two objects to heuristically compare the performance of the bubble sort, selection sort, and insertion sort algorithms To do this a Timer object will be created and compositionally related to a storage class that will load the file contents, execute the handle any y allocati d to be bia d ma s that sorts i made in order to do this and report back the execution times of each algorithm on the provided input files for that machine First you will need to make a Timer object This object should function like a traditional stopwatch with methods for starting, stopping, resetting, and reporting back times The design of the object itself is up to you it but it must should minimally contain methods for the aforementioned ideas consist of a solitary object that provides interfaces appropriate for being compositionally included as part of a sorting object to facilitate the time keeping portion of this exercise Make sure you have a properly separated specification and implementation file for your Timer/Stopwatch object The second object you will make should be a data housing object that has methods that enable client code to read in the formatted contents of data files, house the data in memory, and execute bubble sort selection sort and insertion sort algorithms in a timed fashion with the assistance of your Timer object You will need to include interfaces/methods for providing file names, reporting erroneously formatted data files reporting files sizes, initiating individual sort algorithms, and reporting back unbiased times to the client code Finally, you must create a driver that instantiates your object, loads the files and executes the sorts and reports back the times back in a manner similar to the following screenshot Example Run Screen Shot "clUsers MarkielDesktop Progra ing Project E3 Stuff CSI 131 Basic Sorting Compa g A ts K ti ORTS OMPLETE XBubble Sort Elapsed Ti Elapsed Ti Elapsed Ti (Sel ti wt 8 nilli Populating A KS2000 el ts ORTS COMPLETE Elapsed Ti (Bubble Sort Elapsed Ti ti Sort 32 Elapsed Ti KSelecti t 62 Populating A C252000 el ting ORTS COMPLETEExplanation / Answer
// The exact execution time you get will vary depending on the speed and execution environment of your machine during the time of run.
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
long length = 1000;
const long max_length = 300000;
int list[max_length];
void read()
{
ifstream fin("random.dat", ios::binary);
for (long i = 0; i < length; i++)
{
fin.read((char*)&list[i], sizeof(int));
}
fin.close();
}
void bubbleSort()
{
int temp;
for(long i = 0; i < length; i++)
{
for(long j = 0; j < length-i-1; j++)
{
if (list[j] > list[j+1])
{
temp = list[j];
list[j] = list[j+1];
list[j+1] = temp;
}
}
}
}
void insertionSort()
{
int temp;
for(long i = 1; i < length; i++)
{
temp = list[i];
long j;
for(j = i-1; j >= 0 && list[j] > temp; j--)
{
list[j+1] = list[j];
}
list[j+1] = temp;
}
}
long partition(long left, long right)
{
int pivot_element = list[left];
int lb = left, ub = right;
int temp;
while (left < right)
{
while(list[left] <= pivot_element)
left++;
while(list[right] > pivot_element)
right--;
if (left < right)
{
temp = list[left];
list[left] = list[right];
list[right] = temp;
}
}
list[lb] = list[right];
list[right] = pivot_element;
return right;
}
void quickSort(long left, long right)
{
if (left < right)
{
long pivot = partition(left, right);
quickSort(left, pivot-1);
quickSort(pivot+1, right);
}
}
int main()
{
double t1, t2;
for (length = 1000; length <= max_length; )
{
cout << " Length : " << length << ' ';
read();
t1 = clock();
bubbleSort();
t2 = clock();
cout << "Bubble Sort : " << (t2 - t1)/CLK_TCK << " sec ";
read();
t1 = clock();
insertionSort();
t2 = clock();
cout << "Insertion Sort : " << (t2 - t1)/CLK_TCK << " sec ";
read();
t1 = clock();
quickSort(0, length - 1);
t2 = clock();
cout << "Quick Sort : " << (t2 - t1)/CLK_TCK << " sec ";
switch (length)
{
case 1000 :
length = 5000;
break;
case 5000 :
length = 10000;
break;
case 10000 :
length = 50000;
break;
case 50000 :
length = 100000;
break;
case 100000 :
length = 200000;
break;
case 200000 :
length = 300000;
break;
case 300000 :
length = 300001;
break;
}
}
return 0;
}
//The above code requires a document "random.dat" which contains 3,00,000 whole numbers put away arbitrarily. This document is perused every time before a sorting is performed.
Then again you can create "random.dat" document through this code. Thus you can produce a greater document for more numbers.
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
const size_t length = 300000;
int main()
{
ofstream fout("random.dat", ios::binary);
srand(time(NULL));
int r;
for (size_t i = 0; i < length; i++)
{
r = rand();
fout.write((char*)&r, sizeof(r));
}
fout.close();
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.