The objective of this assignment is to analyze the time complexities of four dif

Question

The objective of this assignment is to analyze the time complexities of four different sorting algorithms. The project has the following components: 1. Implement a random number generator function that can generate integer numbers between 1 and 20000. Duplicate numbers should not be allowed. You can make use of any of the random number generating available in C library, or you can write your own pseudo random number generating code 2. Implement algorithms for insertion sort, quick sort, heap sort, and merge sort. Given a choice between a recursive and an iterative version for a particular algorithm, you may choose either one. 3. Execute each sorting algorithm for the following different values of n, where n is the size of the list to be sorted n 100,500,1000,2000,5000,8000,10000. In each case, the list consists of random numbers generated in step 1. For a particular value of n, the same input data (ie., list to be sorted) should be given to all the sorting algorithms 4. For each value of n, and for each sorting algorithm, obtain the actual execution time of the algorithm for the machine you are using for the cases when a) an unsorted list is presented as the input data, and b) a sorted list is presented as the input data

Explanation / Answer

#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;
}

also download random.dat file from the given link

https://onedrive.live.com/?id=A976BCD81E2434BA%21116&cid=A976BCD81E2434BA

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.