Sorting a list of objects based on another

public class Product
{
    public string Code { get; private set; }

    public Product(string code)
    {
        Code = code;
    }
}

List<Product> sourceProductsOrder = 
              new List<Product>() { new Product("BBB"), new Product("QQQ"), 
                                    new Product("FFF"), new Product("HHH"),
                                    new Product("PPP"), new Product("ZZZ")};

List<Product> products = 
              new List<Product>() { new Product("ZZZ"), new Product("BBB"),
                                    new Product("HHH")};

I have two product lists and I want to reorder the second one with the same order as the first. How can I reorder the products list so that the result would be : "BBB", "HHH", "ZZZ"?

EDIT: Changed Code property to public as @juharr mentioned

Upvotes: 3

Views: 489

Answers (5)

JLRishe
JLRishe

Reputation: 101652

Here is an efficient way to do this:

var lookup = sourceProductsOrder.Select((p, i) => new { p.Code, i })
                                .ToDictionary(x => x.Code, x => x.i);

products = products.OrderBy(p => lookup[p.Code]).ToList();

This should have a running time complexity of O(N log N), whereas an approach using IndexOf() would be O(N2).

This assumes the following:

  • there are no duplicate product codes in sourceProductsOrder
  • sourceProductsOrder contains all of the product codes in products
  • you make the Code field/property non-private

If needed, you can create a safeguard against the first bullet by replacing the first statement with this:

var lookup = sourceProductsOrder.GroupBy(p => p.Code)
                                .Select((g, i) => new { g.Key, i })
                                .ToDictionary(x => x.Key, x => x.i);

You can account for the second bullet by replacing the second statement with this:

products = products.OrderBy(p => 
            lookup.ContainsKey(p.Code) ?  lookup[p.Code] : Int32.MaxValue).ToList();

And you can use both if you need to. These will slow down the algorithm a bit, but it should continue to have an O(N log N) running time even with these alterations.

Upvotes: 1

Youp Bernoulli
Youp Bernoulli

Reputation: 5635

Easy come easy go:

IEnumerable<Product> result = 

products.OrderBy(p => sourceProductsOrder.IndexOf(sourceProductsOrder.FirstOrDefault(p2 => p2.Code == p.Code)));

This will provide the desired result. Objects with ProductCodes not available in the source list will be placed at the beginning of the resultset. This will perform just fine for a couple of hundred of items I suppose.

If you have to deal with thousands of objects than an answer like @Jon's will likely perform better. There you first create a kind of lookup value / score for each item and then use that for sorting / ordering.

The approach I described is O(n2).

Upvotes: 0

wilkesybear
wilkesybear

Reputation: 528

I would implement a compare function that does a lookup of the order from sourceProductsOrder using a hash table. The lookup table would look like

(key) : (value)
"BBB" : 1
"QQQ" : 2
"FFF" : 3
"HHH" : 4
"PPP" : 5
"ZZZ" : 6

Your compare could then lookup the order of the two elements and do a simple < (pseudo code):

int compareFunction(Product a, Product b){ 
    return lookupTable[a] < lookupTable[b]
}

Building the hash table would be linear and doing the sort would generally be nlogn

Upvotes: 0

Corey Adler
Corey Adler

Reputation: 16137

You would use IndexOf:

var sourceCodes = sourceProductsOrder.Select(s => s.Code).ToList();
products = products.OrderBy(p => sourceCodes.IndexOf(p.Code));

The only catch to this is if the second list has something not in the first list those will go to the beginning of the second list.

MSDN post on IndexOf can be found here.

Upvotes: 3

WeSt
WeSt

Reputation: 2684

You could try something like this

products.OrderBy(p => sourceProductsOrder.IndexOf(p))

if it is the same Product object. Otherwise, you could try something like:

products.OrderBy(p => GetIndex(sourceProductsOrder, p))

and write a small GetIndex helper method. Or create a Index() extension method for List<>, which would yield

products.OrderBy(p => sourceProductsOrder.Index(p))

The GetIndex method is rather simple so I omit it here.

(I have no PC to run the code so please excuse small errors)

Upvotes: 2

Related Questions