C # - The fastest way to sort an array of primitives and track their indices

Question

I need to sort float[] . And I need to know where the old indexes are in the new array. Therefore, I can not use Array.Sort(); or something else. Therefore, I would like to write a function that sorts the array for me and remembers from which index each value was required:

 float[] input = new float[] {1.5, 2, 0, 0.4, -1, 96, -56, 8, -45}; // sort float[] output; // {-56, -45, -1, 0, 0.4, 1.5, 2, 8, 96}; int[] indices; // {6, 8, 4, 2, 3, 0, 1, 7, 5}; 

The size of the arrays will be around 500. How do I approach this? What sorting algorithm, etc.

---

After the solution: It always surprises me how powerful C # is. I did not even think that I was able to accomplish this task myself. And since I already heard that Array.Sort() really fast, I'll take it.

Answer 1

 float[] input = new float[] { 1.5F, 2, 0, 0.4F, -1, 96, -56, 8, -45 }; int[] indices = new int[input.Length]; for (int i = 0; i < indices.Length; i++) indices[i] = i; Array.Sort(input, indices); // input and indices are now at the desired exit state 

Basically, a version of Array.Sort with two arguments applies the same operations to arrays as well, performing actual comparisons of sorting by the first array. Usually it is used the other way around - to change something according to the desired indicators; but it works too.

Answer 2

You can use the Array.Sort () overload, which takes TWO arrays and sorts the second according to how it sorted the first:

 float[] input = new [] { 1.5f, 2, 0, 0.4f, -1, 96, -56, 8, -45 }; int[] indices = Enumerable.Range(0, input.Length).ToArray(); Array.Sort(input, indices); 

Answer 3

You can create a new array of indices, and then sort both of them with Array.Sort and treat the input as keys:

 float[] input = new float[] { 1.5F, 2, 0, 0.4F, -1, 96, -56, 8, -45 }; int[] indicies = Enumerable.Range(0, input.Length).ToArray(); Array.Sort(input, indicies); 

Answer 4

if you use linq:

  float[] input = new float[] { 1.5F, 2, 0, 0.4F, -1, 96, -56, 8, -45 }; var result = input.Select(x => new { Value = x, Index = input.ToList().IndexOf(x)}).OrderBy(x => x.Value).ToList(); // sort float[] output = result.Select(x => x.Value).ToArray(); int[] indices = result.Select(x => x.Index).ToArray(); 

in the results you got objects with values ​​and their indices.

Answer 5

A List<KeyValuePair<int,float>> , and a custom sorter will also work. the key for each pair contains the source index.

  private void Form1_Load(object sender, EventArgs e) { List<KeyValuePair<int,float>> data = new List<KeyValuePair<int,float>> { new KeyValuePair<int,float>(0,1.5f), new KeyValuePair<int,float>(1,2), new KeyValuePair<int,float>(2,0), new KeyValuePair<int,float>(3,0.4f), new KeyValuePair<int,float>(4,-1), new KeyValuePair<int,float>(5,96), new KeyValuePair<int,float>(6,-56), new KeyValuePair<int,float>(7,8), new KeyValuePair<int,float>(8,-45) }; data.Sort(SortByValue); foreach (KeyValuePair<int, float> kv in data) { listBox1.Items.Add(kv.Key.ToString() + " - " + kv.Value.ToString()); } } private int SortByValue(KeyValuePair<int, float> a, KeyValuePair<int, float> b) { return a.Value.CompareTo(b.Value); }