5 ms·
Shouldn't that be: 1. $10 1. $10 3. $8 The way I see it, the person with $8 is ranked third, not second. Think of what would happen if you extended it.
by SimonPStevens 16y ago
Shouldn't that be:
1. $10
1. $10
3. $8
The way I see it, the person with $8 is ranked third, not second.
Think of what would happen if you extended it. If you had 99 people earning $10 and 1 earning $8, it would be misleading to rank that bottom individual 2nd.
- landhar 16y agoYou are absolutely right, that was more what I was thinking about when I wrote that. I just edited it to match with your proposal.
- btrask 16y agoFor what it's worth, this is quite easy to compute in a way that works with any number of ties, and doesn't require computing the whole list in order. Your rank is the number of people above you plus one.
- Retric 16y agoI must be missing something. That's a N^2 operation on an unsorted list. ~N Log N if you sort it first. And N to insert a new entry to a sorted list.
- btrask 16y agoYes, it requires a sorted list, but so does the naïve implementation. The performance is equivalent to binary search to find the entry, although you then have to scan backwards to make sure you have the first entry with the same value. Since performance is probably not an issue for most rankings, the biggest benefit is a clear, easy to remember definition, which should reduce the chances of making the same mistake landhar did.
- Retric 16y agoIf you are inserting 3 into an indexed and sorted list (1,2,4,5) you can calculate the index of 3 in O(Log N). But you also need to update the index of 4, and 5 which is an O(N) operation.
- deleted 16y ago[deleted]
- deleted 16y ago[deleted]