QUES 1. Write a program to compare insertion sort and merge sort.
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
long length = 1000;
const long max_length = 1000000;
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 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;
}
}
void mergesort(long low,long mid,long high) {
int t[100000];
long i,j,k;
i=low;
j=mid+1;
k=low;
while((i<=mid) && (j<=high)) {
if(list[i]>=list[j])
t[k++]=list[j++];
else
t[k++]=list[i++];
}
while(i<=mid)
t[k++]=list[i++];
while(j<=high)
t[k++]=list[j++];
for(i=low;i<=high;i++)
list[i]=t[i];
}
void msortdiv(long low,long high) {
long mid;
if(low!=high) {
mid=((low+high)/2);
msortdiv(low,mid);
msortdiv(mid+1,high);
mergesort(low,mid,high);
}
}
int main()
{ double t1, t2;
for (length = 1000; length <= max_length; ) {
cout << "\nLength\t: " << length << '\n';
read();
t1 = clock();
msortdiv(0, length - 1);
t2 = clock();
cout << "mergesort\t: " << (t2 - t1)/CLK_TCK << " sec\n";
read();
t1 = clock();
insertionSort();
t2 = clock();
cout << "Insertion Sort\t: " << (t2 - t1)/CLK_TCK << " sec\n";
switch (length){
case 1000 :
length = 10000;
break;
case 10000 :
length = 100000;
break;
case 100000 :
length = 1000000;
break;
case 1000000 :
length = 10000001;
break;
}
}
return 0;
}
RUNNING TIME OF INSERTION SORT AND MERGE
SORT
Input
1000
10000
100000
1000000
Merge
Insertion sort
sort
0.003
0.28
24.995
1016.4
0.005
0.035
0.308
0.453
INSERTION VS MERGE SORT
1200
1000
800
TIME ( in seconds)
Insertion sort
600
mergesort
400
200
0
1000
10000
100000
INPUT (N)
1000000
QUES 2. Write a program to compare insertion sort and improvised
insertion sort.
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
long length = 1000;
const long max_length = 1000000;
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 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;
}
}
int binarySearch(int item, int low, int high) {
if (high <= low)
return (item > list[low])? (low + 1): low;
int mid = (low + high)/2;
if(item == list[mid])
return mid+1;
if(item > list[mid])
return binarySearch(item, mid+1, high);
return binarySearch(item, low, mid-1);
}
// Function to sort an array a[] of size 'n'
void binaryinsertion()
{
int i, loc, j, k, selected;
for (i = 1; i < length; ++i) {
j = i - 1;
selected = list[i];
// find location where selected sould be inseretd
loc = binarySearch(selected, 0, j);
// Move all elements after location to create space
while (j >= loc) {
list[j+1] = list[j];
j--;
}
list[j+1] = selected;
}
}
int main()
{
double t1, t2;
for (length = 1000; length <= max_length; ) {
cout << "\nLength\t: " << length << '\n';
read();
t1 = clock();
insertionSort();
t2 = clock();
cout << "Insertion Sort\t: " << (t2 - t1)/CLK_TCK << " sec\n";
read();
t1 = clock();
binaryinsertion();
t2 = clock();
cout << "Improved version 1\t: " << (t2 - t1)/CLK_TCK << " sec\n";
switch (length) {
case 1000 :
length = 10000;
break;
case 10000 :
length = 100000;
break;
case 100000 :
length = 1000000;
break;
case 1000000 :
length = 10000001;
break;
}
}
return 0;
}
RUNNING TIME OF INSERTION SORT AND MERGE
SORT
Improved
Insertion sort
Input
1000
insertion
0.04
0.03
10000
0.272
0.226
10000
0
10000
00
22.852
16.297
1011.1
950.6
Insertion sort and improved insertion sort
1200
1000
800
Time (in seconds)
Insertion sort
600
Improved insertion sort
400
200
0
1000
10000
100000
INPUT (N)
1000000
QUES 3. Write a program to compare quick sort with randomized quick
sort.
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
long count=0;
long length = 1000;
const long max_length = 1000000;
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(); }
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) {
count++;
temp
= list[left];
list[left] = list[right];
list[right] = temp;
} }
list[lb] = list[right];
list[right] = pivot_element;
return right; }
int r_partition(long p,long r) {
long i=p+rand()%(r-p+1);
long temp;
temp=list[r];
list[r]=list[i];
list[i]=temp;
count++;
return partition(p,r);
}
void quickSort(long left, long right) {
if (left < right)
{
long pivot = partition(left, right);
quickSort(left, pivot-1);
quickSort(pivot+1, right);
} }
void r_quickSort(long left, long right) {
if (left < right)
{
long pivot = r_partition(left, right);
quickSort(left, pivot-1);
quickSort(pivot+1, right);
} }
int main() {
double t1, t2;
for (length = 1000; length <= max_length; ) {
cout << "\nLength\t: " << length << '\n';
count=0;
read();
t1 = clock();
quickSort(0, length - 1);
t2 = clock();
cout << "Quick Sort running time\t: " << (t2 - t1)/CLK_TCK << " sec\n";
cout<<"Exchanges:"<<count<<"\n";
count=0;
read();
t1 = clock();
r_quickSort(0, length - 1);
t2 = clock();
cout << "Randomized Quick Sort running time\t: " << (t2 - t1)/CLK_TCK << "
sec\n";
cout<<"Exchanges:"<<count<<"\n";
switch (length) {
case 1000 :
length = 10000;
break;
case 10000 :
length = 100000;
break;
case 100000 :
length = 1000000;
break;
case 1000000 :
length = 10000001;
break;
} }
return 0; }
RUNNING TIME OF QUICK SORT AND RANDOMIZED
QUICK SORT
Input
Quick sort
1000
10000
100000
1000000
Randomized quick sort
1739
24634
319425
3453887
1740
24649
319268
3334843
Quick sort VS randomized quick sort
Number of exchanges
4000000
3500000
3000000
2500000
2000000
1500000
1000000
500000
0
Quick sort
Randomized quick sort
INPUT (N)
