Server Help :: View topic - Ranking/sorting algorithm?

Server Help

Bot Questions - Ranking/sorting algorithm?

tansey - Thu Mar 03, 2005 12:28 am
Post subject: Ranking/sorting algorithm?

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 - Thu Mar 03, 2005 1:15 am
Post subject:

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 - Thu Mar 03, 2005 2:31 am
Post subject:

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

Bak - Thu Mar 03, 2005 9:29 am
Post subject:

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).

Mr Ekted - Thu Mar 03, 2005 9:50 am
Post subject:

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)

Bak - Thu Mar 03, 2005 12:28 pm
Post subject:

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

Mr Ekted - Thu Mar 03, 2005 12:46 pm
Post subject:

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 - Thu Mar 03, 2005 3:44 pm
Post subject:

Mr Ekted wrote:

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

Here is a good list of which sorts are stable and which are not.

Maverick - Thu Mar 03, 2005 4:37 pm
Post subject:

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

Mr Ekted - Thu Mar 03, 2005 6:03 pm
Post subject:

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