For each algorithm, implement the functions that take an array of integers and t

ID: 3755922 • Letter: F

Question

For each algorithm, implement the functions that take an array of integers and the size of the array and then sort it in ascending order. Add counters to count the number of key comparisons and the number of data moves during sorting. For the quick sort algorithm, you are supposed to take the first element of the array as the pivot. 3Find Sum of an Array Elements in both merge sort and guick sort Find the sum of all odd numbers in given range in both merge sort and gquick sort 5 Write a main function to measure the time required by each sorting algorithm. To this end, and after each sorting algorithm to measure the elapsed time in milliseconds. use the library function clockO, which is defined in time.h. Invoke the clock) library function before

Explanation / Answer

You have not mentioned in which language do I need to write the code.

I am choosing c++ program/ Please comment below for any queries regarding the program or any modifications needed to the code. Thank you.

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>

using namespace std;

long lengt = 1000;
const long maximum_len = 300000;

int listData[maximum_len];

void read()
{
ifstream fiin("random.dat", ios::binary);
for (long i = 0; i < lengt; i++)
{
fiin.read((char*)&listData[i], sizeof(int));
}
fiin.close();
}

void bubbleSort()
{
int temporary;
for(long i = 0; i < lengt; i++)
{
for(long j = 0; j < lengt-i-1; j++)
{
if (listData[j] > listData[j+1])
{
temporary = listData[j];
listData[j] = listData[j+1];
listData[j+1] = temporary;
}
}
}
}

void insertionSort()
{
int temporary;
for(long i = 1; i < lengt; i++)
{
temporary = listData[i];
long j;
for(j = i-1; j >= 0 && listData[j] > temporary; j--)
{
listData[j+1] = listData[j];
}
listData[j+1] = temporary;
}
}

long partition(long leftt, long rightt)
{
int pivot_ele = listData[leftt];
int lb = leftt, ub = rightt;
int temporary;

while (leftt < rightt)
{
while(listData[leftt] <= pivot_ele)
leftt++;
while(listData[rightt] > pivot_ele)
rightt--;
if (leftt < rightt)
{
temporary = listData[leftt];
listData[leftt] = listData[rightt];
listData[rightt] = temporary;
}
}
listData[lb] = listData[rightt];
listData[rightt] = pivot_ele;
return rightt;
}

void quickSort(long leftt, long rightt)
{
if (leftt < rightt)
{
long pivot = partition(leftt, rightt);
quickSort(leftt, pivot-1);
quickSort(pivot+1, rightt);
}
}

int main()
{
double tim1, tim2;

for (lengt = 1000; lengt <= maximum_len; )
{
cout << " Length : " << lengt << ' ';

read();
tim1 = clock();
bubbleSort();
tim2 = clock();
cout << "Bubble Sort : " << (tim2 - tim1)/CLK_TCK << " sec ";

read();
tim1 = clock();
insertionSort();
tim2 = clock();
cout << "Insertion Sort : " << (tim2 - tim1)/CLK_TCK << " sec ";

read();
tim1 = clock();
quickSort(0, lengt - 1);
tim2 = clock();
cout << "Quick Sort : " << (tim2 - tim1)/CLK_TCK << " sec ";

switch (lengt)
{
case 1000 :
lengt = 5000;
break;
case 5000 :
lengt = 10000;
break;
case 10000 :
lengt = 50000;
break;
case 50000 :
lengt = 100000;
break;
case 100000 :
lengt = 200000;
break;
case 200000 :
lengt = 300000;
break;
case 300000 :
lengt = 300001;
break;
}
}

return 0;
}

Navigate

For each algorithm below, indicate the running time using the simplest and most

For each analysis, use the following steps to write a complete description of re

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

For each algorithm, implement the functions that take an array of integers and t

Question

Explanation / Answer

Related Questions

Navigate