Server Help

[tansey]

I have a list of stats for players in a txt file. The format is name:stat1:stat2:...:statn:rating:rank such that the players are ranked by their rating, with higher ratings corresponding to lower rankings (rating of 1000 may be ranked #1 where 999 would be #2, etc). The stats are updated after the event is run and therefore the list is in random order.

Can anyone think of a good way to sort/rank the players in the file that's better than (n^2)*logn?

--tansey

[Mine GO BOOM]

Quicksort or Mergesort. Will do it in n * log n. If those sources don't help you, google will find source code for you.

[tansey]

right, i was assuming that i would use quicksort in my analysis.....

[Bak]

if you use STL, you can use the sort() function (#include <algrothim>, hybrid quick/heap sort) or load them into a list and call list.sort (mergesort).
_________________
SubSpace Discretion: A Third Generation SubSpace Client

[Mr Ekted]

Note that neither quicksort nor mergesort are stable. That is, they do not preserve the order of equal items. So if you want a list sorted by two things, you can't simply sort by the second, then sort again by the first. Make your compare function check for both "keys" simultaneously.

Code: Show/Hide (a1 > a2) || (a1 == a2 && b1 > b2)

_________________
4,691 irradiated haggis!

[Bak]

merge sort is stable, and in fact stl's stable_sort function uses merge sort

[Mr Ekted]

Well, it might depend on which implementation then I suppose. I never did make sense to me why merge sort wouldn't be stable.

[Mine GO BOOM]

[Maverick]

Yea.. as Mr. Ekted said.. Better to write your own. I did a few times too; simple for loop comparing chars.
_________________

Nickname: Maverick (I changed my name!)
TWCore developer | Subspace statistics

[Mr Ekted]

I didn't say write your own. I always use qsort() and implement the compare such that the sort is stable.