Sort groups based on values within groups

Question

I am trying to sort an array that contains logical groups of people, and the people's scores.

Name   | Group | Score
----------------------
Alfred |     1 |     3
Boris  |     3 |     3
Cameron|     3 |     1
Donna  |     1 |     2
Emily  |     2 |     2

The people should be sorted by group, based on the lowest score in the group. Therefore, group 3 is first, because it contains the person with the lowest score. Then the people in group 1 because it has the person with the next lowest score (and a lower group number than group 2).

So the result would be: Cameron, Boris, Donna, Alfred, Emily

I have accomplished this, but I am wondering if there is a better way of doing it. I receive an array, and end up sorting the array in the correct order.

I use LINQ (mostly obtained from Linq order by, group by and order by each group?) to create a target sorting array that maps where a person should be, compared to where they currently are in the array.

I then use Array.Sort using my target sorting array, but the array the LINQ statement creates is "reversed" in terms of indices and values, so I have to reverse the indices and values (not the order).

I have attached my code below. Is there a better way of doing this?

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

namespace Sorter
{
    class Program
    {
        static void Main(string[] args)
        {
            // Sample person array.
            // Lower score is better.
            Person[] peopleArray = new Person[]
            {
                new Person { Name = "Alfred", Group = "1", Score = 3, ArrayIndex = 0 },
                new Person { Name = "Boris", Group = "3", Score = 3, ArrayIndex = 1 },
                new Person { Name = "Cameron", Group = "3", Score = 1, ArrayIndex = 2 },
                new Person { Name = "Donna", Group = "1", Score = 2, ArrayIndex = 3 },
                new Person { Name = "Emily", Group = "2", Score = 2, ArrayIndex = 4 }
            };

            // Create people list. 
            List<Person> peopleModel = peopleArray.ToList();

            // Sort the people based on the following:
            // Sort people into groups (1, 2, 3)
            // Sort the groups by the lowest score within the group.
            // So, the first group would be group 3, because it has the
            // member with the lowest score (Cameron with 1).
            // The people are therefore sorted in the following order:
            //  Cameron, Boris, Donna, Alfred, Emily
            int[] targetOrder = peopleModel.GroupBy(x => x.Group)
                                           .Select(group => new
                                           {
                                               Rank = group.OrderBy(g => g.Score)
                                           })
                                           .OrderBy(g => g.Rank.First().Score)
                                           .SelectMany(g => g.Rank)
                                           .Select(i => i.ArrayIndex)
                                           .ToArray();

            // This will give the following array:
            // [2, 1, 3, 0, 4]
            // I.e: Post-sort, 
            //  the person who should be in index 0, is currently at index 2 (Cameron).
            //  the person who should be in index 1, is currently at index 1 (Boris).
            //                 etc.

            // I want to use my target array to sort my people array.

            // However, the Array.sort method works in the reverse.
            // For example, in my target order array:  [2, 1, 3, 0, 4]
            //    person currently at index 2 should be sorted into index 0.
            // I need the following target order array: [3, 1, 0, 2, 4], 
            //    person currently at index 0, should be sorted into index 3
            // So, "reverse" the target order array.
            int[] reversedArray = ReverseArrayIndexValue(targetOrder);

            // Finally, sort the base array.
            Array.Sort(reversedArray, peopleArray);

            // Display names in order.
            foreach (var item in peopleArray)
            {
                Console.WriteLine(item.Name);
            }

            Console.Read();
        }

        /// <summary>
        /// "Reverses" the indices and values of an array.
        /// E.g.: [2, 0, 1] becomes [1, 2, 0].
        /// The value at index 0 is 2, so the value at index 2 is 0.
        /// The value at index 1 is 0, so the value at index 0 is 1.
        /// The value at index 2 is 1, so the value at index 1 is 2.
        /// </summary>
        /// <param name="target"></param>
        /// <returns></returns>
        private static int[] ReverseArrayIndexValue(int[] target)
        {
            int[] swappedArray = new int[target.Length];

            for (int i = 0; i < target.Length; i++)
            {
                swappedArray[i] = Array.FindIndex(target, t => t == i);
            }

            return swappedArray;
        }
    }
}

