highscore sorting

So i am making a highscore program, so i need ur thought about the sorting
this is my plan:
When we get a new score, we start for the top of the score and when we get to the place where the new score is higher than the score on that place, we put the new score on that place and all scores below (including the score on that place) are getting shifted down and the last one gets thrown out of the list
This way every time we get a new score we have O(n) in the big O notation.
So what do guys think, is this ony good?
I'd say it depends on what is your container for the scores.

For example :
If it's a multimap, just insert your score and everithing will be done automatically
If it's an array/vector with random access, use dichotomy to find its place and shift all the following scores before inserting it
What's wrong with just appending the highscore to a vector or list and then sorting it with std::sort?

EDIT: actually, if you use a list, you can just look for the place to insert the new value, insert it, and then remove the last one.
Last edited on
well, my container are 2 arrays, 1 for the score and 1 for the name (yes, i know i should have put them in a class and then have an rray of those classes, but i got my reasons), and i dont really want to use vectors or lists because i alrdy started it like i did and i want to do the sorting and all that by myself

and why should i use dichotomy?

Because dichotomy should find the score position faster on average, but that's maybe not important in your case (if you have a small quantity of scores for example)
oh when u said dichotomy i thought u meant something else, but i see now how it should work, im not exactly sure at the moment how to implement it but i will look into it, thx .
and i plan to let the user choose the number of scores, so yes, it is important because the maximum is a little (relativ) less of maximum number that can hold unsinged int
Last edited on
Topic archived. No new replies allowed.