Jump to content
  • Advertisement
Sign in to follow this  
agisler

Sort array index by highest value

This topic is 2632 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello,

So I am creating a function that will return an array of indexes sorted by there value. I have written the code but it only works for a max array size of 8. I would like the method to be able to sort any array size. My code as of right now works great but I feel it could be greatly improved, there is a of code being duplicated. I am just not sure how I can optimize the code.

[source]


private int[] ArrayShift(int[] array,int startingPoint)
{
for (int i = startingPoint; i > 0; --i)
{
array = array[i - 1];
}

return array;
}


private int[] ArrayMaxValue(int[] array)
{
int[] arrayRanks = new int[8] {-1,-1,-1,-1,-1,-1,-1,-1};

int[] stack = new int[8];

for (int Index = 0; Index < array.Length; Index++)
{
if (array[Index] > 0)
{
if (array[Index] >= array[stack[0]])
{
stack=ArrayShift(stack,7); //shift the array down from highest index;
stack[0] = Index;
arrayRanks = ArrayShift(arrayRanks,7);
arrayRanks[0] = array[Index];
continue;
}
if ((array[Index] <= arrayRanks[0]) && (array[Index] >= arrayRanks[1]))
{
stack = ArrayShift(stack, 6);
stack[1] = Index;
arrayRanks = ArrayShift(arrayRanks, 6);
arrayRanks[1] = array[Index];
continue;
}
if ((array[Index] <= arrayRanks[1]) && (array[Index] >= arrayRanks[2]))
{
stack = ArrayShift(stack, 5);
stack[2] = Index;
arrayRanks = ArrayShift(arrayRanks, 5);
arrayRanks[2] = array[Index];
continue;
}
if ((array[Index] <= arrayRanks[2]) && (array[Index] >= arrayRanks[3]))
{
stack = ArrayShift(stack, 4);
stack[3] = Index;
arrayRanks = ArrayShift(arrayRanks, 4);
arrayRanks[3] = array[Index];
continue;
}
if ((array[Index] <= arrayRanks[3]) && (array[Index] >= arrayRanks[4]))
{
stack = ArrayShift(stack, 3);
stack[4] = Index;
arrayRanks = ArrayShift(arrayRanks, 3);
arrayRanks[4] = array[Index];
continue;
}
if ((array[Index] <= arrayRanks[4]) && (array[Index] >= arrayRanks[5]))
{
stack = ArrayShift(stack, 2);
stack[5] = Index;
arrayRanks = ArrayShift(arrayRanks, 2);
arrayRanks[5] = array[Index];
continue;
}
if ((array[Index] <= arrayRanks[5]) && (array[Index] >= arrayRanks[6]))
{
stack = ArrayShift(stack, 1);
stack[6] = Index;
arrayRanks = ArrayShift(arrayRanks, 1);
arrayRanks[6] = array[Index];
continue;
}
if ((array[Index] <= arrayRanks[6]) && (array[Index] >= arrayRanks[7]))
{

stack[7] = Index;

arrayRanks[7] = array[Index];
continue;
}

}
}


return stack;

}

[/source]

Thanks for the help.

agisler

Share this post


Link to post
Share on other sites
Advertisement
I'd go with:

1. Create an array of array indices: { 0, 1, 2, ...}.

2. Sort that array, using a standard sort algorithm like std::sort(), but with a custom comparison function that looks up the values for the two indices in the other array and compares those values.

Share this post


Link to post
Share on other sites
Maybe there is something I don't know but I thought the C# sort function only sorted the values not the indexes. In my case the indexes relate to players within the game and the value within the index relate to the players score. So what I need is the index of the player from highest to smallest.


Adam could you pleas elaborate a bit more?

Many thanks for the replies

agisler

Share this post


Link to post
Share on other sites
I'm not that familiar with C# so I'm guessing a bit here.

What you need is a custom comparison function like the one you can get by using this sort function. http://msdn.microsoft.com/en-us/library/bzw8611x.aspx

That custom function should look something like:

[source]public class ArrayIndexComparer : IComparer<int>
{
public int[] values; // Set this to your array of values before use

public int Compare(int x, int y)
{
// Compare the values of the ints at the given array indexes
int v1 = values[x];
int v2 = values[y];
if (v1 < v2) return -1;
if (v1 > v2) return 1;
return 0;
}
}[/source]

Obviously the array of values should be changed to hold players in your case.

You use that to sort your array of indices.

Share this post


Link to post
Share on other sites

So I am creating a function that will return an array of indexes sorted by there value. I have written the code but it only works for a max array size of 8.
[/quote]
Does it work for arrays of size less than 8? It also doesn't handle negative values.

And is maybe broken when the array size is exactly 8. =]

int [] array = {26, 58, 71, 3, 80, 3, 45, 37};
int [] result = ArrayMaxValue(array);
// result is {4, 4, 4, 2, 6, 7, 0, 0}

Unit tests are great for catching such cases. The next time you're writing such an algorithm, I highly recommend writing some unit tests, preferably first. It is very easy to write tests that test what the code does after the fact, rather than what it should be doing. Writing tests first means that you aren't influenced by how you'll solve the problem.


I would like the method to be able to sort any array size.
[/quote]
Great! In programming, there are generally three cases, none, one or many. You rarely want to support some arbitrary N, if it can be avoided.


My code as of right now works great but I feel it could be greatly improved, there is a of code being duplicated.
[/quote]
Well, as mentioned before it doesn't work, but yes we can remove the duplication from your algorithm.


I am just not sure how I can optimize the code.
[/quote]
Using the standard library will use a superior algorithm.

