Sorting problem

Posted By: NITRO777

Sorting problem - 08/07/10 23:39

Hello,
I am trying to sort some randomly generated player turns and then correctly assign them and also make sure there are no repetitions. I will show what I mean below:

I have randomly generated 4 numbers for players from the code below, my goal is that the player with the highest number gets to go first, the player with the second highest number goes next, etc. etc.

Code:

function turns()
{
	random_seed(0);
	player1_turn = integer(random(100));
	turn_array[0] = player1_turn;
	
	player2_turn = integer(random(100));
	turn_array[1] = player2_turn;
		
	player3_turn = integer(random(100));
	turn_array[2] = player3_turn;
		
	player4_turn = integer(random(100));
	turn_array[3] = player4_turn;
}

Next I have sorted the data with a reverse bubble sort like this:

Code:

////////simple bubble sort///////
var i;
var j;
var hold;
	
for (i=0; i<7; i++) //passes
{
 for (j=0; j<7; j++) //one pass
 {
	if (turn_array[j] < turn_array[j+1]) //one comparison 
	{
	 hold = turn_array[j];   //one swap
	 turn_array[j] = turn_array[j+1];
	 turn_array[j+1] = hold;
				
	}
  }
 }

All of this code works successfully, my 4 generated numbers are sorted from highest to lowest. But I still have two problems:

#1 PROBLEM is that I need to assign the turn order to the respective players

#2 PROBLEM I don't know how to deal with situations where I have two of the same numbers like if 2 "45"'s show up.

So I was hoping there was a way to fix one or both of these problems in an efficient manner, but any help or directions at all would be excellent.

Let me know if I didn't describe the problem clearly.

Thanks

Posted By: ventilator

Re: Sorting problem - 08/08/10 00:36

there is a solution to your second problem in this thread:

http://www.opserver.de/ubb7/ubbthreads.p...true#Post320572

Posted By: NITRO777

Re: Sorting problem - 08/08/10 02:24

Hi,
Thanks thats an interesting method I haven't seen before but it makes the game slightly unfair if the first number chosen is the highest no one else will ever get a chance to get that number.

What I was hoping for is a solution which allows for repetition of the same numbers, but if that occurs will allow them to try again specifically against each other, then re-sort them in order.

Then I still need a way to assign the turn order to the structure or entity which generated it.

The players themselves will probably just be structs and the turn order number will just be a data member of that particular struct. Unless I can think of a better way of doing it with arrays or perhaps I will make each one an entity and store it's turn order in a skill?

Anyway, thanks for the input I definitely learned a new method.

Posted By: MrGuest

Re: Sorting problem - 08/08/10 02:42

Originally Posted By: NITRO777

Hi,
Thanks thats an interesting method I haven't seen before but it makes the game slightly unfair if the first number chosen is the highest no one else will ever get a chance to get that number.

That's slightly flawed logic. Each player has the same chance of going 1st.

i)Imagine 3 players,

PLAYER A picks from 1 2 or 3, he has 33.333r% chance of picking any number, we'll choose 3 (highest) to demonstrate.

Once he's picked 3, PLAYER B and PLAYER C still have an equal chance of going next (50%).

If PLAYER B picks 2, this now leaves PLAYER C with 1, going last (unfair? no).

Use this logic backwards now.

If PLAYER A picks 1, B and C now have 50% chance of going 1st, increasing both of their odds.

If PLAYER B now picks 2 again, this guarantees PLAYER C going 1st even though both times he hasn't picked and has the same chance the whole way through.

ii) imagine 13 players with a suit of cards.

There's 1/13 chance of getting the ace for each player.

If PLAYER 1 draws the ace, everyone still thinks they have the same chance of drawing the ace until it's actually revealed, just because they're not going 1st doesn't lower their chances of getting it.

Trawl the internet for 'Progressive Probability' for more examples.

Originally Posted By: NITRO777

Then I still need a way to assign the turn order to the structure or entity which generated it.

When I made a turnbased game, I initially thought too that you'll then need to change the turns. but that's the reason why you're generating the initial turn?

Originally Posted By: NITRO777

The players themselves will probably just be structs and the turn order number will just be a data member of that particular struct. Unless I can think of a better way of doing it with arrays or perhaps I will make each one an entity and store it's turn order in a skill?

For storing whose turn it is, just have an integer array, which saves each position from the initial randomisation. Then just ++ through the array until the end.

You can also assign this number to a skill for each entity, then reference it to make sure they're moving the right pieces.

Hope this helps

Posted By: NITRO777

Re: Sorting problem - 08/08/10 12:14

Quote:

That's slightly flawed logic. Each player has the same chance of going 1st.

Ahh that is interesting. I did look online and it appears that it is called "conditional probability" and most closely models situations such as drawing straws. After studying your post and others online I now see the logic of it, thanks.