CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 14 of 14
  1. #1
    Join Date
    Mar 2007
    Posts
    155

    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.

  2. #2
    Join Date
    Apr 1999
    Posts
    27,449

    Re: Ranking integers in an Array

    Quote 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

  3. #3
    Join Date
    May 2006
    Location
    Norway
    Posts
    1,709

    Re: Ranking integers in an Array

    Quote 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..

  4. #4
    Join Date
    Apr 1999
    Posts
    27,449

    Re: Ranking integers in an Array

    Quote 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

  5. #5
    Join Date
    Mar 2007
    Posts
    155

    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....

  6. #6
    Join Date
    Mar 2007
    Posts
    155

    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}.

  7. #7
    John E is offline Elite Member Power Poster
    Join Date
    Apr 2001
    Location
    Manchester, England
    Posts
    4,835

    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

  8. #8
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,721

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

  9. #9
    Join Date
    May 2006
    Location
    Norway
    Posts
    1,709

    Re: Ranking integers in an Array

    Quote 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

  10. #10
    Join Date
    Apr 1999
    Posts
    27,449

    Re: Ranking integers in an Array

    Quote 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

  11. #11
    John E is offline Elite Member Power Poster
    Join Date
    Apr 2001
    Location
    Manchester, England
    Posts
    4,835

    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

  12. #12
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,721

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

  13. #13
    Join Date
    Mar 2007
    Posts
    155

    Re: Ranking integers in an Array

    Quote 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

  14. #14
    Join Date
    Mar 2007
    Posts
    155

    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
  •  





Click Here to Expand Forum to Full Width

Featured