How does one rank an array (sort) by value? *With a twist*

By : Ed.
Source: Stackoverflow.com
Question!

I need to take an array and sort it in c/c++, replacing each value with its' "rank", an integer that corresponds to its position after sort. Heres an example: Input: 1,3,4,9,6. Output: 1, 2, 3, 5, 4. So, I need to replace each value with its position relative to all the other values. I hope that makes sense, but its late, so who knows :p.

Edit: I am using a shell sort procedure, and duplicates' ranks are arbitrarily chosen, based on which came first in the original array.

Update:

Despite my best efforts, I havent been able to implement a sort algorithm that sorts an array of pointerse by the values they point to. Could someone please tell me whats going wrong? The current example wont compile, and I've changed it around so much that it doesnt really matter. I'd very much appreciate it if someone could help me fix this!

void SortArray( int ** pArray, int ArrayLength ) {

    int i, j, flag = 1;    // set flag to 1 to begin initial pass
    int * temp;    // holding variable orig with no *
    for(i = 1; (i <= ArrayLength) && flag; i++)
    {
        flag = 0;
        for (j=0; j < (ArrayLength -1); j++)
        {
            if (*pArray[j+1] > *pArray[j])    // ascending order simply changes to <
            { 
                &temp = &pArray[j];    // swap elements
                &pArray[j] = &pArray[j+1];    //the problem lies somewhere in here
                &pArray[j+1] = &temp;
                flag = 1;    // indicates that a swap occurred.
            }
        }
    }
};
By : Ed.


Answers

create a new Array and use bubble sort to rank the elements

int arr[n];
int rank[n];
 for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
       if(arr[i]>arr[j])
         rank[i]++;

The rank of each element will be rank[i]+1 to be in the order of 1,2,....n

By : aravinth


Parallel sorting of vector using boost::lambda...

   std::vector<int> intVector;
   std::vector<int> rank;

   // set up values according to your example...
   intVector.push_back( 1 );
   intVector.push_back( 3 );
   intVector.push_back( 4 );
   intVector.push_back( 9 );
   intVector.push_back( 6 );


   for( int i = 0; i < intVector.size(); ++i )
   {
      rank.push_back( i );
   }

   using namespace boost::lambda;
   std::sort( 
              rank.begin(), rank.end(),
              var( intVector )[ _1 ] < var( intVector )[ _2 ] 
            );

   //... and because you wanted to replace the values of the original with 
   //    their rank
   intVector = rank;

Note: I used vectorS instead of arrays because it is clearer/easier, also, I used C-style indexing which starts counting from 0, not 1.

By : paxos1977


Ok, here is my atempt in C++

#include <iostream>
#include <algorithm>

struct mycomparison
{
    bool operator() (int* lhs, int* rhs) {return (*lhs) < (*rhs);}
};

int main(int argc, char* argv[])
{
    int myarray[] = {1, 3, 6, 2, 4, 9, 5, 12, 10};
    const size_t size = sizeof(myarray) / sizeof(myarray[0]);
    int *arrayofpointers[size];
    for(int i = 0; i < size; ++i)
    {
        arrayofpointers[i] = myarray + i;
    }
    std::sort(arrayofpointers, arrayofpointers + size, mycomparison());
    for(int i = 0; i < size; ++i)
    {
        *arrayofpointers[i] = i + 1;
    }
    for(int i = 0; i < size; ++i)
    {
        std::cout << myarray[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}


This video can help you solving your question :)
By: admin