What is your desired end result? Do you just want a `List` sorted by your criteria? I'm a little unclear with all the arrays you are throwing around what is just part of your attempted workings and what is required output... — Chris, Jun 28 '17 at 17:49
Both groups 1 and 2 have the next lowest score. What criterion would be used to determine that group 1 is next? — Eric Olsson, Jun 28 '17 at 17:51
@Chris My desired end result is the array I started with (peopleArray) in this case, in sorted order. — SortingAndOrdering, Jun 28 '17 at 17:53
@Eric I suppose in this case, a lower ArrayIndex (or the order in the starting array). It's not hugely important beyond the group and score. — SortingAndOrdering, Jun 28 '17 at 17:55
@JeroenHeier Anything that is shorter/cleaner or more efficient. I especially don't like the part where I reverse the index/value in my sort target array. — SortingAndOrdering, Jun 28 '17 at 18:09
Do you really need the `ArrayIndex` property? Or it's just because of your current algorithm? — Ivan Stoev, Jun 28 '17 at 18:11

score 2 · Answer 1 · answered Jun 28 '17 at 18:07

2

Not sure if I really understood what the wished outcome should be, but this at least gives same order as mentioned in example in comments:

   var sortedNames = peopleArray
            // group by group property
            .GroupBy(x => x.Group)
            // order groups by min score within the group
            .OrderBy(x => x.Min(y => y.Score))
            // order by score within the group, then flatten the list
            .SelectMany(x => x.OrderBy(y => y.Score))
            // doing this only to show that it is in right order
            .Select(x =>
            {
                Console.WriteLine(x.Name);
                return false;
            }).ToList();

answered Jun 28 '17 at 18:07

Giedrius

8,430
6
50
91

Good job. My only comment would be that in your Test Select you should `return x` instead of `return false`. Otherwise you get a list of boolean at the end. And while I know that in live code that last Select won't be there its still nicer for a demo to be as fully functional as possible. – Chris Jun 28 '17 at 18:14
The LINQ sorting in this works perfectly, but is there a way to apply the sort to the original array? I don't want to end up with a sorted copy of it, I need the original one sorted. – SortingAndOrdering Jun 28 '17 at 18:20

Ivan Stoev · Accepted Answer · 2017-06-28T18:31:40.827

As I understand, you want to sort the input array in place.

First, the sorting part can be simplified (and made more efficient) by first OrderBy Score and then GroupBy Group, utilizing the defined behavior of Enumerable.GroupBy:

The IGrouping<TKey, TElement> objects are yielded in an order based on the order of the elements in source that produced the first key of each IGrouping<TKey, TElement>. Elements in a grouping are yielded in the order they appear in source.

Once you have that, all you need is to flatten the result, iterate it (thus executing it) and put the yielded items in their new place:

var sorted = peopleArray
    .OrderBy(e => e.Score)
    .ThenBy(e => e.Group) // to meet your second requirement for equal Scores
    .GroupBy(e => e.Group)
    .SelectMany(g => g);
int index = 0;
foreach (var item in sorted)
    peopleArray[index++] = item;

This works perfectly. Thank you. Gosh.. it's so much less code than my original implementation. — SortingAndOrdering, Jun 28 '17 at 18:39

William Han · Answer 3 · 2017-06-28T19:10:56.320

If your desired result is less line of codes. How about this?

var peoples = peopleModel.OrderBy(i => i.Score).GroupBy(g => 
              g.Group).SelectMany(i => i, (i, j) => new { j.Name });

1) Order list by scores

2) Group it by grouping

3) Flatten the grouped list and create new list with "Name" property using SelectMany

For information using anonymous type https://dzone.com/articles/selectmany-probably-the-most-p

score 0 · Answer 4 · answered Jun 28 '17 at 18:58

int[] order = Enumerable.Range(0, peopleArray.Length)
                        .OrderBy(i => peopleArray[i].Score)
                        .GroupBy(i => peopleArray[i].Group)
                        .SelectMany(g => g).ToArray();          // { 2, 1, 3, 0, 4 }

Array.Sort(order, peopleArray); 

Debug.Print(string.Join(", ", peopleArray.Select(p => p.ArrayIndex)));  // "3, 1, 0, 2, 4"

Sort groups based on values within groups

4 Answers4