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

Question

Hi all, 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. Thanks in advance.
Edit: I am using a shell sort procedure, and duplicates' ranks are arbitrarily chosen, based on which came first in the original array.

Answer 1

Well, there's a trival n^2 solution.

In python:

newArray = sorted(oldArray)
blankArray = [0] * len(oldArray)
for i in xrange(len(newArray)):
  dex = oldArray.index(newArray[i])
  blankArray[dex]  = i

Depending on how large your list is, this may work. If your list is very long, you'll need to do some strange parallel array sorting, which doesn't look like much fun and is a quick way to introduce extra bugs in your code.

Also note that the above code assumes unique values in oldArray. If that's not the case, you'll need to do some post processing to solve tied values.

Answer 2

Since you're using C++, I would do it something like this. The SortIntPointers function can be any sort algorithm, the important part is that it sorts the array of pointers based on the int that they are pointing to. Once that is done, you can go through the array of pointers and assign their sorted index which will end up in the original position in the original array.

int* intArray; // set somewhere else
int arrayLen;  // set somewhere else  

int** pintArray = new int*[arrayLen];
for(int i = 0; i < arrayLen; ++i)
{
    pintArray[i] = &intArray[i];
}

// This function sorts the pointers according to the values they
// point to. In effect, it sorts intArray without losing the positional
// information.
SortIntPointers(pintArray, arrayLen);

// Dereference the pointers and assign their sorted position.
for(int i = 0; i < arrayLen; ++i)
{
    *pintArray[i] = i;
}

Hopefully that's clear enough.

Answer 3

create a new array with increasing values from 0 to n-1 (where n is the length of the array you want to sort). Then sort the new array based on the values in the old array indexed by the values in the new array.

For example, if you use bubble sort (easy to explain), then instead of comparing the values in the new array, you compare the values in the old array at the position indexed by a value in the new array:

function bubbleRank(A){
  var B = new Array();
  for(var i=0; i<A.length; i++){
    B[i] = i;
  }
  do{
    swapped = false;
    for(var i=0; i<A.length; i++){
      if(A[B[i]] > A[B[i+1]]){
        var temp = B[i];
        B[i] = B[i+1];
        B[i+1] = temp;
        swapped = true;
      }
    }
  }while(swapped);
  return B;
}

Answer 4

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

Thanks in advance.

Answer 5

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

Answer 6

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.