Sort objects using predefined list of sorted values

Question

I was wondering what would be the fastest way to sort an array of objects in the same order as a different array.

Here is an example in C#:

class MyClass
{
    public MyClass(int value)
    {
        this.value = value;
    }
    int value;
    public int Value
    {
        get { return value; }
        set { this.value = value; }
    }
}


    static List<int> sortedValuesList;
    static List<MyClass> objectList;

What is the fastest way of sorting objectList in the same order as sortedValuesList? There might be multiple objects with the same value.

I already have simple algorithm that can do it, but it's O(n^2) and requires extra memory.

EDIT: I guess it's not clear what I'm trying to do. Let's say a user sees a data grid of salespeople on the screen. He can sort them by any column he wants. Now the user clicks on a button and a table of customers is being shown. Every customer references one of the salespeople. I want to sort the customer list, based on the order of salespeople in previous data grid.

It's only a theoretical question as I don't need more performance. I was just wondering if there is some nice sorting algorithm when you need to use a lookup table to compare objects.

Answer 1

Break it into steps:

1. Go through your sortedValuesList and build a map from values -> index positions; this is O(n log n)
2. Go through your objects and add the index in a temporary field (again, O(n log n))
3. Sort your list by the temporary field (also O(n log n))

Total algorithm, O(n log n).

Alternatively, if you don't want to have the scratch field, you can look up the sort key via the map each time for an overall O(n (log n)^2)

Answer 2

Here is my very simple solution:

class Program
{
    static List<int> sortedValuesList;
    static List<MyClass> objectList;

    static void Main(string[] args)
    {
        //Generate some test data;
        Random random = new Random();
        objectList = new List<MyClass>();
        sortedValuesList = new List<int>();
        for (int i = 0; i < 10; i++) {
            MyClass a = new MyClass(random.Next() % 20);
            objectList.Add(a);
            if (!sortedValuesList.Contains(a.Value))
                sortedValuesList.Add(a.Value);
        }

        //Shuffle id's
        for (int i = sortedValuesList.Count - 1; i > 0; i--) {
            int n = random.Next(i + 1);
            int tempId = sortedValuesList[n];
            sortedValuesList[n] = sortedValuesList[i];
            sortedValuesList[i] = tempId;
        }

        Console.WriteLine("Reference list:");
        for (int i = 0; i < sortedValuesList.Count; i++) {
            Console.WriteLine(string.Format("{0,2} {1,5}", i, sortedValuesList[i]));
        }

        Console.WriteLine("unsorted list:");
        for (int i = 0; i < objectList.Count; i++) {
            Console.WriteLine(string.Format("{0,2} {1,5}", i, objectList[i].Value));
        }

        //Sort
        List<MyClass> sortedList = new List<MyClass>();
        foreach (int id in sortedValuesList) {
            sortedList.AddRange(
                objectList.FindAll(delegate(MyClass a) { return a.Value == id; })
            );
        }

        Console.WriteLine("After sorting:");
        for (int i = 0; i < sortedList.Count; i++) {
            Console.WriteLine(string.Format("{0,2} {1,5}", i,  sortedList[i].Value));
        }
        Console.ReadKey();

    }
}

Answer 3

First, do yourself a favor and use the generic version of List, so define your objectList as

static List<MyClass> objectList;

But, in either case, since a List is a collection of references to the actual objects, and since you seem to want to have the two lists in the same order, why not just assign one list to the other? What am I missing?

Answer 4

It sounds like you want a map instead:

static Dictionary<int, MyClass> sortedObjectList