Yesterday i was translating some code i wrote in R to C++. I had some calculation to do which required the list of index of the top `n` values in a list. Therefore what i needed was not a the list sorted itself or get a sorted copy of a given list, but actually the sorted order of the index into the actual array. To describe the problem, for example consider the following list:

arr = 20 50 40 80 10

The sorted (non-decreasing) ordering of the values is obviously

sorted_arr = 10 20 40 50 80

The sorted (non-decreasing) ordering of the index into the original array is (index starts at 1 in this example)

sorted_index_into_arr = 5 1 3 2 4

Therefore the smallest value in the list `arr` could be found by indexing into `arr` using the first value of `sorted_index_into_arr`, which stores the index of the array `arr` holding the smallest value.

arr[ sorted_index_into_arr[1] ]

The sorted index ordering is very easy to get in languages like R and Octave or Matlab. For example in R we can do the following to get the sorted index order using the `order` function:

> arr <- c (20, 50, 40, 80, 10)
> arr
[1] 20 50 40 80 10
> order (arr)
[1] 5 1 3 2 4

In the case of Octave or Matlab you can get the index order using the `sort` function, which will return two lists (1xn matrix), the first list is the sorted array itself, and the next one is the sorted index order into the original array.

octave:1> a = [20 50 40 80 10]
a =
20 50 40 80 10
octave:2> [sorted index] = sort (a)
sorted =
10 20 40 50 80
index =
5 1 3 2 4

Although these functional languages provides gives these features in C/C++ it is not immediately available using the builtin sort library functions. But the sorting routines accepts a function pointer to a comparison function, writing appropriate code for which will do the trick.

Continue reading “Get sorted index orderting of an array” →

22.505694
88.351861