Sorting a C# List<> without LINQ or delegates

Question

I have a list of objects, each of which have a position in 3D space. I need to sort this list by distance to an arbitrary point. Currently I'm doing this with:

_attachedEffectors = _attachedEffectors.OrderBy(x =>
        Mathf.Pow((x.transform.position.x - position.x), 2) + Mathf.Pow((x.transform.position.y - position.y), 2) + Mathf.Pow((x.transform.position.z - position.z), 2)
        ).ToList();

However, unfortunately I'm constrained by using Unity's compiler which is horrible with memory allocation and LINQ/delegates. Is there any way to sort a list like this without using LINQ or delegates? Optimally a search that allocates little or no memory as I need to run this thing many times a frame.

Also in future there may be other, arbitrary constraints on the search (e.g. if the distance from this particular object is more than some object-specific maximum distance, ignore it)

EDIT: I don't think I clearly explained my problem. I'm aware of sorting algorithms, however, all these solutions are regarding 2 independantly comparable objects. I'm asking how to sort these objects in regards to an external variable. That is, they need to be sorted by distance to a given point in space that the objects don't know about, but the sorting algorithm does. I know this could be done by the objects knowing about this point but that screams bad design to me.

Basically, I need a Sort() implementation that takes a parameter as well as the objects to be sorted, and uses that parameter in conjunction with the objects to sort the list (as seen in the LINQ implementation - position is parameter to the function this line is in).

You can easily implement your own sorting function, you can try bubblesort (or a hundred of other algorithms). — Kamil T, Jul 31 '14 at 08:25
If you need maximum performance and no memory allocation - do it yourself =). Or just copy one of the billions existing implementations of sorting algorithms (from bubble-sort to quicksort or merge sort). — Sasha, Jul 31 '14 at 08:25
http://msdn.microsoft.com/en-us/library/w56d4y5z%28v=vs.110%29.aspx Is that what you need? — Dennis_E, Jul 31 '14 at 08:26
Use [List.Sort](http://msdn.microsoft.com/en-us/library/234b841s%28v=vs.110%29.aspx) which takes `IComparer` overload. — Sriram Sakthivel, Jul 31 '14 at 08:27
LINQ is a horrible choice for high-performance applications. — game development germ, Jul 31 '14 at 08:52

score 3 · Answer 1 · answered Jul 31 '14 at 08:41

You could use the List.Sort(). However if you want to use this method, the object's type that is stored in your list should implement the IComparable interface. Below I provide you a sample of code, on which you can based on and write your own:

public class Customer : IComparable<Customer>
{
    public int Age { get; set; }
    public string FirstName { get; set; }
    public string LastName { get; set; }

    public Customer(int age, string firstName, string lastName)
    {
        Age = age;
        FirstName = firstName;
        LastName = lastName;
    }

    public int CompareTo(Customer other)
    {
        return Age.CompareTo(other.Age);
    }
}

class Program
{
    static void Main(string[] args)
    {
        List<Customer> customers = new List<Customer>
        {
            new Customer(25,"a","b"),
            new Customer(21,"c","d"),
            new Customer(22,"e","f"),
            new Customer(28,"g","i"),
            new Customer(30,"j","k"),
            new Customer(23,"l","m"),
            new Customer(31,"a","b"),
        };


        customers.Sort();

        foreach (var customer in customers)
        {
            Console.WriteLine(customer.Age);
        }

        Console.ReadKey();
    }
}

Regarding the complexity of List.Sort() method, as it is stated in MSDN,

On average, this method is an O(n log n) operation, where n is Count; in the worst case it is an O(n ^ 2) operation.

Sorting a C# List<> without LINQ or delegates

1 Answers1

Linked

Related