Sort a C# list by word

Question

I want to sort a C# list by word. Assume I have a C# list (of objects) which contains following words:

[{id:1, name: "ABC"},
 {id:2, name: "XXX"},
 {id:3, name: "Mille"},
 {id:4, name: "YYY"},
 {id:5, name: "Mill",
 {id:6, name: "Millen"},
 {id:7, name: "OOO"},
 {id:8, name: "GGGG"},
 {id:9, name: null},
 {id:10, name: "XXX"},
 {id:11, name: "mil"}]  

If user pass Mil as a search key, I want to return all the words starting with the search key & then all the words which does not match criteria & have them sort alphabetically.

Easiest way I can think of is to run a for loop over the result set, put all the words starting with search key into one list and put the renaming words into another list. Sort the second list and them combine both the list to return the result.

I wonder if there is a smarter or inbuilt way to get the desired result.

Answer 1

Sure! You will sort by the presence of a match, then by the name, like this:

var results = objects.OrderByDescending(o => o.Name.StartsWith(searchKey))
                     .ThenBy(o => o.Name);

Note that false comes before true in a sort, so you'll need to use OrderByDescending.

As AlexD points out, the name can be null. You'll have to decide how you want to treat this. The easiest way would be to use o.Name?.StartsWith(searchKey) ?? false, but you'll have to decide based on your needs. Also, not all Linq scenarios support null propagation (Linq To Entities comes to mind).

Answer 2

This should do it, but there's probably a faster way, maybe using GroupBy somehow.

var sorted = collection
    .Where(x => x.Name.StartsWith(criteria))
    .OrderBy(x => x.Name)
    .Concat(collection
           .Where(x => !x.Name.StartsWith(criteria))
           .OrderBy(x => x.Name))

Answer 3

You can try GroupBy like this:

var sorted = collection
  .GroupBy(item => item.Name.StartsWith(criteria))
  .OrderByDescending(chunk => chunk.Key)
  .SelectMany(chunk => chunk
    .OrderBy(item => item.Name));

• Separate items into two groups (meets and doesn't meet the criteria)
• Order the groups as whole (1st that meets)
• Order items within each group
• Finally combine the items

Answer 4

There's nothing C#-specific to solve this, but it sounds like you're really looking for algorithm design guidance.

You should sort the list first. If this is a static list you should just keep it sorted all the time. If the list is large, you may consider using a different data structure (Binary Search Tree, Skip List, etc.) which is more optimized for this scenario.

Once it's sorted, finding matching elements becomes a simple binary search. Move the matching elements to the beginning of the result set, then return.

Answer 5

Add an indicator of a match into the select, and then sort on that:

void Main()
{
    word[] Words = new word[11]
    {new word {id=1, name= "ABC"},
    new word {id=2, name= "XXX"},
    new word {id=3, name= "Mille"},
    new word {id=4, name= "YYY"},
    new word {id=5, name= "Mill"},
    new word {id=6, name= "Millen"},
    new word {id=7, name= "OOO"},
    new word {id=8, name= "GGGG"},
    new word {id=9, name= null},
    new word {id=10, name= "XXX"},
    new word {id=11, name= "mil"}};

    var target = "mil";
    var comparison = StringComparison.InvariantCultureIgnoreCase;

    var q =  (from w in Words
              where w.name != null
              select new {
                           Match = w.name.StartsWith(target, comparison)?1:2, 
                           name = w.name})
                .OrderBy(w=>w.Match).ThenBy(w=>w.name);
    q.Dump();       
}

public struct word
{
    public int id;
    public string name;
}

Answer 6

It is probably not easier but you could create a class that implements IComparable Interface and have a property Mil that is used by CompareTo.

Then you could just call List.Sort(). And you can pass an IComparer to List.Sort.

It would probably be the most efficient and you can sort in place rather than producing a new List.

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.

 public int CompareTo(object obj) 
 {
    if (obj == null) return 1;

    Temperature otherTemperature = obj as Temperature;
    if (otherTemperature != null)
    {
        if(string.IsNullOrEmpty(Mil) 
            return this.Name.CompareTo(otherTemperature.Name); 
        else if(this.Name.StartsWith(Mill) && otherTemperature.Name.StartsWith(Mill)
            return this.Name.CompareTo(otherTemperature.Name);
        else if(!this.Name.StartsWith(Mill) && !otherTemperature.Name.StartsWith(Mill)
            return this.Name.CompareTo(otherTemperature.Name); 
        else if(this.Name.StartsWith(Mill))
            return 1;
        else 
            return 0;
    }
    else
       throw new ArgumentException("Object is not a Temperature");
 }

You will need to add how you want null Name to sort

Answer 7

First create a list of the words that match, sorted. Then add to that list all of the words that weren't added to the first list, also sorted.

public IEnumerable<Word> GetSortedByMatches(string keyword, Word[] words)
{
    var result = new List<Word>(words.Where(word => word.Name.StartsWith(keyword))
        .OrderBy(word => word.Name));
    result.AddRange(words.Except(result).OrderBy(word => word.Name));
    return result;
} 

Some of the comments suggest that it should be case-insensitive. That would be

public IEnumerable<Word> GetSortedByMatches(string keyword, Word[] words)
{
    var result = new List<Word>(
        words.Where(word => word.Name.StartsWith(keyword, true)) //<-- ignoreCase
        .OrderBy(word => word.Name));
    result.AddRange(words.Except(result).OrderBy(word => word.Name));
    return result;
}