I need help to add comments throughout my C++ program below and I need a summary
ID: 3726269 • Letter: I
Question
I need help to add comments throughout my C++ program below and I need a summary touching base on these points to the best of your ability on answering them if you can please:
a) Overview of your program;
b) Usage manual of your program (how does a regular user uses your program?);
c) Test cases you have used to make your program fully functional and robust;
d) Potential improvements on your program (given more time, do you have any plan to make it better?);
#include<iostream>
#include<fstream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
//created insertionSort
void insertionSort(int array[],int n){
int i, key, j;
for (i= 1; i< n; ++i){
key= array[i];
j=i-1;
while (j >= 0 && array[j]>key){
array[j+1] = array[j];
j = j-1;
}
array[j+1] = key;
}
ofstream out("inputFile.txt");
for(i=0;i<n;++i)
out<<array[i]<<endl;
cout<<" Output file successful"<<endl;
out.close();
}
//Merge function of mergeSort.
void merge(int arr[], int l, int m, int r){
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++) {
L[i] = arr[l + i];
}
for (j = 0; j < n2; j++) {
R[j] = arr[m + 1+ j];
i = 0;
j = 0;
k = l;
}
while (i < n1 && j < n2){
if (L[i] <= R[j]){
arr[k] = L[i];
i++;
}
else{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1){
arr[k] = L[i];
i++;
k++;
}
while (j < n2){
arr[k] = R[j];
j++;
k++;
}
}
// Created mergeSort
void mergeSort(int arr[], int l, int r){
if (l < r){
int m = l+(r-l)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
// Swap function
void swap(int *a, int *b){
int x = *a;
*a = *b;
*b = x;
}
// Created a Partition function
int partition (int arr[], int low, int high){
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high- 1; j++){
if (arr[j] <= pivot){
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
// Created quickSort
void quickSort(int arr[], int low, int high){
if (low < high){
int z = partition(arr, low, high);
quickSort(arr, low, z - 1);
quickSort(arr, z + 1, high);
}
}
// Removes any duplicates from the array.
int noDuplicates(int array[], int n){
if (n==0 || n==1)
return n;
int j = 0;
for (int i=0; i < n-1; i++)
if (array[i] != array[i+1])
array[j++] = array[i];
array[j++] = array[n-1];
return j;
}
//Sorting the array
void countingSort(int *input, size_t num_elements) {
size_t max = *std::max_element(input, input+num_elements);
std::vector<size_t> counts(max+1);
for (int i=0; i<num_elements; i++)
++counts[input[i]];
int temp = input[0];
input[0] = input[num_elements-1];
int ntemp = input[num_elements-2];
input[num_elements-2] = temp;
input[num_elements-1] = ntemp;
}
//Main function
int main(int argc,char *argv[]){
int array[20],i=0,j,count=0,k;
ifstream input;
input.open(argv[1]);
if(input.fail()) {
cout<<"File is empty or does not exist";
}
else{
while(input.eof()==0){
input>>array[i];
i=i+1;
count=count+1;
}
string s;
cout << "Would you like to use the insertion, merge, quick or counting sort method?:";
cin >> s;
if(s==std::string("insert")){
insertionSort(array,count);
ofstream out("inputFile.txt");
for(i=0;i<count;++i){
out<<array[i]<<endl;
}
cout<<"Output file successful"<<endl;
out.close();
}
else if(s==std::string("quick")){
quickSort(array,0,count-1);
ofstream out("inputFile.txt");
for(i=0;i<count;++i){
out<<array[i]<<endl;
}
cout<<"Output file successful"<<endl;
out.close();
}
else if(s==std::string("merge")){
mergeSort(array,0,count);
ofstream out("inputFile.txt");
for(i=0;i<count;++i)
out<<array[i]<<endl;
cout<<"Output file successful"<<endl;
out.close();
}
else if(s==std::string("count")){
countingSort(array, count);
ofstream out("inputFile.txt");
for(i=0;i<count;++i){
out<<array[i]<<endl;
cout<<array[i]<<" ";
}
cout<<"Output file successful"<<endl;
out.close();
}
else{
cout<<"Choose either to use insertion, merge, quick or counting sort method";
}
}
return 0;
}
Explanation / Answer
Overview of the program:
This program implements insertion sort, merge sort, quick sort, and counting sort. It uses the sorting algorithms to sort a given set of numbers. A user could select one of the sorting algorithm given above and the program will sort according to the algorithm.
Usage Manual:
A regular user uses this program to sort a given set of numbers based on of the four algorithms. Three steps that the user should follow to sort a given set of numbers.
Step 1: store the given numbers in a text file. for example, save it in ‘ip.txt’.
Step 2: Run the program and give the filename as command line arguments. for example in Linux. ./a.out ip.txt
Step 3: Program asks for the user to select one of the sorting algorithms. A user should input one of
‘insert’ for insertion algorithm
‘merge’ for merge sort
‘quick’ for quick sort
‘count’ for counting sort
After you select of the algorithm, the program on the given input and produces the sorted numbers in a file ‘input.txt’.
Test Cases:
Create three files with the contents of each file as shown.
ip1.txt: “1”
ip2.txt: “5 4 3 1 2 6”
ip3.txt: “9383 886 2777 6915 7793 8335 5386 492 6649 1421 2362 27 8690 59 7763 3926 540 3426 9172 5736”
For each algorithm, we run these three files. So which gives us like 3*4=12 test cases.
Test Case
Run
input
1
./a.out ip1.txt
insert
2
./a.out ip1.txt
merge
3
./a.out ip1.txt
quick
4
./a.out ip1.txt
count
5
./a.out ip2.txt
insert
6
./a.out ip2.txt
merge
7
./a.out ip2.txt
quick
8
./a.out ip2.txt
count
9
./a.out ip3.txt
insert
10
./a.out ip3.txt
merge
11
./a.out ip3.txt
quick
12
./a.out ip3.txt
count
improvements in the above program:
In merge() function, you need to initialize the i=0,j=0,k=l outside the second for loop, but you are initializing inside the for loop
While you are calling the mergeSort() function in main function you were calling “mergeSort(array, 0, count), Instead you should call with mergeSort(array,0,count-1)
In count sort, The array is not completely sorted. So after you get the counts of each number into counts vector. you need to fill the input array with the sorted. In order to do it, you need to remove the following code
//
int temp = input[0];
input[0] = input[num_elements-1];
int ntemp = input[num_elements-2];
input[num_elements-2] = temp;
input[num_elements-1] = ntemp;
//
And add the following code:
int k=0;
for(int i=0;i<=max;i++){
for(int j=0;j<counts[i];j++)
input[k++] = i;
}
//Final Code after improvements
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
//created insertionSort
void insertionSort(int array[],int n){
int i, key, j;
//loop through all the elements
for (i= 1; i< n; ++i){
key= array[i]; //select the next element
j=i-1;
//Move all the elements greater than key,one
//positon ahead of the current position
while (j >= 0 && array[j]>key){
array[j+1] = array[j];
j = j-1;
}
//store the key in positon where all the elements [j+1...i-1] are greater than key
array[j+1] = key;
}
//create a file inputFile.txt and print to it
ofstream out("inputFile.txt");
for(i=0;i<n;++i)
out<<array[i]<<endl;
cout<<" Output file successful"<<endl;
out.close();
}
//Merge function of mergeSort.
//It is a helper function for merge sort
//inputs are array, start index, middle index, and the right most index
//middle index is used to split the array at that point
void merge(int arr[], int l, int m, int r){
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
//store the left half of the in the temperary array L
for (i = 0; i < n1; i++) {
L[i] = arr[l + i];
}
//store the right half of the array in the temporary array R
for (j = 0; j < n2; j++) {
R[j] = arr[m + 1+ j];
}
//intitalize the indexes
i = 0;
j = 0;
k = l;
//Compare the corresponding left and right values at indexes i,j
//Insert the least of L and R into the arr at index k
while (i < n1 && j < n2){
//top value of L is lesser then insert L[i]
//else insert R[j]
if (L[i] <= R[j]){
arr[k] = L[i];
i++;
}else{
arr[k] = R[j];
j++;
}
k++;
}
//copy the remaining elements of i...n1 into the array back
while (i < n1){
arr[k] = L[i];
i++;
k++;
}
//copy the remianing elements of j...n2 into the array back
while (j < n2){
arr[k] = R[j];
j++;
k++;
}
return;
}
// Created mergeSort
void mergeSort(int arr[], int l, int r){
if (l < r){
int m = l+(r-l)/2;
//calll the left of the function to get sorted
mergeSort(arr, l, m);
//call the right half of the function to get sorted
mergeSort(arr, m+1, r);
//once left and right are sorted, compare both and sort into the final array
merge(arr, l, m, r);
}
}
// Swap function
//used to swap two integers
void swap(int *a, int *b){
int x = *a;
*a = *b;
*b = x;
}
// Created a Partition function
//This function is a helper function to quick sort
//It takes input array, the left index and the right index
//It takes the value at right index as a pivot element and
//fits it in a correct position where the elements to the left of that position
//are lesser than the pivot and the elements to the right of the position are
//greater than the pivot
int partition (int arr[], int low, int high){
int pivot = arr[high]; //take the righmost element as pivot
int i = (low - 1);
//iterate from low to high and find the correct position
for (int j = low; j <= high- 1; j++){
//compare pivot and the current element and swap if current element is lesser than pivot
if (arr[j] <= pivot){
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
// Created quickSort
//It is the main function to call when using quickSort
//It's inputs are array, starting index and ending index
void quickSort(int arr[], int low, int high){
if (low < high){
//find the partition of the array with the last element as pivot
int z = partition(arr, low, high);
//sort the left half of pivot
quickSort(arr, low, z - 1);
//sort the right half of pivot
quickSort(arr, z + 1, high);
}
}
// Removes any duplicates from the array.
int noDuplicates(int array[], int n){
if (n==0 || n==1)
return n;
int j = 0;
for (int i=0; i < n-1; i++)
if (array[i] != array[i+1])
array[j++] = array[i];
array[j++] = array[n-1];
return j;
}
//Sorting the array
//Here we get the counts of each number
//Then insert back these numbers into the given array
void countingSort(int *input, size_t num_elements) {
size_t max = *std::max_element(input, input+num_elements);
std::vector<size_t> counts(max+1);
//Get the counts into counts vector
for (int i=0; i<num_elements; i++)
++counts[input[i]];
// int temp = input[0];
// input[0] = input[num_elements-1];
// int ntemp = input[num_elements-2];
// input[num_elements-2] = temp;
// input[num_elements-1] = ntemp;
//insert back the numbers into the array
int k=0;
for(int i=0;i<=max;i++){
for(int j=0;j<counts[i];j++)
input[k++] = i;
}
return;
}
//Main function
int main(int argc,char *argv[]){
int array[20],i=0,j,count=0,k;
ifstream input;
//open the file which is given as command line argument
input.open(argv[1]);
if(input.fail()) {
cout<<"File is empty or does not exist";
}else{
//read the full text file which contains integers
while(input.eof()==0){
input>>array[i];
i=i+1;
count=count+1;
}
//take the user input
string s;
cout << "Would you like to use the insertion, merge, quick or counting sort method?:";
cin >> s;
//compare it with "insert","quick","merge","count"
//If it matches call the corresponding function
//If it doesn't match print error
if(s==std::string("insert")){
insertionSort(array,count);
ofstream out("inputFile.txt");
for(i=0;i<count;++i){
out<<array[i]<<endl;
}
cout<<"Output file successful"<<endl;
out.close();
}else if(s==std::string("quick")){
quickSort(array,0,count-1);
ofstream out("inputFile.txt");
for(i=0;i<count;++i){
out<<array[i]<<endl;
}
cout<<"Output file successful"<<endl;
out.close();
}else if(s==std::string("merge")){
mergeSort(array,0,count-1);
ofstream out("inputFile.txt");
for(i=0;i<count;++i)
out<<array[i]<<endl;
cout<<"Output file successful"<<endl;
out.close();
}else if(s==std::string("count")){
countingSort(array, count);
ofstream out("inputFile.txt");
for(i=0;i<count;++i){
out<<array[i]<<endl;
cout<<array[i]<<" ";
}
cout<<"Output file successful"<<endl;
out.close();
}else{
cout<<"Choose either to use insertion, merge, quick or counting sort method";
}
}
return 0;
}
Test Case
Run
input
1
./a.out ip1.txt
insert
2
./a.out ip1.txt
merge
3
./a.out ip1.txt
quick
4
./a.out ip1.txt
count
5
./a.out ip2.txt
insert
6
./a.out ip2.txt
merge
7
./a.out ip2.txt
quick
8
./a.out ip2.txt
count
9
./a.out ip3.txt
insert
10
./a.out ip3.txt
merge
11
./a.out ip3.txt
quick
12
./a.out ip3.txt
count
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.