in C#, how do I order items in a list where the "largest" values are in the middle of the list

Question

I have been stumped on this one for a while. I want to take a List and order the list such that the Products with the largest Price end up in the middle of the list. And I also want to do the opposite, i.e. make sure that the items with the largest price end up on the outer boundaries of the list.

Imagine a data structure like this.. 1,2,3,4,5,6,7,8,9,10

In the first scenario I need to get back 1,3,5,7,9,10,8,6,4,2 In the second scenario I need to get back 10,8,6,4,2,1,3,5,7,9

The list may have upwards of 250 items, the numbers will not be evenly distributed, and they will not be sequential, and I wanted to minimize copying. The numbers will be contained in Product objects, and not simple primitive integers.

Is there a simple solution that I am not seeing?

Any thoughts.

So for those of you wondering what I am up to, I am ordering items based on calculated font size. Here is the code that I went with...

The Implementation...

private void Reorder()
{
    var tempList = new LinkedList<DisplayTag>();
    bool even = true;
    foreach (var tag in this) {
        if (even)
            tempList.AddLast(tag);
        else
            tempList.AddFirst(tag);

        even = !even;
    }

    this.Clear();
    this.AddRange(tempList);
}

The Test...

[TestCase(DisplayTagOrder.SmallestToLargest, Result=new[]{10,14,18,22,26,30})]
[TestCase(DisplayTagOrder.LargestToSmallest, Result=new[]{30,26,22,18,14,10})]
[TestCase(DisplayTagOrder.LargestInTheMiddle, Result = new[] { 10, 18, 26, 30, 22, 14 })]
[TestCase(DisplayTagOrder.LargestOnTheEnds, Result = new[] { 30, 22, 14, 10, 18, 26 })]
public int[] CalculateFontSize_Orders_Tags_Appropriately(DisplayTagOrder sortOrder)
{
    list.CloudOrder = sortOrder;
    list.CalculateFontSize();

    var result = (from displayTag in list select displayTag.FontSize).ToArray();
    return result;
}

The Usage...

public void CalculateFontSize()
{
    GetMaximumRange();
    GetMinimunRange();
    CalculateDelta();

    this.ForEach((displayTag) => CalculateFontSize(displayTag));

    OrderByFontSize();
}

private void OrderByFontSize()
{
    switch (CloudOrder) {
        case DisplayTagOrder.SmallestToLargest:
            this.Sort((arg1, arg2) => arg1.FontSize.CompareTo(arg2.FontSize));
            break;
        case DisplayTagOrder.LargestToSmallest:
            this.Sort(new LargestFirstComparer());
            break;
        case DisplayTagOrder.LargestInTheMiddle:
            this.Sort(new LargestFirstComparer());
            Reorder();
            break;
        case DisplayTagOrder.LargestOnTheEnds:
            this.Sort();
            Reorder();
            break;
    }
}

Answer 1

Simplest solution - order the list descending, create two new lists, into the first place every odd-indexed item, into the other every even indexed item. Reverse the first list then append the second to the first.

Answer 2

Something like this?

public IEnumerable<int> SortToMiddle(IEnumerable<int> input)
{
    var sorted = new List<int>(input);
    sorted.Sort();
    var firstHalf = new List<int>();
    var secondHalf = new List<int>();

    var sendToFirst = true;
    foreach (var current in sorted)
    {
        if (sendToFirst)
        {
            firstHalf.Add(current);
        }
        else
        {
            secondHalf.Add(current);
        }
        sendToFirst = !sendToFirst;
    }
    //to get the highest values on the outside just reverse 
    //the first list instead of the second
    secondHalf.Reverse();
    return firstHalf.Concat(secondHalf);
}

For your specific (general) case (assuming unique keys):

