CODEWITHSUNDEEP
c#winformsarrays
user725913
user725913

Reputation:

Get largest value from array without sorting

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

Upvotes: 2

Views: 15190

Answers (8)

smoothe
smoothe

Reputation: 578

Use 

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

see this post

Upvotes: 1

Gio
Gio

Reputation: 41

You can keep a tracking wich player has the max value in all the process, in each increase you can review if the new value is bigger than the old value, so in this way you can to know wich player has the max value in any moment at the game.

private int maxPlayer = 0;
private int value = 0;

public void setIncrement(int player, int amount)
{
    allPlayer[player] += amount; 
    if(allPlayer[player] > value) 
    { 
        maxPlayer = player; 
        value =  allPlayer[player];
    }
}

public int getMaxPlayer()
{
return maxPlayer;
}

Upvotes: 0

Corey Kosak
Corey Kosak

Reputation: 2625

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

Upvotes: 3

cwharris
cwharris

Reputation: 18125

Using Linq:

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

Without Linq:

int score;
int player;

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

Upvotes: 0

Padu Merloti
Padu Merloti

Reputation: 3229

Just iterate throught it once as others have suggested. That's unavoidable,

UNLESS

You wrap your players array into an array and encapsulate the way to set player score. Then you can make the comparison when adding stuff to your list.

Upvotes: -1

BrokenGlass
BrokenGlass

Reputation: 160882

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

Upvotes: 3

tvanfosson
tvanfosson

Reputation: 532435

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.

Upvotes: 4

markdsievers
markdsievers

Reputation: 7309

If you are unable to sort or keep a parallel data structure that can do the sorting or keep a a reference to the largest value, you are going to have an O(n) algorithm.

Easiest way would be to keep a reference to the highest value inserted into the array.

Upvotes: 0

Related Questions