In C++ : You will write a program that compares the execution time of several so
ID: 3835791 • Letter: I
Question
In C++
: You will write a program that compares the execution time of several sorting algorithms, and displays the results as a table
· You will be sorting arrays of 100000 integers
· The integers must be randomly generated.
· Each sorting algorithm will use the same array
· The sorting algorithms to be used are:
o Selection
o Insertion
o Quick
o Modified Quicksort (size 30)
o Radix
§ You were not given the code for this algorithm, you must actually write it
o Heap
§ You were not given the code for this algorithm, you must actually write it
§ You may NOT use the heap in the STL
· The comparisons should be done on 5 different arrays, and the average execution time should be displayed
· Each algorithm will be called in a function, and each function definition will be template
· Each function template will be in a separate header file
Internal documentation is required :
Explanation / Answer
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
long length = 100000;
const long max_length = 100000;
int array[100000];
void generate()
{
srand((unsigned)time(0));
for(int i=0; i<length; i++){
array[i] = (rand()%100)+1;
}
}
void bubbleSort()
{
int temp;
for(long i = 0; i < length; i++)
{
for(long j = 0; j < length-i-1; j++)
{
if (array[j] > array[j+1])
{
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
void insertionSort()
{
int temp;
for(long i = 1; i < length; i++)
{
temp = array[i];
long j;
for(j = i-1; j >= 0 && array[j] > temp; j--)
{
array[j+1] = array[j];
}
array[j+1] = temp;
}
}
long partition(long left, long right)
{
int pivot_element = array[left];
int lb = left, ub = right;
int temp;
while (left < right)
{
while(array[left] <= pivot_element)
left++;
while(array[right] > pivot_element)
right--;
if (left < right)
{
temp = array[left];
array[left] = array[right];
array[right] = temp;
}
}
array[lb] = array[right];
array[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 << ' ';
generate();
t1 = clock();
bubbleSort();
t2 = clock();
cout << "Bubble Sort : " << (t2 - t1)/CLK_TCK << " sec ";
generate();
t1 = clock();
insertionSort();
t2 = clock();
cout << "Insertion Sort : " << (t2 - t1)/CLK_TCK << " sec ";
generate();
t1 = clock();
quickSort(0, length - 1);
t2 = clock();
cout << "Quick Sort : " << (t2 - t1)/CLK_TCK << " sec ";
}
}