public static IEnumerable<T> SortToMiddle<T, TU>(IEnumerable<T> input, Func<T, TU> getSortKey)
{
    var sorted = new List<TU>(input.Select(getSortKey));
    sorted.Sort();
    var firstHalf = new List<TU>();
    var secondHalf = new List<TU>();

    var sendToFirst = true;
    foreach (var current in sorted)
    {
        if (sendToFirst)
        {
            firstHalf.Add(current);
        }
        else
        {
            secondHalf.Add(current);
        }
        sendToFirst = !sendToFirst;
    }
    //to get the highest values on the outside just reverse 
    //the first list instead of the second
    secondHalf.Reverse();
    sorted = new List<TU>(firstHalf.Concat(secondHalf));

    //This assumes the sort keys are unique - if not, the implementation 
    //needs to use a SortedList<TU, T>
    return sorted.Select(s => input.First(t => s.Equals(getSortKey(t))));

}

And assuming non-unique keys:

public static IEnumerable<T> SortToMiddle<T, TU>(IEnumerable<T> input, Func<T, TU> getSortKey)
{
    var sendToFirst = true;
    var sorted = new SortedList<TU, T>(input.ToDictionary(getSortKey, t => t));
    var firstHalf = new SortedList<TU, T>();
    var secondHalf = new SortedList<TU, T>();

    foreach (var current in sorted)
    {
        if (sendToFirst)
        {
            firstHalf.Add(current.Key, current.Value);
        }
        else
        {
            secondHalf.Add(current.Key, current.Value);
        }
        sendToFirst = !sendToFirst;
    }
    //to get the highest values on the outside just reverse 
    //the first list instead of the second
    secondHalf.Reverse();
    return(firstHalf.Concat(secondHalf)).Select(kvp => kvp.Value);
}

Answer 3

Okay, I'm not going to question your sanity here since I'm sure you wouldn't be asking the question if there weren't a good reason :-)

Here's how I'd approach it. Create a sorted list, then simply create another list by processing the keys in order, alternately inserting before and appending, something like:

sortedlist = list.sort (descending)
biginmiddle = new list()
state = append
foreach item in sortedlist:
    if state == append:
        biginmiddle.append (item)
        state = prepend
    else:
        biginmiddle.insert (0, item)
        state = append

This will give you a list where the big items are in the middle. Other items will fan out from the middle (in alternating directions) as needed:

1, 3, 5, 7, 9, 10, 8, 6, 4, 2

To get a list where the larger elements are at the ends, just replace the initial sort with an ascending one.

