-
March 19th, 2007, 12:44 AM
#1
Ranking integers in an Array
Dear brothers,
I have been stuck up with a sorting and ranking algorithm.
For example, I have an array of integers, say
int array[5] = {4, 5, 1, 9, 3}.
I should rank the integers based on maximum value in the array. So I need rank like this,
{3, 2, 5, 1, 4}.
Ranking can be acheived by a sorting algorithm, but the elements will be sorted ascending or descending which is to be avoided.
At present I can forget about the ranking of repeated elements in the array.
-
March 19th, 2007, 04:13 AM
#2
Re: Ranking integers in an Array
Originally Posted by thomus07
Dear brothers,
I have been stuck up with a sorting and ranking algorithm.
For example, I have an array of integers, say
int array[5] = {4, 5, 1, 9, 3}.
I should rank the integers based on maximum value in the array. So I need rank like this,
{3, 2, 5, 1, 4}.
Maybe it's me, but can you please explain how you got those numbers given the original data?
Regards,
Paul McKenzie
-
March 19th, 2007, 04:18 AM
#3
Re: Ranking integers in an Array
Originally Posted by Paul McKenzie
Maybe it's me, but can you please explain how you got those numbers given the original data?
Regards,
Paul McKenzie
it means that 9 is the largest number, 5 the 2nd largest and so on..
-
March 19th, 2007, 04:21 AM
#4
Re: Ranking integers in an Array
Originally Posted by laitinen
it means that 9 is the largest number, 5 the 2nd largest and so on..
And what is the third largest number? It isn't '4', as this doesn't follow the pattern.
Regards,
Paul McKenzie
-
March 19th, 2007, 06:37 AM
#5
Re: Ranking integers in an Array
Thanks for all the comments...
Original data: int array[5] = {4, 5, 1, 9, 3}
I need: {3, 2, 5, 1, 4} (This ranking based on the maximum value)
Had I gone through a sorting of original array, I would have ranked very easily based on the array index. But the rank is also sorted (I mean in ascending).
In the above example, rank of 4 is 3...5 is 2 and so on....
-
March 19th, 2007, 06:42 AM
#6
Re: Ranking integers in an Array
Maybe it's me, but can you please explain how you got those numbers given the original data?
Regards,
Paul McKenzie
Yes, brother....
Original data (Just an example, I have different numbers in my program):
int array[5] = {4, 5, 1, 9, 3}.
The array I need (rank based on maximum value): {3, 2, 5, 1, 4}.
-
March 19th, 2007, 07:25 AM
#7
Re: Ranking integers in an Array
Basically, you need to produce an intermediate array between your original array and your final array. Let's call them array, intermediate_array and final_array. The intermediate array needs to contain the numbers in descending order (in your case, this would be int intermediate_array[5] = {9, 5, 4, 3, 1} ). I'll assume that you can write some code to sort the numbers into descending order. Given the first 2 arrays, you now need to compare them and produce a final array, depending upon the results of the comparision.
Something like this:-
Code:
int array[5] = {4, 5, 1, 9, 3};
int intermediate_array[5] = {9, 5, 4, 3, 1}; // Let's assume that you sorted them somehow
int final_array[5];
for (int x=0; x<5; x++)
{
int ranked_number = array[x];
for (int y=0; y<5; y++)
if (intermediate_array[y] == ranked_number)
final_array[y] = x+1;
}
I haven't tested it but I think that final_array would contain {3, 2, 5, 1, 4}
Of course, this might depend on not having duplicate entries....
[Edit...] Oops sorry, doesn't work. I need a re-think
Sorry, I got array and intermediate_array mixed up. The final code should look like this:-
Code:
int array[5] = {4, 5, 1, 9, 3};
int intermediate_array[5] = {9, 5, 4, 3, 1}; // Let's assume that you sorted them somehow
int final_array[5];
for (int x=0; x<5; x++)
{
int ranked_number = intermediate_array[x];
for (int y=0; y<5; y++)
if (array[y] == ranked_number)
final_array[y] = x+1;
}
Last edited by John E; March 19th, 2007 at 07:48 AM.
"A problem well stated is a problem half solved.” - Charles F. Kettering
-
March 19th, 2007, 07:51 AM
#8
Re: Ranking integers in an Array
There are a number of ways to do this. The most straightforward
would have a complexity of O(N*N). If you use extra arrays,
you can get this down to O( N*LOG(N)).
1) create 2 arrays, and index array and a rank array (both of the same
size as the original).
2) set the index array = {0,1,2,3,4} ... write your code to "sort" the
index array, except at the comparison stage, compare using the
original array, and switch the index array instead of the original.
3) set rank[index[i]] = i + 1
Here is an example using standard C++ library ... you probably are
supposed to write your own sorting algorithm
Code:
#include <iostream>
#include <algorithm>
using namespace std;
int array[5] = {4, 5, 1, 9, 3};
bool IndexPredicate(int lhs , int rhs)
{
return array[ lhs ] > array[ rhs] ;
}
int main()
{
int i;
int index_array[5];
int rank[5];
for (i=0; i<5; ++i) index_array[i] = i;
sort(index_array,index_array+5,IndexPredicate);
for (i=0; i<5;++i)
{
rank[index_array[i]] = i+1;
}
for (i=0; i<5; ++i)
cout << rank[i] << "\n";
return 0;
}
-
March 19th, 2007, 10:14 AM
#9
Re: Ranking integers in an Array
Originally Posted by Paul McKenzie
And what is the third largest number? It isn't '4', as this doesn't follow the pattern.
Isn't it? What is the 3rd largest number?
Laitinen
-
March 19th, 2007, 01:04 PM
#10
Re: Ranking integers in an Array
Originally Posted by laitinen
Isn't it? What is the 3rd largest number?
Laitinen
Sure, 4 is the third largest number, but from what has been posted, the resulting array is nowhere near what I'm believing the answer should be.
If the original array is {4, 5, 1, 9, 3}, then the "order" array should yield {4, 2, 1, 5, 3} as the positions of the numbers in descending order.
Position Element
4 -> 9
2 -> 5
1 -> 4
5 -> 3
3 -> 1
That is assuming that the order array is 1 based. Show me what I'm not getting here.
Regards,
Paul McKenzie
-
March 19th, 2007, 01:15 PM
#11
Re: Ranking integers in an Array
Paul, the original post is quite ambiguous but the way I read it was that the final array should give the numbers in 'magnitude of largeness', rather than 'position of largeness'. In other words:-
Code:
4 -> third highest number -> 3
5 -> second highest number -> 2
1 -> fifth highest number -> 5
9 -> highest number -> 1
3 -> fourth highest number -> 4
"A problem well stated is a problem half solved.” - Charles F. Kettering
-
March 19th, 2007, 02:44 PM
#12
Re: Ranking integers in an Array
Paul's answer is the "usual" sorted index answer (in the code that I
posted, it is my index_array ... except my array is zero-based).
The final ordinal rank (which I think the OP wanted), is straight-forward
to arrive at (see the rank array in the code that I posted).
-
March 20th, 2007, 12:27 AM
#13
Re: Ranking integers in an Array
Originally Posted by Paul McKenzie
Sure, 4 is the third largest number, but from what has been posted, the resulting array is nowhere near what I'm believing the answer should be.
That is assuming that the order array is 1 based. Show me what I'm not getting here.
Regards,
Paul McKenzie
Thanks brother for your comments.
sorry,I really did'nt get you. Any way I beleive with what John has replied...
I need the rank based on maximum value in any of the index of the whole array... rather the maximum index....
I repeat what John has told...
Re: Ranking integers in an Array
--------------------------------------------------------------------------------
Paul, the original post is quite ambiguous but the way I read it was that the final array should give the numbers in 'magnitude of largeness', rather than 'position of largeness'. In other words:-
Code:
4 -> third highest number -> 3
5 -> second highest number ->2
1 -> fifth highest number -> 5
9 -> highest number -> 1
3 -> fourth highest number ->4
-
March 21st, 2007, 12:39 AM
#14
Re: Ranking integers in an Array
Dear brothers,
I am pleased with the effort taken by you all. I am benefited with what John has given. Also another genuine approach given by Philip is appreciable. In addition, I thank for the pain you all have taken in writing the code, reading and sparing your time. I think the problem is resolved with needing a little concern about the repeated entries in the array.
Any future readers can refer to the post given by Paul and Philip.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|