Sorting two arrays (values,keys), then sorting the keys

I have what seems to be a simple problem but I can't figure it out so far.

Say I have two arrays:

int[] values = {10,20,20,10,30};
int[] keys = {1,2,3,4,5};

Array.Sort(values,keys);

Then the arrays would look like this:

values = {10,10,20,20,30};
keys = {4,1,2,3,5};

Now, what I want to do is make it so that the keys are also sorted in second priority so the key array to look like this:

keys = {1,4,2,3,5};

Noti开发者_JAVA百科ce the 1 and 4 values are switched and the order of the value array has not changed.

---

If an "in-place sorting" is not strictly necessary for you, I suggest to use OrderBy:

var sortedPairs = values.Select((x, i) => new { Value = x, Key = keys[i] })
                        .OrderBy(x => x.Value)
                        .ThenBy(x => x.Key)
                        .ToArray(); // this avoids sorting 2 times...
int[] sortedValues = sortedPairs.Select(x => x.Value).ToArray();
int[] sortedKeys = sortedPairs.Select(x => x.Key).ToArray();

// Result:
// sortedValues = {10,10,20,20,30};
// sortedKeys = {1,4,2,3,5};

---

Generally, parallel arrays are frowned upon. It is very easy for the data to become out of sync. What I would suggest is either using a map/Dictionary data type, or storing the keys and values in a single object, and then having an array of said objects.

Edit: after re-reading your question, I dont' think the Dictionary is the data type you want, based on your need to sort the values. I would still suggest having an object that contains the keys and values, however. You can then sort by the values, and rest assured that they keys aren't out of sync.

---

Array.Sort(values,keys) will use the default Comparer to sort the values and keys. You would need to write a custom Comparer to do what you're describing, and pass your Comparer in to the Array.Sort method.

---

By converting this to a sort on an array of value pairs you can supply your own comparator and make the sort work pretty much any way you like. (It seems awful risky to use two separate arrays.) See the fourth method at http://msdn.microsoft.com/en-us/library/system.array.sort.aspx.

---

I think the accepted answer is great. One can use anonymous types, as shown in that answer, or declare a named type to hold the data while sorting.

Even better, declare a named type to hold the data all the time. Parallel arrays are usually not a good idea. There are some niche scenarios where they are needed for performance or interopability reasons, but otherwise they should be avoided.

That said, for completeness I think it would be useful to also point out that the arrays can be sorted "by proxy". I.e. create a new array that is just the indexes of the original arrays and sort that array. Once the index array has been sorted, you can use that array to access the original data directly, or you can use that array to then copy the original data into new, sorted arrays.

For example:

static void Main(string[] args)
{
    int[] values = { 10, 20, 20, 10, 30 };
    int[] keys = { 1, 2, 3, 4, 5 };

    int[] indexes = Enumerable.Range(0, values.Length).ToArray();

    Array.Sort(indexes, (i1, i2) => Compare(i1, i2, values, keys));

    // Use the index array directly to access the original data
    for (int i = 0; i < values.Length; i++)
    {
        Console.WriteLine("{0}: {1}", values[indexes[i]], keys[indexes[i]]);
    }

    Console.WriteLine();

    // Or go ahead and copy the old data into new arrays using the new order
    values = OrderArray(values, indexes);
    keys = OrderArray(keys, indexes);

    for (int i = 0; i < values.Length; i++)
    {
        Console.WriteLine("{0}: {1}", values[i], keys[i]);
    }
}

private static int Compare(int i1, int i2, int[] values, int[] keys)
{
    int result = values[i1].CompareTo(values[i2]);

    if (result == 0)
    {
        result = keys[i1].CompareTo(keys[i2]);
    }

    return result;
}

private static int[] OrderArray(int[] values, int[] indexes)
{
    int[] result = new int[values.Length];

    for (int i = 0; i < values.Length; i++)
    {
        result[i] = values[indexes[i]];
    }

    return result;
}