The sorted and final lists can just be pointers to the actual items (since you state they're not simple integers) - this will minimise both extra storage requirements and copying.

Answer 4

I might go for something like this

static T[] SortFromMiddleOut<T, U>(IList<T> list, Func<T, U> orderSelector, bool largestInside) where U : IComparable<U>
{
    T[] sortedArray = new T[list.Count];

    bool add = false;
    int index = (list.Count / 2);
    int iterations = 0;

    IOrderedEnumerable<T> orderedList;
    if (largestInside)
        orderedList = list.OrderByDescending(orderSelector);
    else
        orderedList = list.OrderBy(orderSelector);

    foreach (T item in orderedList)
    {
        sortedArray[index] = item;
        if (add)
            index += ++iterations;
        else
            index -= ++iterations;

        add = !add;
    }

    return sortedArray;
}

Sample invocations:

int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

int[] sortedArray = SortFromMiddleOut(array, i => i, false);
foreach (int item in sortedArray)
    Console.Write("{0} ", item);

Console.Write("\n");

sortedArray = SortFromMiddleOut(array, i => i, true);
foreach (int item in sortedArray)
    Console.Write("{0} ", item);

With it being generic, it could be a list of Foo and the order selector could be f => f.Name or whatever you want to throw at it.

Answer 5

Maybe its not the best solution, but here's a nifty way...

Let Product[] parr be your array.

Disclaimer It's java, my C# is rusty. Untested code, but you get the idea.

int plen = parr.length
int [] indices = new int[plen];
for(int i = 0; i < (plen/2); i ++)
    indices[i] = 2*i + 1;   // Line1
for(int i = (plen/2); i < plen; i++)
    indices[i] = 2*(plen-i); // Line2

for(int i = 0; i < plen; i++)
{
    if(i != indices[i])
        swap(parr[i], parr[indices[i]]);
}

The second case, Something like this?

int plen = parr.length
int [] indices = new int[plen];
    for(int i = 0; i <= (plen/2); i ++)
       indices[i] = (plen^1) - 2*i;
    for(int i = 0; i < (plen/2); i++)
       indices[i+(plen/2)+1] = 2*i + 1;


for(int i = 0; i < plen; i++)
{
    if(i != indices[i])
        swap(parr[i], parr[indices[i]]);
}

Answer 6

The appropriate data structure is a LinkedList because it allows you to efficiently add to either end:

        LinkedList<int> result = new LinkedList<int>();

        int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

        Array.Sort(array);

        bool odd = true;

        foreach (var x in array)
        {
            if (odd)
                result.AddLast(x);
            else
                result.AddFirst(x);
            odd = !odd;
        }

        foreach (int item in result)
            Console.Write("{0} ", item);

No extra copying steps, no reversing steps, ... just a small overhead per node for storage.

Answer 7

C# Iterator version

(Very simple code to satisfy all conditions.)

One function to rule them all! Doesn't use intermediate storage collection (see yield keyword). Orders the large numbers either to the middle, or to the sides depending on the argument. It's implemented as a C# iterator

// Pass forward sorted array for large middle numbers,
//  or reverse sorted array for large side numbers.
//
public static IEnumerable<long> CurveOrder(long[] nums) {

    if (nums == null || nums.Length == 0)
        yield break; // Nothing to do. 

    // Move forward every two.
    for (int i = 0;  i < nums.Length;  i+=2)
        yield return nums[i];

    // Move backward every other two. Note: Length%2 makes sure we're on the correct offset.
    for (int i = nums.Length-1 - nums.Length%2;  i >= 0;  i-=2)
        yield return nums[i];
}

Example Usage

For example with array long[] nums = { 1,2,3,4,5,6,7,8,9,10,11 };

Start with forward sort order, to bump high numbers into the middle.

Array.Sort(nums); //forward sort
// Array argument will be:  { 1,2,3,4,5,6,7,8,9,10,11 };
long[] arrLargeMiddle = CurveOrder(nums).ToArray();

Produces: 1 3 5 7 9 11 10 8 6 4 2

Or, Start with reverse sort order, to push high numbers to sides.

Array.Reverse(nums); //reverse sort
// Array argument will be:  { 11,10,9,8,7,6,5,4,3,2,1 };
long[] arrLargeSides = CurveOrder(nums).ToArray();

Produces: 11 9 7 5 3 1 2 4 6 8 10

Significant namespaces are:

using System;
using System.Collections.Generic;
using System.Linq;

Note: The iterator leaves the decision up to the caller about whether or not to use intermediate storage. The caller might simply be issuing a foreach loop over the results instead.

---

Extension Method Option

Optionally change the static method header to use the this modifier public static IEnumerable<long> CurveOrder(this long[] nums) { and put it inside a static class in your namespace;
Then call the order method directly on any long[ ] array instance like so:

Array.Reverse(nums); //reverse sort
// Array argument will be:  { 11,10,9,8,7,6,5,4,3,2,1 };
long[] arrLargeSides = nums.CurveOrder().ToArray();

Just some (unneeded) syntactic sugar to mix things up a bit for fun. This can be applied to any answers to your question that take an array argument.

Answer 8

The fastest (but not the clearest) solution is probably to simply calculate the new index for each element:

        Array.Sort(array);

        int length = array.Length;
        int middle = length / 2;
        int[] result2 = new int[length];

        for (int i = 0; i < array.Length; i++)
        {
            result2[middle + (1 - 2 * (i % 2)) * ((i + 1) / 2)] = array[i];
        }