Homework Soursefirst algorithm AlgorithmMaxsubSlowA Input An nelement array
first algorithm
AlgorithmMaxsubSlow(A): Input: An n-element array A of numbers, indexed from 1 to n. Output: The maximum subarray sum of array A. m 0 // the maximum found so far for j 1to n do for k j to n do s 0 // the next partial sum we are computing for i j to k do s s + A[i]if s>mthen m sreturn m
second algorithm
AlgorithmMaxsubFaster(A): Input: An n-element array A of numbers, indexed from 1 to n. Output: The maximum subarray sum of array A. S0 0 // the initial prex sum for i 1to n do Si Si1 + A[i]m 0 // the maximum found so farfor j 1to n do for k j to n do s = Sk Sj1 if s>mthen m sreturn m
third algorithm
AlgorithmMaxsubFastest(A): Input: An n-element array A of numbers, indexed from 1 to n. Output: The maximum subarray sum of array A. M0 0 // the initial prex maximum for t 1to n do Mt max{0,M t1 + A[t]}m 0 // the maximum found so farfor t 1to n do m max{m, Mt}return m
Write Java program to implement these three algorithms
Choose values of n = 1000; 5000; 10,000; 20,000; 50,000; 100,000
Assign random numbers between 25 to +25 as array values. To generate random numbers in the range of min to max, use the expression randomNum = min + Math.random() * (max – min)
Measure the time taken by the three algorithms, and plot the results
Submit your programs and a report with your time measurements, the time analysis and BigOh analysis of the three algorithms. Verify that your analysis matches the experimental observations. Include the experimental validation in your report.
Solution
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
long length = 1000;
const long max_length = 100000;
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\\t: \" << length << \'\ \';
read();
t1 = clock();
bubbleSort();
t2 = clock();
cout << \"Bubble Sort\\t: \" << (t2 - t1)/CLK_TCK << \" sec\ \";
read();
t1 = clock();
insertionSort();
t2 = clock();
cout << \"Insertion Sort\\t: \" << (t2 - t1)/CLK_TCK << \" sec\ \";
read();
t1 = clock();
quickSort(0, length - 1);
t2 = clock();
cout << \"Quick Sort\\t: \" << (t2 - t1)/CLK_TCK << \" sec\ \";
switch (length)
{
case 1000 :
length = 5000;
break;
case 5000 :
length = 10000;
break;
case 10000 :
length = 20000;
break;
case 20000 :
length = 50000;
break;
case 50000 :
length = 100000;
break;
case 100000 :
length = 100001;
break;
}
}
return 0;
}
