Sort array of integer-triples in C#

Question

I have an array of integers which consists of triples.

[a₁, b₁, c₁, a₂, b₂, c₂, ... ,a_N, b_N, c_N]

Every tuple (a_i, b_i) is unique regardless of the value of c_i in the triple (a_i, b_i, c_i).

I want to sort my array ascending by the value of a_i and then ascending by the value of b_i.

Of course I could introduce a struct Triple, make an array of instances of Triple and sort it with a custom sorter but this would have a big memory allocation and performance overhead.

How can I sort it within the integer array?

Sort by threes: i.e. every iteration, you're moving and manipulating 3 integers at a time. — Batman
– Batman, Commented Mar 21, 2021 at 21:05
I'm curious why you think a collection of a three integer structs is going to use more memory and take more machine cycles to sort, compared to a collection of 3x integers? — Flydog57
– Flydog57, Commented Mar 21, 2021 at 21:17
Because I would have to create them in the first place. I already have the integer array. — user2033412
– user2033412, Commented Mar 21, 2021 at 21:21
Write a type that acts as a facade over three integers in an array, but that looks and smells like a three integer tuple. — Flydog57
– Flydog57, Commented Mar 21, 2021 at 21:28
Do you really feel like writing a custom Sort implementation that treats each consecutive triplet of an array as a distinct entity? Writing such code correctly is not for the faint-hearted. If I was in your place I would strongly consider paying the cost of an extra array allocation, to avoid having to write such complex and error-prone code. — Theodor Zoulias
– Theodor Zoulias, Commented Mar 21, 2021 at 22:00

Theodor Zoulias · Accepted Answer · 2021-03-29 18:51:17Z

Here is a method for sorting arrays composed by consecutive triplets, that should be quite efficient. Each sorting operation allocates an auxiliary int[] indices array, having a third of the size of the source array. The sorting is performed on this auxiliary array, reducing the swap operations on the larger source array to the absolute minimum (at most N - 1 swaps).

public static void SortTriplets<T>(T[] source, Comparison<(T, T, T)> comparison)
{
    // Create an array of incremental indices (zero based)
    var indices = new int[source.Length / 3];
    for (int i = 0; i < indices.Length; i++) indices[i] = i;

    // Sort the indices according to the source array and the comparison delegate
    Array.Sort<int>(indices, (a, b) =>
    {
        a *= 3;
        b *= 3;
        return comparison(
            (source[a], source[a + 1], source[a + 2]),
            (source[b], source[b + 1], source[b + 2]));
    });

    // Rearrange the source array according to the sorted indices
    for (int i = 0; i < indices.Length - 1; i++)
    {
        int k = indices[i];
        while (k < i) k = indices[k];
        if (k == i) continue;
        Swap(i, k);
    }

    void Swap(int a, int b)
    {
        a *= 3;
        b *= 3;
        (T, T, T) temp = (source[a], source[a + 1], source[a + 2]);
        source[a] = source[b];
        source[a + 1] = source[b + 1];
        source[a + 2] = source[b + 2];
        source[b] = temp.Item1;
        source[b + 1] = temp.Item2;
        source[b + 2] = temp.Item3;
    }
}

Usage example:

var random = new Random();
int[] source = Enumerable.Range(1, 15).Select(_ => random.Next(1, 6)).ToArray();
Console.WriteLine($"Source: {String.Join(", ", source)}");
SortTriplets(source, (a, b) =>
{
    int ret = Comparer<int>.Default.Compare(a.Item1, b.Item1);
    if (ret == 0) ret = Comparer<int>.Default.Compare(a.Item2, b.Item2);
    return ret;
});
Console.WriteLine($"Sorted: {String.Join(", ", source)}");

Output:

Source: 3, 2, 3, 2, 2, 1, 2, 3, 2, 5, 4, 2, 1, 5, 4
Sorted: 1, 5, 4, 2, 2, 1, 2, 3, 2, 3, 2, 3, 5, 4, 2

Try it on Fiddle.

Collectives™ on Stack Overflow

Sort array of integer-triples in C#

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related