Need a C++ program for the comparison of 3 algorithms: Insertion sort, merge sor
ID: 3751983 • Letter: N
Question
Need a C++ program for the comparison of 3 algorithms: Insertion sort, merge sort and quicksort AND ALSO Include randomizaed quicksort in your comparisons
Measure average time by generating n random data values and calling the three sorts for the same data. Vary n and graph the times T(n) as a function of n for each sort. The range of n should be determined so that it allows to compare the performance of the algorithms.
To obtain the elapsed time call a timing function within your program, that starts the timer just before and stops it just after the section to be timed. Be sure that there is no I/O in the timed section.
To obtain accurate timings T(n), run the program (for a particular n) with the same data in a loop, and divide the total time for the loop by the number of iterations (i.e., take the average time per iteration); this will give you one data point as the time T(n) in your graph.
To check if your program sorts correctly, also output the sequence of points to be sorted as well as the sorted sequence (with each sort) for n = 10 only.
On linux or mac use "script" to generate a "typescript" file showing your compilation and execution with output of the program. Otherwise add another type of log file or screenshots to show these.
Submit your program, input and output for small (n = 10) runs, and report describing methods used (including random number generator, data range used, timing function and its precision). The program should be well-commented and have a description of input and output parameters for each sorting function.
Your report should further contain your plots and a discussion of the results, also comparing your observations to the theoretical time complexity.
Explanation / Answer
You can generate the randon number from the code below.
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
const size_t size = 300000;
int main()
{
ofstream fout("random.dat", ios::binary);
srand(time(NULL));
int k;
for (size_t i = 0; i < length; i++)
{
k = rand(); //rand function is used to generate the random numbers.
fout.write((char*)&k, sizeof(k));
}
fout.close();
return 0;
}
Comparision code for insrtion sort, merge sort and qiuck sort.
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
long length = 1000;
const long max_size = 300000;
int list[maxsize];
void read()
{
ifstream fin("random.dat", ios::binary);
for (long i = 0; i < size; i++)
{
fin.read((char*)&list[i], sizeof(int));
}
fin.close();
}
void MergeSort()
{
int temp;
for(long i = 0; i < size; i++)
{
for(long j = 0; j < size-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 < size; 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 (size = 1000; size <= max_size; )
{
cout << " Length : " << size << ' ';
read();
t1 = clock();
MergeSort();
t2 = clock();
cout << "Merge Sort : " << (t2 - t1)/CLK_TCK << " sec "; //Timing calculation for mergesort
read();
t1 = clock();
insertionSort();
t2 = clock();
cout << "Insertion Sort : " << (t2 - t1)/CLK_TCK << " sec "; timing calculatin for insertion sort
read();
t1 = clock();
quickSort(0, length - 1);
t2 = clock();
cout << "Quick Sort : " << (t2 - t1)/CLK_TCK << " sec "; //timing calculation for quicksort.
switch (size) . //testcase length switcher.
{
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;
}
This program needs random.dat file. To generate the random.date file, the code is in the begining of the answer.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.