0

I have an array of integers which consists of triples.

[a1, b1, c1, a2, b2, c2, ... ,aN, bN, cN]

Every tuple (ai, bi) is unique regardless of the value of ci in the triple (ai, bi, ci).

I want to sort my array ascending by the value of ai and then ascending by the value of bi.

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?

user2033412
  • 1,950
  • 2
  • 27
  • 47
  • Sort by threes: i.e. every iteration, you're moving and manipulating 3 integers at a time. – Richard Barker Mar 21 '21 at 21:05
  • 3
    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 Mar 21 '21 at 21:17
  • 1
    Because I would have to create them in the first place. I already have the integer array. – user2033412 Mar 21 '21 at 21:21
  • 1
    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 Mar 21 '21 at 21:28
  • Any idea how such a type would work in C#? I get your idea but I need more guidance. – user2033412 Mar 21 '21 at 21:47
  • 4
    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](https://referencesource.microsoft.com/mscorlib/system/collections/generic/arraysorthelper.cs.html#6e012536844280af) 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 Mar 21 '21 at 22:00
  • I'm on my phone so I can't write code. But take a look at my answer to this, it might inspire you: https://stackoverflow.com/questions/66324262/performant-concatenating-2d-arrays-stored-as-sub-arrays/66325673#66325673 – Flydog57 Mar 21 '21 at 22:02
  • The idea would be to create a type that implements `ICollection` (where ITriplet is an interface that exposes three integer properties and ICollection is what I think the minimum collection rule is for sorting). For a collection of _N_ triplets, the constructor would take a collection of _3N_ integers. The rest is programming – Flydog57 Mar 21 '21 at 23:27
  • I understand how the sorting-algorithm would be able to do comparisons but how would that way the integer-array be changed? Sorry, I'm stuck. – user2033412 Mar 22 '21 at 07:26

1 Answers1

2

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.

Theodor Zoulias
  • 34,835
  • 7
  • 69
  • 104