please!!
- Answer The Questions Using The Information I Provided Please In Lab1 We Are Reading A File That Contains About 10 000 1 (156.5 KiB) Viewed 20 times
integers. Here is some of the integers.
Lab1_data.txt:
- Answer The Questions Using The Information I Provided Please In Lab1 We Are Reading A File That Contains About 10 000 2 (45.12 KiB) Viewed 20 times
3761695
4074926
5469210
7788553
7280943
4789072
3728526
1885390
7023103
1255160
1234365
5257074
6198972
7084052
791808
179239
644012
1004805
1678598
6253504
9627653
4096366
Lab1.cpp code in text:
#include <iostream>
#include <fstream>
#include <ctime>
#include <chrono>
using namespace std;
//COMBINES SORTED ARRAY TOGETHER AFTER
void combine(int * array, int left, int middle, int right);
//RECURSIVE MERGE SORT FUNCTION
void auxMergeSort(int * array, int startIndex, int
endIndex);
//PRINTS THE ARRAY
void print(int * array, int size);
//RECURSIVE FUNCTION TO GO THROUGH ARRAY
bool sortHelper(int * array, int index);
//CHECKS IF SORTED
bool check(int * array);
//USER FUNCTION TELLS IF CHECK RETURNS TRUE OR FALSE
bool flgIsSorted(int * array);
//SWITCHES TWO THINGS IN ARRAY
void exchange(int * first, int * second);
//QUICKSORT RECRUSIVE FUNCTION
void auxQuickSort(int * array, int startIndex, int
endIndex);
//QUICKSORT ALGORITHM THAT PARTITION ARRAY
int partition(int * array, int startIndex, int endIndex);
double takeTime(clock_t c1, clock_t c2);
//THE MAX AMOUNT OF ITEMS POSSIBLE
const int max_size = 10000000;
int main()
{
//DYNAMIC ARRAY THAT WILL HOLD VALUES FROM FILE
int * array = new int[max_size];
ifstream file;
file.open("lab1_data.txt");
//CHECKS IF FILE EXISTS
if(!file)
{
cerr << "Not a valid file" << endl;
return 0;
}
int num = 0;
int index = 0;
//KEEPS GOING UNTIL IT REACHES END OF THE FILE
while(!file.eof())
{
file >> array[index];
index++;
//HOW MANY NUMBERS TO INPUT
if(index == 2000000)
{
break;
}
}
int arraySize = index-1;
cout << "\nBefore applying sort: ";
flgIsSorted(array);
int input = 0;
do
{
cout << "\n1 for mergesort 2 for quicksort" << endl
<< "Input: ";
cin >> input;
if(input == 1)
{
//WHERE THE TIME STARTS
auto start = chrono::steady_clock::now();
auxMergeSort(array, 0, arraySize - 1);
//WHERE THE TIME ENDS
auto end = chrono::steady_clock::now();
double totalTime = double(chrono::duration_cast
<chrono::nanoseconds>(end - start).count());
cout << "\nTime taken in milliseconds was: " <<
totalTime/1000000 << endl;
break;
}
else if(input == 2)
{
//WHERE THE TIME STARTS
auto start = chrono::steady_clock::now();
auxQuickSort(array, 0, arraySize - 1);
//WHERE THE TIME ENDS
auto end = chrono::steady_clock::now();
double totalTime = double(chrono::duration_cast
<chrono::nanoseconds>(end - start).count());
cout << "\n The Time taken in milliseconds was: " <<
totalTime/1000000 << endl;
break;
}
else
{
cout << "\nInvalid input try again\n";
}
}
while(input != 2 || input !=1);
cout << "\nThe array after sorting algorithm is\n\n";
cout << "\nAfter applying sort: \n\n";
flgIsSorted(array);
print(array, arraySize);
return 0;
}
//FUNCTION THAT MERGES ARRAY TOGETHER
void merge(int * array, int left, int middle, int right)
{
int i, j, k;
int first = middle - left + 1;
int second = right - middle;
//CREATE TEMP ARRAYS
int L[first], R[second];
for (i = 0; i < first; i++)
//PUTS DATA INTO ARRAYS
L = array[left + i];
for (j = 0; j < second; j++)
R[j] = array[middle + 1+ j];
//RESET INDEX VALUES
i = 0;
j = 0;
k = left;
while (i < first && j < second)
{
//CHECK IF VALUE IN LEFT IS LESS OR SAME AND RIGHT
if (L <= R[j])
{
array[k] = L;
i++;
}
else
{
array[k] = R[j];
j++;
}
k++;
}
while (i < first)
{
array[k] = L;
i++;
k++;
}
while (j < second)
{
array[k] = R[j];
j++;
k++;
}
}
void auxMergeSort(int * array, int startIndex, int endIndex)
{
if (startIndex < endIndex)
{
int middle = startIndex +(endIndex-startIndex)/2;
//SORTING TWO ARRAYS
auxMergeSort(array, startIndex, middle);
auxMergeSort(array, middle+1, endIndex);
//CALL MERGE FUNCTION TO ATTACH ARRAYS BACK
merge(array, startIndex, middle, endIndex);
}
}
void print(int * array, int size)
{
int i;
for (i=0; i < 100; i++)
cout << array << " ";
cout << endl << endl;
}
//DOES THE WORK FOR CHECKING
bool sortHelper(int * array, int index)
{
if(sizeof(array) - index < 2)
{
return true;
}
//CHECKS IF VALUE IS GREATER THAN SUCCESSOR
else if(array[index] > array [index + 1])
{
return false;
}
return sortHelper(array, index + 1);
}
bool flgIsSorted(int * array)
{
//USER UTILITY FUNCTION
if(check(array) == true)
{
cout << "Array is sorted (checked with
flgIsSorted)\n";
return true;
}
else
{
cout << "Array is not sorted (checked with
flgIsSorted)\n";
return false;
}
}
bool check(int * array)
{
if(sortHelper(array, 0) == true)
{
return true;
}
else
{
return false;
}
}
void exchange(int * first, int * second)
{
//TEMP VARIABLE TO HOLD ONE OF THE ELEMENTS
int a = *first;
*first = *second;
*second = a;
}
void auxQuickSort(int * array, int startIndex, int endIndex)
{
if(startIndex < endIndex)
{
//Q CATCHES RETURN VALUE OF PARTITION
int q = partition(array, startIndex, endIndex);
//RECURSIVE CALLS ON THE FIRST AND SECOND HALF
auxQuickSort(array, startIndex, q-1);
auxQuickSort(array, q+1, endIndex);
}
}
int partition(int * array, int startIndex, int endIndex)
{
int m = (startIndex + endIndex)/2;
exchange(&array[m], &array[endIndex]);
int x = array[endIndex];
int i = startIndex - 1;
for (int j = startIndex; j <= endIndex - 1; j++)
{
if(array[j] <= x)
{
i++;
exchange(&array, &array[j]);
}
}
exchange(&array[i + 1], &array[endIndex]);
return (i + 1);
}
7. Use your Labl’s read method for data. Then write a recursive O(nlog n) non-destructive divide-and- conquer algorithm to list the largest 10 elements of the data you read, and listing them in decreasing order as the output. Again, starts with 1,000 and increases at 10x until it needs to read more than 10 million numbers. Output the execution time of your approach. DO NOT SORT the array first!!! [Hint: modify your mergesort's merge part.] 8. Test your result by calling one of your sorting algorithms to sort the data first and display largest numbers in decreasing order as the output. Output the execution time of your approach that sort the array first. 9. Run your code for 5 and 6 three times, record the execution time in milliseconds for each run on each size, enter the milliseconds reading into an Excel spreadsheet, calculate the average execution time in milliseconds for each run on each size and display your results in both a table and as a line chart. 10. Write a half to one page report to explain your execution time observation and discuss the problem solving approach you applied for step 5. Is it DP, greedy algorithm, or divide-and-conquer? It is possible that your answer is that it is has more than one.
1 NP 2 3 4 5 6 7 8 9 10 11 3761695 4074926 5469210 7788553 7280943 4789072 3728526 1885390 7023103 1255160 1234365 5257074 6198972 7084052 791808 179239 644012 1004805 1678598 6253504 9627653 4096366 12 13 14 15 16 17 18 19 20 21 22