Making an array with the order of numbers from another array

Question

I'm looking at writing an array that takes the values of another array and "sorts" them into another array based on their size.

Example:

an array of [16, 5, 23, 1, 19]

would end up in the second array as

[2, 1, 4, 0, 3]

The first array can be any size, but is assumed to not have any duplicate numbers in it. It should NOT sort the numbers by greatest to largest, maintaining position in the array is vital.

How is it going to sort based on size. I dont understand how `[16,5,23,1,19]` will end up as `[2,1,4,0,3]` — , Sep 28 '13 at 07:25
16 is the third largest number, 5 is second largest, 23 is the largest overall, 1 is the smallest, 19 is the fourth largest. — user2825792, Sep 28 '13 at 07:28
You are not sorting on regular string or number, but trying to sort based on your own business logic, You can overwrite the CompareTo or Equalto function of your Object and then use that to sort array based on that logic. — Sumit Gupta, Sep 28 '13 at 07:30
So whats the problem?? Go on.. do it !! if you get stuck.. then come and ask to us — Shaharyar, Sep 28 '13 at 07:31
http://stackoverflow.com/questions/8975698/implementing-custom-icomparer-with-string try this comparer for writing your own. — Sumit Gupta, Sep 28 '13 at 07:31
possible duplicate of [Is there C# support for an index-based sort?](http://stackoverflow.com/questions/659866/is-there-c-sharp-support-for-an-index-based-sort) — Gayot Fow, Sep 28 '13 at 13:01

score 4 · Accepted Answer · answered Sep 28 '13 at 07:35

4

Naive implementation:

var array = new []{16, 5, 23, 1, 19};

var sortedArray = array.OrderBy(x=>x).ToArray();

var result = new int[array.Length];

for(int i = 0; i<result.Length; i++)
    result[i] = Array.IndexOf(sortedArray, array[i]);

answered Sep 28 '13 at 07:35

Alberto

15,626
9
43
56

score 0 · Answer 2 · answered Sep 28 '13 at 07:37

var result = origArray.Select(Tuple.Create<int, int>)
  .OrderBy(t => t.Item1)
  .Select((t, x) => Tuple.Create(t.Item2, x))
  .OrderBy(s => s.Item1)
  .Select(s => s.Item2)
  .ToArray();

Untested, so probably needs some adjustment, but the idea should be OK.

Matthew Watson · Answer 3 · 2013-09-28T09:19:40.863

You can do this using the overload of Array.Sort() which takes two arrays and sorts the second one according to the order that it sorts the first one.

var array = new[] { 16, 5, 23, 1, 19 };
var indices = Enumerable.Range(0, array.Length).ToArray();
Array.Sort(array.ToArray(), indices);
var result = new int[array.Length];

for (int i = 0; i < result.Length; ++i)
    result[indices[i]] = i;

// Now result[] contains the answer.

This uses a couple of O(n) operations to make a copy of the array and to create the indices array at the start, followed by an O(n log n) sort, and finally finishes up with an O(n) operation to rearrange result[].

(The algorithms presented in the other answers are likely a bit slower, but you probably really don't care unless you've already determined this functionality to require maxmimum speed - which seems unlikely.)

Making an array with the order of numbers from another array

3 Answers3

Linked