[hr]
Here is how you might approach improving the current algorithm, if it hypothetically was correct. As I'm sure you're aware, all the conditions have the same basic shape, with the exception of the first and last. You just copied and pasted the conditions and changed the values. The values are related to the "index" of the particular condition into the block of conditions.

Let us look at the 3[sup]rd[/sup] "element" of the conditional array:

if ((array[Index] <= arrayRanks[1]) && (array[Index] >= arrayRanks[2]))
{
stack = ArrayShift(stack, 5);
stack[2] = Index;
arrayRanks = ArrayShift(arrayRanks, 5);
arrayRanks[2] = array[Index];
continue;
}

We're treating the conditionals as an (0 based) array, this block of code is then the 3[sup]rd[/sup] element - and is at index 2. We want to generalise this logic, so it could be used from index 0 to index 7. The problems are the "magic numbers" - 1, 2 and 5 in this code.

We can immediately see that the magic number "2" can be replaced by an index variable. What about 1? Well, it appears to be examining the previous element of arrayRanks. So that would be index - 1.

Finally, 5. We want to shift the array "up" to make room for the elements. We have filled indices 0..index already. We are just about to fill arrayRanks[index] now - that makes index + 1 elements logically filled. So we can use 8 - (index + 1) as a forumla that will give us the 5 elements we need to shift.

The only tricky part is dealing with the special cases. Well, we can note that index == 7 is not a special case - if we call ArrayShift(stack, 0) the array doesn't change. The only thing is when index == 0. From my above reasoning, you're trying to look at the previous element in the array. When index is 0, there is no previous element. So we just need to be careful to avoid testing this condition when index is 0.

Sometimes we can get rid of the special 0 case by doing a little extra setup outside the loop, and then looping from 1 to 8. I haven't really bothered to investigate this here because your algorithm is broken.

Now we just need to write a loop that will cover all the above conditions:

private static int[] GetSortedIndices(int[] array)
{
int[] arrayRanks = new int[8] {-1,-1,-1,-1,-1,-1,-1,-1};

int[] stack = new int[8];

for (int i = 0; i < array.Length; ++i)
{
int currentValue = array;
if (currentValue > 0)
{
for(int j = 0 ; j < 8 ; ++j)
{
int previous = j - 1;
if ((j == 0 || currentValue <= arrayRanks[previous]) && (currentValue >= arrayRanks[j]))
{
int remaining = 8 - (j + 1);
stack = ArrayShift(stack, remaining);
stack[j] = i;
arrayRanks = ArrayShift(arrayRanks, remaining);
arrayRanks[j] = currentValue;
break;
}
}
}
}

return stack;
}

I hope that makes some sense. Note we changed the "continue" to a "break". If you think about it, it has the same effect - it gets the outer loop to go to the next iteration.

We've removed duplication, what about allowing arbitrary sized arrays? Well, this one is easy: just remove the magic numbers by making everything relative to array.Length, instead of "8".

private static int[] GetSortedIndices(int[] array)
{
int length = array.Length;
int[] arrayRanks = new int[length];
int[] stack = new int[length];

for(int i = 0 ; i < length ; ++i)
{
arrayRanks = -1;
}

for (int i = 0; i < length; i++)
{
int currentValue = array;
if (currentValue > 0)
{
for(int j = 0 ; j < length ; ++j)
{
int previous = j - 1;
if ((j == 0 || currentValue <= arrayRanks[previous]) && (currentValue >= arrayRanks[j]))
{
int remaining = length - (j + 1);
stack = ArrayShift(stack, remaining);
stack[j] = i;
arrayRanks = ArrayShift(arrayRanks, remaining);
arrayRanks[j] = currentValue;
break;
}
}
}
}

return stack;
}

Voilà, ton algorithm sans duplication.

Now you know how it can be done. I'd recommend fixing this algorithm sometime, it would be a good exercise for you to practise on. Once you get it working: throw it away and use the built in sorting routines!

Share this post


Link to post
Share on other sites
Wow. Thanks so much. Seems so obvious with your demonstration and the way you walked through the problem.


[color="#1C2837"]Unit tests are great for catching such cases. The next time you're writing such an algorithm, I highly recommend writing some unit tests, preferably first. It is very easy to write tests that test what the code does after the fact, rather than what it should be doing. Writing tests first means that you aren't influenced by how you'll solve the problem.
[color="#1C2837"][/quote]

[color="#1c2837"]I can clearly see how doing unit tests can be so useful. It seemed like I was spending days finding one problem and then tweaking the code to get another problem. Was stuck in this endless loop. I did think I had the problem solved but I have clearly been dis-proven tongue.gif I will try to spend more time walking through the problem like you did in the future.


[color="#1C2837"]Using the standard library will use a superior algorithm.
[color="#1C2837"][/quote]

I have been learning about the IComparer and IComparable the last few days as Adam recommended. These library functions do seem quite handy. I was unaware of them until the post. :) I have spent most of my programming time learning C++, so I am just starting learn about all the library functions available.



[color="#1c2837"]Thanks once again for you help and time.

[color="#1c2837"]agisler

Share this post


Link to post
Share on other sites

Wow. Thanks so much. Seems so obvious with your demonstration and the way you walked through the problem
[/quote]
No worries, glad it helped.


I have spent most of my programming time learning C++, so I am just starting learn about all the library functions available.
[/quote]
I'm not sure if this implies you think that there is no equivalent in C++, or just that you're too used to using the C++ standard library. If the former, you should note that C++'s std::sort() accepts a custom comparator function/functor too - it defaults to using std::less<> as the comparator.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!