Write down a recurrence relation for this version of QuickSort, and solve it asymp-totically. Show your work. Assume that the ti
1 answer:
You might be interested in
Answer:
Here is the C++ program:
#include <iostream> //to use input output functions
#include <fstream> //to manipulate files
using namespace std; //to identify objects like cin cout
int main(){ //start of main function
ifstream file; //creates an object of ifstream
file.open("random.txt"); //open method to open random.txt file using object file of ifstream
int numCount = 0; //to store the number of all numbers in the file
double sum = 0; //to store the sum of all numbers in the file
double average = 0.0; //to store the average of all numbers in the file
int number ; //stores numbers in a file
if(!file){ //if file could not be opened
cout<<"Error opening file!\n"; } //displays this error message
while(file>>number){ //reads each number from the file till the end of the file and stores into number variable
numCount++; //adds 1 to the count of numCount each time a number is read from the file
sum += number; } //adds all the numbers and stores the result in sum variable
average = sum/numCount; //divides the computed sum of all numbers by the number of numbers in the file
cout<<"The number of numbers in the file: "<<numCount<<endl; //displays the number of numbers
cout<<"The sum of all the numbers in the file: "<<sum<<endl; //displays the sum of all numbers
cout<<"The average of all the numbers in the file: "<< average<<endl; //displays the average of all numbers
file.close(); } //closes the file
Explanation:
Since the random.txt is not given to check the working of the above program, random.txt is created and some numbers are added to it:
35
48
21
56
74
93
88
109
150
16
while(file>>number) statement reads each number and stores it into number variable.
At first iteration:
35 is read and stored to number
numCount++; becomes
numCount = numCount + 1
numCount = 1
sum += number; this becomes:
sum = sum + number
sum = 0 + 35
sum = 35
At second iteration:
48 is read and stored to number
numCount++; becomes
numCount = 1+ 1
numCount = 2
sum += number; this becomes:
sum = sum + number
sum = 35 + 48
sum = 83
So at each iteration a number is read from file, the numCount increments to 1 at each iteration and the number is added to the sum.
At last iteration:
16 is read and stored to number
numCount++; becomes
numCount = 9 + 1
numCount = 10
sum += number; this becomes:
sum = sum + number
sum = 674 + 16
sum = 690
Now the loop breaks and the program moves to the statement:
average = sum/numCount; this becomes:
average = 690/10;
average = 69
So the entire output of the program is:
The number of numbers in the file: 10 The sum of all the numbers in the file: 690 The average of all the numbers in the file: 69
The screenshot of the program and its output is attached.
