How to store the original indices of array after sorting the array in ascending ordering

Question

Assume that I have a array_dist, and I sorted this array in ascending order successfully. But I need also to store the indices of the original array in new array called index_arr. Example: array [5,4,3,2,1] has indices [0,1,2,3,4]. what I need after sorting the array [1,2,3,4,5]. is these indices [4,3,2,1,0]

I try the following code which correctly sorted the array_dist but not correctly store the indices in index_arr

int index_arr[4344]{};
for (int i = 0; i < 4344; ++i) {
 index_arr[i] = i;
}
float temp; int x; 
for (int i = 0; i < 4344 ; i++)
{
   for (int j = i + 1; j < 4344; j++)
   {   
       if (array_dist[i] > array_dist[j])
       {
            temp = array_dist[i];
            array_dist[i] = array_dist[j];
            array_dist[j] = temp;
            x = index_arr[i];
            index_arr[i] = index_arr[j];
         index_arr[j] = x;
       }        
    }
}
    
cout << "print out distance colum after ascending sorting : \n";
 
    for (int i = 0; i < 4344; ++i)
 {
     cout << index_arr[i] << " : "
         << array_dist[i] << endl;
 }

The correctly working code that I compare my results with:

auto sortRuleLambda = [](pair<int, float> const& s1, pair<int, float> const& s2) -> bool
    {
        return s1.second < s2.second;
    };
    sort(array_dist.begin(), array_dist.end(), sortRuleLambda);

     cout << "print out distance colum after ascending sorting : \n";
             for (int i = 0; i < array_X_train.size(); ++i)
    {
        cout << array_dist[i].first << ": "
            << array_dist[i].second << endl;
    }

