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

Question

I would like to sort an array in ascending order using C/C++. The outcome is an array containing element indexes. Each index is corespondent to the element location in the sorted array.

Example

Input:  1, 3, 4, 9, 6
Output: 1, 2, 3, 5, 4

Edit: I am using shell sort procedure. The duplicate value indexes are arbitrarily chosen based on which duplicate values are first in the original array.

Update:

Despite my best efforts, I haven't been able to implement a sorting algorithm for an array of pointers. The current example won't compile.

Could someone please tell me what's wrong?

I'd very much appreciate some help!

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

Answer 1

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 2

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