Get largest value from array without sorting

Question

I am creating a somewhat simple game, and I need to keep track of what players have what score. 25 people will be playing this game at one time, these players will be put into an array:

public static int[] allPlayers = new int[25];

Depending on a correct answer, the current player will earn 100 points, let's say. So, if player 1 were up, the code would be something similar to the following:

allPlayers[0] += 100;

If player 3 were up, the code on a correct answer would be:

allPlayers[2] += 100;

At the end of the game, I want to determine which player has the accumulated the most amount of points. Please note that I cannot simply sort this array because I need the order of the array to remain intact. If the order is not left intact, I will not be able to tell which player had which points to his/her name.

I'm interested to hear what you all have to say and I look forward to your responses.

Thank you very much,

Evan

Solution 1

No need to sort, just iterate through the array, keeping track of the largest value seen so far and the index of that value.

  var largest = -1;
  var player = -1;
  for (var i = 0; i < allPlayers.Length; ++i)
  {
       if (allPlayers[i] > largest)
       {
           player = i;
           largest = allPlayers[i];
       }
  }

  Console.WriteLine( "Player {0} wins, with score {1}", player, largest );

Handling ties is left as an exercise.

Solution 2

Using Linq as an alternative if you wanted a ranking of possibly more than one player (a simple loop with keeping the index of the winning player is much more effective for the base case):

var player = allPlayers.Select((x, i) => new { Score = x, Player = i })
                       .OrderByDescending(x => x.Score)
                       .First();

Console.WriteLine("Player {0} wins with a score of {1}", player.Player, player.Score);

Solution 3

I'd like to be a LINQ purist and say that if you are using OrderByDescending, you're doing an O(NlogN) sort. Since max is an O(N) algorithm, we should be able to do better with LINQ. Here is my O(N) proposal for LINQ:

  var player=allPlayers.Select((x, i) => new {Score=x, Player=i})
    .Aggregate((self, next) => self.Score>=next.Score ? self : next);

  Console.WriteLine("Player {0} wins with a score of {1}", player.Player, player.Score);

Solution 4

Use

int max = maxplayers.Max()//linq extension method of [] int

see this post

View more solutions

Comments

[Admin]

I really like this approach! Thank you for this.

[Admin]

Is this sorting the array in any way as OrderByDescending suggests?

[BrokenGlass]

@Evan: No the array itself remains unchanged, the ordering is done on a separate enumeration

[Admin]

I know that I am being an absolute pain, and I have done some reading on the matter but I would be so grateful if you, or perhaps someone else who sees this comment could explain exactly what purpose the lambda operator is in this scenario? I would love to learn how to use this guy!

[BrokenGlass]

@Evan: You can read it as "goes to" - its basically an anonymous function that takes the input on the left and maps it to the output on the right. Also see msdn.microsoft.com/en-us/library/bb397687.aspx

[cwharris]

a lamba "function" is (in this specific instance) a shorthand delegate.