Sorting array by max distance

Question

I've got a list of unique integers, and I want to sort them so that the next integer is always as far from all the rest, an it's possible.

For example, {1,2,3,4,5,6,7,8,9} => {1,9,6,2,8,3,7,4,5}

And I need to do it really fast.

Currently, I'm doing it like this:

    static double GetDistanceIndex(int value, List<int> others)
    {
        double result=0;
        foreach (var other in others)
        {
            result += Math.Sqrt(Math.Abs(other - value));
        }

        return result;
    }

    static List<int> Sort(List<int> items, int initialValue)
    {
        items = items.ToList();
        List<int> result=new List<int>();


        lock (rnd)
        {
            while (true)
            {
                result.Add(initialValue);
                items.Remove(initialValue);
                if (items.Count == 0)
                {
                    break;
                }
                Dictionary<double, List<int>> distances = new Dictionary<double, List<int>>();
                foreach (var item in items)
                {
                    var d = GetDistanceIndex(item, result);
                    if (!distances.ContainsKey(d))
                    {
                        distances[d] = new List<int>();
                    }
                    distances[d].Add(item);
                }

                var max = distances.Keys.Max();
                var l = distances[max];
                //if (l.Count == 1)
                //{
                //    initialValue = l[0];
                //}
                //else
                //{
                initialValue = l[rnd.Next(l.Count)];
                //} 
            } 
        }

        return result;
    }

But the problem is, that implemented like this, the algorithm will work extremely slowly for large arrays.

Can anyone suggest to me a better way to do it?

UPDATE

Here's a better description what was done:

{1,2,3,4,5,6,7,8,9}=>

1. initial seed : 1. Really, it can be any number. We can select 5, and get something like {5,9,1,2,8,3,7,6,4}
2. From the provided array, 9 is the farthest away from 1 by distances
3. Because in the list all the numbers are equidistant from 1 and from 9, we can select any of them. I used rand to select 6.
4. Now we are looking for a number farthest away from {1,9,6}. 2 is selected because abs(2-1)+abs(2-9)+abs(2-6)=12 and is greater than abs(3-1)+abs(3-9)+abs(3-6)=11 or abs(4-1)+abs(4-9)+abs(4-6)=10 or abs(8-1)+abs(8-9)+abs(8-6)=10 or abs(7-1)+abs(7-9)+abs(7-6)=9 or abs(5-1)+abs(5-9)+abs(5-6)=9
5. etc

UPDATE 1

I'm using this algorithm to select numbers as different from each other as possible from a fixed number of alternatives

UPDATE 2

Dukeling in his answer pointed out to me, that {1,9,2,8,3,7,4,6,5} also conforms to my requirements. This was true, and it's my mistake. I want the numbers to be as far spaced as possible, and 3d number being very close to the first one is not what I intended. So I'm updating the distance function to reflect this

Answer 1

[Edited to conform to new distance function]

You are making unnecessary work by calling GetDistanceIndex() repeatedly. Notice that you don't need to sum everything from scratch everytime. If you have an array like this:

[a, b, c, d, ............, x]

Where a, b, c, and d are already sorted, then, when you insert a new element 'e', the sum of the distance function of any position 'x' in the unsorted set to all the other numbers in the sorted set is only increased by sqrt(abs(x-e)). You don't have to recompute the whole sum from scratch.

So here's how you can optimize it: use some kind of method to store a pair (number, distance). If you were using C, you could, for example, make an array of a structure with two integers, the value itself, and the distance to the sorted set. At each step, you go through every pair (number, distance) that is not in the sorted set and you update its distance attribute. You can keep track of the maximum at the same time. Some pseudo-code:

• Create an auxiliary buffer S, to hold pairs of (number, distance);

• Insert every number x different from initialValue in S, with distance = sqrt(abs(initialValue - x)). Keep track of the maximum, m, at the same time;

• In each step, pick m and move it to the sorted piece of the array. Remove it from S. Then, go to every element y in S and add sqrt(abs(y.number-m.number)) to y's distance. Again, you need to keep track of the maximum as you do this. Keep repeating that until every element is sorted.

It's not a brilliant solution; it runs in O(n^2), but your current algorithm runs in O(n^3) because GetDistanceIndex() always starts from scratch. Also, I wouldn't use lists and dictionaries, try to use a simple array, so that you can access and delete elements in constant time. Deleting from a list can be inefficient, it never gets better than O(log(n)).

At the moment, that's the only optimization I can think of, maybe someone will have a better idea.

Answer 2

{1,9,2,8,3,7,4,6,5} seems to conform to your requirements, and is fairly easy to generate.

Just sort the numbers in ascending / descending order (if not already done).

Then iterate from both the back and the front, alternating between them until we get to the middle. This step runs in linear time.