Sorting vector of objects

[graceful tapir]

I have a class and a function that calculates a number based on various attributes of an object in the class
I want to sort a vector made up of objects from that class based on how high that number is.

I've made a basic bubble sort algorithm for it, but am currently calling the function that calculates the number twice per time through the for loop (once for each object getting checked). What suggestions would you have to optimize this as it's doing a whole ton of unnecessary work? Here's my thoughts of solutions that might work, but I'm not sure how I'd implement either:

1. make that number calculated just a member variable. issue: not sure how to make sure the number is recalculated before running the sorting algorithm as that number changes throughout the course of the code and the sorter can be run at (essentially) any time

2. calculate all the numbers first, then sort the numbers, and relate them to the object they were calculated from. issue: not sure how to relate them. I've done a bit of python and think I'd approach this problem with a dictionary, but not sure how I'd do this.

I'm happy to provide code if helpful, but if there's a conceptual answer I'll happily take it even if it means a bit of work on my part to figure out how to implement on my specific situation. Also sorry if my terminology is inconsistent/off, I'm in a c++ class and we only just learned about classes. Open to any other suggestions of how to approach this if mine are "bad" XD

[buoyant breach]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

[graceful tapir]

please ping reply, I might be unavailable for a bit today as I have classes, but will respond when able!

[swift owl]

So your function decides if one class is greater than the other or something?

or it evaluates your class to a numeric value?

[graceful tapir]

oh sorry, it should be "various attributes of the object". Think of it like a student's grades where each course's grade is a member variable and the function calculates the gpa (and within the rest of the program the user can change student's grades, and the hope is the sorter can sort the students based on gpa)

that's not exactly what I'm coding but a pretty synonymous analogy

essentially right now my sorter code is:

vector<Student> sort(vector<Student> vec){
    for(int i = 0; i < vec.size(); i++){
        for(int j = 0; j < vec.size()-i; j++){
            int a = vec[j].gpa_calc();
            int b = vec[j+1].gpa_calc();
            if (a > b){
                Student hold = vec[j];
                vec[j] = vec[j+1];
                vec[j+1] = hold;
            }          
        }
    }
    return vec;
}

[swift owl]

Yeah it sounds like you actually just want to overload operator<

and check if vec[j] < vec[j+1]

that makes your code look cleaner, but you cant avoid calling gpa_calc(), this is the simplest way i think

[graceful tapir]

hmm okay, that feels super slow since the gpa_calc() involves a for loop as well, but ig it's unavoidable :(

I'll make the a/b change tho :P

oh I have an idea

one min

[swift owl]

maybe if there is something obvious to check first

[graceful tapir]

yeah I think this'll work, I made a member variable "gpa", then modified the function gpa_calc to just update gpa instead of returning the integer gpa. Then before the sorter run a for loop of all the students, doing gpa_calc to all, then in the if statement just doing if(vec[j}.gpa > vec[j+1].gpa)

so essentially the first solution I proposed but actually working lol

[swift owl]

well that works too

thats how you can save performance, instead of calculation, you use and update some state

[graceful tapir]

I think it's a lower time complexity? Still running the for loop in gpa_calc for every student, but now only once/student rather than once/student/time it's in a pair that's checked

it still won't run through on my computer (at least it's been trying to go for a minute or so and hasn't outputted my calculation) but I think that's probably an issue somewhere else?

[swift owl]

well i have no clue how you implemented it and what you are trying to achieve

[graceful tapir]

yeah, I don't want to modify the original as it holds important data. Really more precicely what's happening is I'm calculating the presumed "best possible gpa" a student could have if they did well in their other classes, but keeping their original/real grades is important

I'll send in a question later if I can't figure out why it's taking so long to run lol

[swift owl]

okay, and what errors are you getting?

[graceful tapir]

none, it's just still "running"

I'll add in some couts here and there to see where it's getting stuck

anyway thanks for help! I'll open something else up if I can't figure out how to fix new problem XD