Determining how close an array is to the target array

Question

I'm playing a little experiment to increase my knowledge and I have reached a part where I feel i could really optimize it, but am not quite sure how to do this.

I have many arrays of numbers. (for simplicity, lets say each array has 4 numbers: 1, 2, 3, and 4)

• The target is to have all of the numbers in ascending order (ie, 1-2-3-4), but the numbers are all scrambled in the different arrays.

• A higher weight is placed upon larger numbers.

• I need to sort all of these arrays in order of how close they are to the target.

Ie, 4-3-2-1 would be the worst possible case.

Some example cases:

3-4-2-1 is better than 4-3-2-1
2-3-4-1 is better than 1-4-3-2 (even though two numbers match (1 and 3). 
                                the biggest number is closer to its spot.)

So the big numbers always take precedence over the smaller numbers. Here is my attempt:

        var tmp = from m in moves
                  let mx = m.Max()
                  let ranking = m.IndexOf(s => s == mx)
                  orderby ranking descending
                  select m;

        return tmp.ToArray();

P.S IndexOf in the above example, is an extension I wrote to take an array and expression, and return the index of the element that satisfies the expression. It is needed because the situation is really a little more complicated, i'm simplifying it with my example.

The problem with my attempt here though, is that it would only sort by the biggest number, and forget all of the other numbers. it SHOULD rank by biggest number first, then by second largest, then by third.

Also, since it will be doing this operation over and over again for several minutes, it should be as efficient as possible.

Answer 1

You could implement a bubble sort, and count the number of times you have to move data around. The number of data moves will be large on arrays that are far away from the sorted ideal.

int GetUnorderedness<T>(T[] data) where T : IComparable<T>
{
    data = (T[])data.Clone(); // don't modify the input data, 
                              // we weren't asked to actually sort.
    int swapCount = 0;
    bool isSorted;
    do
    {
        isSorted = true;
        for(int i = 1; i < data.Length; i++)
        {
            if(data[i-1].CompareTo(data[i]) > 0)
            {
                T temp = data[i];
                data[i] = data[i-1];
                data[i-1] = temp;
                swapCount++;
                isSorted = false;
            }
        }
    } while(!isSorted);
}

From your sample data, this will give slightly different results than you specified.

Some example cases:
3-4-2-1 is better than 4-3-2-1
2-3-4-1 is better than 1-4-3-2

3-4-2-1 will take 5 swaps to sort, 4-3-2-1 will take 6, so that works.
2-3-4-1 will take 3, 1-4-3-2 will also take 3, so this doesn't match up with your expected results.

This algorithm doesn't treat the largest number as the most important, which it seems you want; all numbers are treated equally. From your description, you'd consider 2-1-3-4 as much better than 1-2-4-3, because the first one has both the largest and second largest numbers in their proper place. This algorithm would consider those two equal, because each requires only 1 swap to sort the array.

This algorithm does have the advantage that it's not just a comparison algorithm, each input has a discrete output, so you only need to run the algorithm once for each input array.