Below are my codes, small.txt file, and the output that needs to be printed. Thank you! #include #include #include #include using namespace std; class Employee { public: //Instantiate string name; int id; int age; string job; int year; //Constructors Employee() { name = ""; job = ""; age = year = id = 0; } Employee(string name, int id, int age, string job, int year) { this->name = name; this->id = id; this->age = age; this->job = job; this->year = year; } }; Employee data(string line) { string input; stringstream ss(line); string name; string job; int id; int age; int year; getline(ss, name, '|'); getline(ss, input, '|'); id = atoi(input.c_str());//convert the int to string getline(ss, input, '|'); age = atoi(input.c_str());//convert the int to string getline(ss, job, '|'); getline(ss, input, '\n'); year = atoi(input.c_str());//convert the int to string Employee emp(name, id, age, string(job), year); return emp; }; //Comparison Counter int ctr; void maxHeapify(Employee arr[], int size, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < size && arr[left].id > arr[largest].id) { largest = left; ctr++; } if (right < size && arr[right].id > arr[largest].id) { largest = right; ctr++; } if (largest != i) { swap(arr[i], arr[largest]); maxHeapify(arr, size, largest); } } void buildMaxHeap(Employee arr[], int size) { for (int i = size / 2 - 1; i >= 0; i--) { maxHeapify(arr, size, i); } } void printResult(Employee arr[], int size) { for (int m = 0; m < size; m++) { cout << arr[m].id << (m + 1 == size ? "\n" : " "); } } void heapSort(Employee arr[], int size) { //print before building max heap printResult(arr, size); buildMaxHeap(arr, size); //print after building max heap printResult(arr, size); for (int i = size - 1; i > 0; i--) { swap(arr[0], arr[i]); maxHeapify(arr, i, 0); printResult(arr, size); } } int main(int argc, char const* argv[]) { //Catches error conditions Check if filename included as parameter if (argc != 2) { cout << "You need to include a filename on the command line.\n"; return -1; } string filename = string(argv[1]);//Fetches the file name fstream file(filename, ios::in); //Catches error conditions Check if file exist if (!file) { cout << "Error opening file: " << filename << endl; return -1; } int size; string input;//store the inputs or the lines from the file file >> size; getline(file, input);//read the entire file line by line Employee* employees = new Employee[size]; for (int i = 0; i < size; ++i) { getline(file, input); employees[i] = data(input); } heapSort(employees, size); cout << "It took " << ctr << " comparisons to sort this list.\n"; file.close(); return 0; } small.txt file 10 Antharion Buxyho|10|31|Engineer|2020 Molly Nyxujijo|2|42|Custodian|2016 Grubbo Totexyca|9|47|Tester|2011 Thriff Cosapeka|7|24|Technician|2019 Grubbo Neferele|6|61|Director|1995 Borphee Rozuzy|5|23|Director|2019 Jeearr Heposiko|1|32|Engineer|2012 Krill Dodepo|4|48|Physicist|1997 Mumbo Muveze|8|27|Physicist|2019 Rezrov Zapefaty|3|44|Bookkeeper|2008 Output that should be printed. 10 2 9 7 6 5 1 4 8 3 10 8 9 7 6 5 1 4 2 3 9 8 5 7 6 3 1 4 2 10 8 7 5 4 6 3 1 2 9 10 7 6 5 4 2 3 1 8 9 10 6 4 5 1 2 3 7 8 9 10 5 4 3 1 2 6 7 8 9 10 4 2 3 1 5 6 7 8 9 10 3 2 1 4 5 6 7 8 9 10 2 1 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 It took 62 comparisons to sort this list.
Hey, i'm try to doing the HeapSort
Below are my codes, small.txt file, and the output that needs to be printed. Thank you!
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
using namespace std;
class Employee {
public:
//Instantiate
string name;
int id;
int age;
string job;
int year;
//Constructors
Employee() {
name = "";
job = "";
age = year = id = 0;
}
Employee(string name, int id, int age, string job, int year) {
this->name = name;
this->id = id;
this->age = age;
this->job = job;
this->year = year;
}
};
Employee data(string line) {
string input;
stringstream ss(line);
string name;
string job;
int id;
int age;
int year;
getline(ss, name, '|');
getline(ss, input, '|');
id = atoi(input.c_str());//convert the int to string
getline(ss, input, '|');
age = atoi(input.c_str());//convert the int to string
getline(ss, job, '|');
getline(ss, input, '\n');
year = atoi(input.c_str());//convert the int to string
Employee emp(name, id, age, string(job), year);
return emp;
};
//Comparison Counter
int ctr;
void maxHeapify(Employee arr[], int size, int i)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < size && arr[left].id > arr[largest].id) {
largest = left;
ctr++;
}
if (right < size && arr[right].id > arr[largest].id) {
largest = right;
ctr++;
}
if (largest != i) {
swap(arr[i], arr[largest]);
maxHeapify(arr, size, largest);
}
}
void buildMaxHeap(Employee arr[], int size) {
for (int i = size / 2 - 1; i >= 0; i--) {
maxHeapify(arr, size, i);
}
}
void printResult(Employee arr[], int size) {
for (int m = 0; m < size; m++)
{
cout << arr[m].id << (m + 1 == size ? "\n" : " ");
}
}
void heapSort(Employee arr[], int size)
{
//print before building max heap
printResult(arr, size);
buildMaxHeap(arr, size);
//print after building max heap
printResult(arr, size);
for (int i = size - 1; i > 0; i--) {
swap(arr[0], arr[i]);
maxHeapify(arr, i, 0);
printResult(arr, size);
}
}
int main(int argc, char const* argv[])
{
//Catches error conditions Check if filename included as parameter
if (argc != 2) {
cout << "You need to include a filename on the command line.\n";
return -1;
}
string filename = string(argv[1]);//Fetches the file name
fstream file(filename, ios::in);
//Catches error conditions Check if file exist
if (!file) {
cout << "Error opening file: " << filename << endl;
return -1;
}
int size;
string input;//store the inputs or the lines from the file
file >> size;
getline(file, input);//read the entire file line by line
Employee* employees = new Employee[size];
for (int i = 0; i < size; ++i)
{
getline(file, input);
employees[i] = data(input);
}
heapSort(employees, size);
cout << "It took " << ctr << " comparisons to sort this list.\n";
file.close();
return 0;
}
small.txt file
10
Antharion Buxyho|10|31|Engineer|2020
Molly Nyxujijo|2|42|Custodian|2016
Grubbo Totexyca|9|47|Tester|2011
Thriff Cosapeka|7|24|Technician|2019
Grubbo Neferele|6|61|Director|1995
Borphee Rozuzy|5|23|Director|2019
Jeearr Heposiko|1|32|Engineer|2012
Krill Dodepo|4|48|Physicist|1997
Mumbo Muveze|8|27|Physicist|2019
Rezrov Zapefaty|3|44|Bookkeeper|2008
Output that should be printed.
10 2 9 7 6 5 1 4 8 3 10 8 9 7 6 5 1 4 2 3 9 8 5 7 6 3 1 4 2 10 8 7 5 4 6 3 1 2 9 10 7 6 5 4 2 3 1 8 9 10 6 4 5 1 2 3 7 8 9 10 5 4 3 1 2 6 7 8 9 10 4 2 3 1 5 6 7 8 9 10 3 2 1 4 5 6 7 8 9 10 2 1 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 It took 62 comparisons to sort this list.
Step by step
Solved in 2 steps