There is no need to sort the original array `array_dist` at all. [See this](https://stackoverflow.com/questions/40405266/having-trouble-creating-an-array-that-shows-how-the-indices-were-moved-in-anothe/40405691#40405691). The only array that requires sorting is the index array -- there is a reason why it's called an index array. Also, why are you using the awful bubble sort, when you could use `std::sort`? — PaulMcKenzie, Aug 27 '21 at 17:36
You should mention up front what you are or are not allowed to use, so that answers are not posted and then rejected because the answer uses things we have no idea you can or cannot use. — PaulMcKenzie, Aug 27 '21 at 17:43
@PaulMcKenzie, what do you mean by "There is no need to sort the original array array_dist at all" — user16767585, Aug 27 '21 at 17:48
The whole purpose of the index array is to -- *index* into the original array. Again, that's why it's called an "index array". You're just not seeing how to use it properly. — PaulMcKenzie, Aug 27 '21 at 17:49
yes but I want for further steps in my code an array with sorted data and an array with indices of original data — user16767585, Aug 27 '21 at 17:51
Look at my answer. You get both *without* having to sort the original array. That's the whole point of having an index array. Also, for more details, [see this answer](https://stackoverflow.com/questions/46382252/sort-array-by-first-item-in-subarray-c/46382976#46382976) — PaulMcKenzie, Aug 27 '21 at 17:51
Your update missed the whole point. You are unnecessarily having to sort the data array, when all you need to sort is the index array. Again, see the answer I posted. — PaulMcKenzie, Aug 27 '21 at 18:15
[Here is what the lambda function should look like](http://coliru.stacked-crooked.com/a/6e63ae1c5eab80d1). Now unless I'm a magician, how did I get the `array_dist` to print out sorted without actually sorting it? — PaulMcKenzie, Aug 27 '21 at 18:20
@PaulMcKenzie thank you very much for your http://coliru.stacked-crooked.com/a/6e63ae1c5eab80d1, it is work correctly well, but I was wondering what is n1 and n2 in the code ??? — user16767585, Aug 28 '21 at 06:52
The `n1` and `n2` are the values that the `std::sort` is sending you for comparison. They come from the `index_array`. — PaulMcKenzie, Aug 28 '21 at 06:53
okay I understand now, I was wondering because I am not required to initialize them — user16767585, Aug 28 '21 at 06:58
could you please add your solution as answer so I could marked it as the correct answer for this question. Thank you very much again — user16767585, Aug 28 '21 at 06:59
@PaulMcKenzie, as I told you before that your solution to use sort is working correctly in c++ and gave me correct results for both array's elements and indices. But, earlier today, I tried to use the same code in OpenCL. It gave me error "function 'sort' is invalid in OpenCL" . So, I return back to the same problem. I really need to use the same procedure {bubble sort) as in my question. But still the indices are not sorted correctly. plz I need your help — user16767585, Aug 28 '21 at 11:37
Keep the bubble sort exactly the same that you wrote *except* remove those lines where you are changing `array_dist`, and replace the `if` clause. That's it. In other words, the solution is a subset of the code you wrote (a simple cut of 3 lines and a replace of one line). — PaulMcKenzie, Aug 28 '21 at 16:53

KhiemGOM · Answer 1 · 2021-08-28T14:36:17.567

2

map<int, int> smallest;
int arr[4344];
//do some initialize
for (int i=0;i<4344;i++) 
{
    smallest.insert(pair(arr[i], i));
}

Now smallest will contain the sorted array by value and contain its corresponding index. Edit (same but without using map container):

class sth //sorry I don't creative with the name
{
public:
    int value, index;
    explicit sth()
    {
        value = 0;
        index = 0;
    }
    sth (const int v, const int i)
    {
        value = v;
        index = i;
    }
};

int main()
{
    constexpr int n = 10; //make a variable like this will make life easier
    sth* smallest = new sth[n];
    int arr[n] = {1,2,3,-4,12,5,124,-12,22,123};
    //do some initialize
    for (int i = 0; i < n; i++)
    {
        smallest[i]=sth(arr[i], i);
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (smallest[i].value > smallest[j].value)
            {
                sth temp = smallest[i];
                smallest[i] = smallest[j];
                smallest[j] = temp;
            }
        }
    }
}

Now the smallest array should contain the value and the index of the first array.

edited Aug 28 '21 at 14:36

answered Aug 28 '21 at 04:31

KhiemGOM

69
8

Depending on context: This might be the most clever or crazy answer. +1 for thinking _outside the box_. – Ted Lyngmo Aug 28 '21 at 06:07
Thank for your suggestion, but I am not allowed to use map – user16767585 Aug 28 '21 at 06:22
@user16767585 Can you use `vector>` ? – KhiemGOM Aug 28 '21 at 09:30
@user16767585 How abt use a struct with two properties: `value`, and `index`? – KhiemGOM Aug 28 '21 at 13:05
okay great. would you please add your struct as answer so I could try – user16767585 Aug 28 '21 at 13:12
@user16767585 okay I fixed it as your demand though the code now has lambda expression. And can you use `std::sort`? – KhiemGOM Aug 28 '21 at 14:24
@user16767585 Oh sorry you can't use sort, just let me fix the code – KhiemGOM Aug 28 '21 at 14:31
Yes so I fixed my code not to use sort, is it what you need? – KhiemGOM Aug 28 '21 at 16:02

score 1 · Accepted Answer · answered Aug 27 '21 at 17:50

1

The issue is that you are sorting the original array_dist when you shouldn't be sorting this at all.

You should only sort the index_array based on the comparison of the array_dist values :

// Compare values at `array_dist`, using the index array 
if (array_dist[index_array[i]] > array_dist[index_array[j]])
{
   // the indices need to be swapped
   x = index_arr[i];
   index_arr[i] = index_arr[j];
   index_arr[j] = x;
}

Once you have this, then to print out the array_dist in sorted order:

for (int i = 0; i < 4344; ++i)
{
   cout << index_arr[i] << " : "
       << array_dist[index_arr[i]] << endl;
}

You use the index_array as a subscript within the original array.

answered Aug 27 '21 at 17:50

PaulMcKenzie

34,698
4
24
45

I just tried your code it gave me the same results of my code – user16767585 Aug 27 '21 at 17:58
Actually I compare my results with other code implemented using pair, begin, end. it gave me slightly difference in indices – user16767585 Aug 27 '21 at 18:00
I just update the question with the code that I compare my results with – user16767585 Aug 27 '21 at 18:05
The code works [here](http://coliru.stacked-crooked.com/a/22b0b03a01e8b02d). Did you make *all* of the changes, including changing the test in the loop, plus print out the array using the index array as a subscript? – PaulMcKenzie Aug 27 '21 at 18:12
Instead of showing OP how to print out the desired output, you can use the sorted `index_arr` to create a re-arranged `array_dist`. Probably easiest to re-arrange into a new array, and then copy the new array on top of `array_dist`. – jxh Aug 27 '21 at 18:21
While I agree in general that you should sort an index file sometimes you get better cache locality sorting the target depending on access needs. – doug Aug 27 '21 at 18:23
@jxh I'm assuming he's just trying to debug his code for learning and not trying to write a better `std::sort` which he compares against. Just pointing out that it's not always optimal to sort against an index depending on how the data is used afterwards. – doug Aug 27 '21 at 18:31
@doug I understood your overall point. But in the context of this likely being a homework problem, the only locality advantage to sorting the data rather than an index is if the sorting algorithm itself can take advantage of that locality. Quicksort is an example of a sorting algorithm that does so. – jxh Aug 27 '21 at 21:08
@jxh I was really thinking of other readers that would be, of course, using `std::sort` and needed an index. And I've frequently sorted index and values with the values sorted because my subsequent use of the values in sorted order was extensive and cache locality, especially after chopping values up for multithreading, was most of the work while backtracking via the index was required but infrequent. But I do agree that sorting the index is typically the best approach. – doug Aug 27 '21 at 21:31

How to store the original indices of array after sorting the array in ascending ordering

2 Answers2