Problem 1: Write a program to complete insertion sort and merge sort , compare t
ID: 3671924 • Letter: P
Question
Problem 1:
Write a program to complete insertion sort and merge sort, compare their performance by measuring the time consumed for each sorting algorithm:
1. Generate an integer array of size 100 by random number generator for the two sorting algorithm; integer should be the range of [0,1000], print out the array
2. Write the two sorting algorithms as functions, take the generated array as input parameters. First use insertion sort, then merge sort, compute the time consuming for different algorithm. After merge sort, the original array should be rewritten by sorted array (Implement this by reference or pointer, do not assign values after sorting) Print out time consuming for different algorithm and print the sorted array in you main function.
3. Loop step 1~2 ten times to get average time of both algorithms, print out the average time consuming.
4.You may need function clock() in <ctime> library to measure the time, print out the time consumed for each algorithm in milliseconds.
Explanation / Answer
********Try this code for all sorting methods and their performance time************
#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();
mergeSort();
t2 = clock();
cout << "merge 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;
}
This includes the randon file
#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;
}