Sorting a flattened array

Question

I'm using C# in .NET 4. The class holds an array of double that represents a 2-D rectangular matrix but (due to business requirements) must be stored flattened (i.e. a double[]). The class also stores the dimensions of the array. I wish to sort the array by the (virtual) first column. Obviously I have to unflatten it, at least partially, in order to do this, right? I don't see anything in LINQ or System.Array that works on a flattened array.

If there's 1 column, System.Array.Sort() works fine and I don't think it can be improved.

If there's 2 columns, it's not hard to split it into two arrays and again use System.Array.Sort(). If you quickly see a way to improve it great, but if not, I'm happy with it as it stands.

I'm not happy with the code for 3 or more columns (it stinks) and suspect there's some way to improve it.

N.B. In real life the class has get-only properties. It's guaranteed that rows and cols are positive, array != null, and rows*cols==array.Length.

public partial class FlattenedArray
{
    public int rows;
    public int cols;
    public double[] array;
    public void sort()
    {
        double[] keys;
        switch(cols)
        {
            case 1:
                System.Array.Sort<double>(array);
                break;
            case 2:
                keys = new double[rows];
                double[] dItems = new double[rows];
                for (int i=0,k=0; i<rows; i++)
                {
                    keys[i] = array[k++];
                    dItems[i] = array[k++];
                }
                System.Array.Sort<double,double>(keys,dItems);
                for (int i=0,k=0; i<rows; i++)
                {
                    array[k++] = keys[i];
                    array[k++] = dItems[i];
                }
                break;
            default:
                keys = new double[rows];
                int[] items = new int[rows];
                double[] temp = new double[rows*cols];
                for (int i=0,k=0; i<rows; i++, k+=cols)
                {
                    keys[i] = array[k];
                    items[i] = k;
                }
                System.Array.Sort<double,int>(keys,items);
                for (int i=0,k=0; i<rows; i++)
                {
                    int spt = items[i];
                    for (int j = 0; j < cols; j++)
                    {
                        temp[k++] = array[spt++];
                    }
                }
                array = temp;
                break;
            }

Answer 1

You can improve the code for 3 or more columns and at the same time use it for 1 or 2 columns, by using LINQ:

public partial class FlattenedArray
{
    public int rows;
    public int cols;
    public double[] array;
    public void sort()
    {
        array = (from i in Enumerable.Range(0, rows)
                        select new List<double>(array.ToList().GetRange(cols * i, cols)))
                        .OrderBy(x => x[0])
                        .SelectMany(x => x)
                        .ToArray();     
    }
}

This divides the array into dimensions and sorts it by the first column then flattens it all back to 1D. It will work for any combination of rows and columns as long the conditions you mentioned hold true.

If the data size gets very large you still might want to use Array.Sort for the 1 column data as this code wouldn't be very efficient for 1 column.

Answer 2

As for introducing special cases for efficiency purposes, you ain't gonna need it. Don't try to second guess reality. If you hit performance bottle neck, AND determine that a great majority of the cases can be handled specially, then you make the special hack. Then measure again keep the hack if it actually is useful.

More than a few lines in a case statement reduces readability. So extract those statements to a method.

default:
    array = Sort(array, rows, cols);
    break;

After that let's look at he algorithm closely to how we can make it more readable

keys = new double[rows];
int[] items = new int[rows];
double[] temp = new double[rows*cols];
for (int i=0,k=0; i<rows; i++, k+=cols)
{
    keys[i] = array[k];
    items[i] = k;
}

A loop doing more than one thing is confusing so split it up, and rearrange declarations so that they are close to what they are used, also rename single letter variables (and generic variable names copied from the API) according to their purpose:

static double[] Sort(double[] array, int rows, int cols)
{
    var result = new double[rows * cols];

    var rowStartIndices = new int[rows];
    for (int row = 0; row < rows; row++)
        rowStartIndices[row] = row * cols;

    var rowFirstValues = new double[rows];
    for (int row = 0; row < rows; row++)
        rowFirstValues[row] = array[rowStartIndices[row]];

    Array.Sort(rowFirstValues, rowStartIndices);

    for (int row = 0; row < rows; row++)
        Array.Copy(array, rowStartIndices[row], result, row * cols, cols);

    return result;
}

Use Array.Copy to copy array ranges.

Also some unnecessary type declarations are removed to improve readability. And it reads quite well top to bottom. There is some more noise that can be removed, and some other noise that can be moved elsewhere:

static double[] Sort(double[] array, int rows, int cols)
{
    double[] sorted = new double[array.Length];

    Enumerable.Range(0, rows)
        .Select(row => row * cols)
        .OrderBy(rowStartIndex => array[rowStartIndex])
        .ForEach((rowStartIndex, row) => Array.Copy(array, rowStartIndex, sorted, row * cols, cols));

    return sorted;
}

Where the ForEach method is a convenience method defined as such:

static class LocalExtensions
{
    public static void ForEach<T>(this IEnumerable<T> source, Action<T, int> action)
    {
        int index = 0;

        foreach(var current in source)
        {
            action(current, index);
            index++;
        }
    }
}

Answer 3

Maybe I'm entirely off-base, but the real smell to me here is this statement:

(due to business requirements) must be stored flattened

If it is truly a rectangular array, all your operations on the flat array have to be double checked to make sure they are valid for the real data structure that you need. It sounds like you may be bending over backwards thinking about the end and not the means. I can certainly understand reasons why it needs to ultimately be converted to a flattened array for storage, etc., but if for all intents and purposes it should behave like a rectangular array in code then it should be one.

If you just use a rectangular array, all the state, dimensions, etc. you have to monitor are already taken care of for you, and if you need it back in the flat format for the "business requirement", there are very easy ways to do the conversion in that direction:

int[,] whatTheCodeProbablyWants = new int[2,2] { {1, 2}, {3, 4} };
int[] whatTheBusinessSideNeeds = whatTheCodeProbablyWants.Cast<int>().ToArray();

...or jagged:

int[][] whatTheCodeProbablyWants = new int[][] { new int[] {1, 2}, new int[] {3} };
int[] whatTheBusinessSideNeeds = whatTheCodeProbablyWants.SelectMany (x => x).ToArray();