+1 678 648 4277 

Sorting and Storing Algorithm using C++ Homework Solution


Sorting Height and Storing in Binary Tree Assignment

Algorithm

The file describes a line of N students standing in a row. Each line of the file gives the name of a student and their integer height. We’ll be implementing the algorithm that sweeps downward. In particular, the main steps are:-

Read the input into a vector, where the string part is a student’s name and the int part is their height

Build a second vector, where the first part is height and the second part is their index

Sort the contents of this second vector (in order by height)

For each student in decreasing order of height

Add a student to a balanced BST keyed on the index (a set)

For each student, call the find method to get an iterate pointing to their record in the set.

Solution:

#include < iostream> #include < vector> #include < set> #include < cstdlib> using namespace std; int main() { vector> students; string data; getline(cin, data); while(!data.empty()) { students.emplace_back(data.substr(0, data.find(' ')), stoi(data.substr(data.find(' ') + 1, data.size()))); getline(cin, data); } vector> heightsByIndex; for(int i = 0; i < students.size(); i++) { heightsByIndex.emplace_back(students[i].second, i); } sort(heightsByIndex.begin(), heightsByIndex.end()); set bstOfIndex; int maxDiff = 0; int prevIndex = 0; int nextIndex = 0; for(int i = heightsByIndex.size() - 1; i >= 0; i--) { bstOfIndex.insert(heightsByIndex[i].second); set::iterator pos = bstOfIndex.find(heightsByIndex[i].second); if(pos != bstOfIndex.begin()) { int diff = abs(*pos - *prev(pos, 1)); if(maxDiff < diff) { maxDiff = diff; prevIndex = *pos; nextIndex = *prev(pos, 1); } } if(next(pos, 1) != bstOfIndex.end()) { int diff = abs(*pos - *next(pos, 1)); if(maxDiff < diff) { maxDiff = diff; prevIndex = *pos; nextIndex = *next(pos, 1); } } } cout << "Longest sight : " << maxDiff << endl << "People : " << students[prevIndex].first << " and " << students[nextIndex].first << endl; }