Как можно отсортировать массив по количеству наиболее повторяемых значений?

Question

[Cod Rob]

Например, есть отсортированный массив array:
1
1
1
2
3
3
4
4
4
4
5
6
6
7
8
Так вот, как отсортировать массив по количеству наиболее повторяемых значений:
4
4
4
4
1
1
1
6
6
3
3
8
7
5
2

Answer 1

[Илья]

int[] array = {1, 1, 1, 2, 3, 3, 4, 4, 4, 4, 5, 6, 6, 7, 8};
var sortedByFrequency = array
    .GroupBy(o => o)
    .OrderByDescending(o => o.Count())
    .ThenByDescending(o => o.Key)
    .SelectMany(o => o)
    .ToArray();
Console.WriteLine(string.Join(",",sortedByFrequency.Select(o => o.ToString())));
//4,4,4,4,1,1,1,6,6,3,3,8,7,5,2

Это если в одно LINQ выражение. Если нужно что-то очень быстрое для больших входных массивов, то стоит поискать что-то другое

Answer 2

[Василий Банников]

Можно как-то так через кастомный IComparer:

var arr = new int[] { 1, 1, 1, 2, 3, 3, 4, 4, 4, 4, 5, 6, 6, 7, 8 };

var index = arr.GroupBy(x => x).ToDictionary(x => x.Key, x => x.Count());
var result = arr.OrderByDescending(x => x, new CountComparer(index)).ToArray();

class CountComparer : IComparer<int>
{
    private readonly IReadOnlyDictionary<int, int> _index;
    public CountComparer(IReadOnlyDictionary<int, int> index)
    {
        _index = index;
    }

    public int Compare(int x, int y)
    {
        var comparsion = _index[x].CompareTo(_index[y]);
        if (comparsion == 0)
            return x.CompareTo(y);
        return comparsion;
    }
}

Ну или можно самому написать алгоритм, но всё равно первым шагом надо будет пройтись по всему массиву с подсчётом повторений.
Хотя мб можно как-то оптимизировать, если предположить, что изначально массив отсортирован по возрастанию.

Answer 3

[Дмитрий Беляев]

Можно использовать вариацию сортировки подсчетом, в которой на втором шаге сортируются не сами значения, а их количественная оценка

Comments

[Василий Банников]

Если я правильно понял, то counting sort - этопросто ещё один алгоритм сортировки, просто вместо перекладывания чисел используется массив с количеством копий.

Автор же хочет отсортировать числа так, чтобы на первом месте были числа с наибольшим количеством копий в массиве, а в конце - с наименьшим

[Дмитрий Беляев]

Если я правильно понял, то counting sort - этопросто ещё один алгоритм сортировки, просто вместо перекладывания чисел используется массив с количеством копий.

Василий Банников, да, это еще один алгоритм сортировки, особенностью которого является то, что в некоторых конкретных случаях его сложность сводится к O(n)

Автор же хочет отсортировать числа так, чтобы на первом месте были числа с наибольшим количеством копий в массиве, а в конце - с наименьшим

И это вполне можно сделать на базе этого алгоритма, только в оригинальном алгоритме внутренняя сортировка происходит по множеству уникальных значений, а тут надо переделать его так, чтоб сортировались их количественные показатели.

[Дмитрий Беляев]

Василий Банников, я к сожалению давно не писал на шарпе, и не уверен, что делаю все оптимально, но примерно так это делается:

class Program
{
    static void Main()
    {
        int[] array = { 4, 4, 4, 4, 1, 1, 1, 6, 6, 3, 3, 8, 7, 5, 2 };
        int[] result = SortByCount(array);
        Console.WriteLine(string.Join(",", result));
    }

    static int[] SortByCount(int[] array)
    {
        var dict = new Dictionary<int, uint>();
        foreach (var value in array)
        {
            uint count = dict.GetValueOrDefault<int, uint>(value, 0);
            dict.Remove(value);
            dict.Add(value, count + 1);
        }
        var result = new int[array.Length];
        uint i = 0;
        foreach (var kv in dict.OrderByDescending(kv => kv.Value))
        {
            uint limit = i + kv.Value;
            for (; i < limit; i++)
            {
                result[i] = kv.Key;
            }
        }
        return result;
    }
}

[Василий Банников]

Дмитрий Беляев, похоже на правду. Скопируйте в ответ, чтобы я его отметил.
Хотя не. Пожодите 5 минут, немного поправлю

[Василий Банников]

Дмитрий Беляев,

var array = new []{1, 1, 1, 2, 3, 3, 4, 4, 4, 4, 5, 6, 6, 7, 8};
SortByCountInPlace(new Span<int>(array));

Console.WriteLine(string.Join(',', array));

static void SortByCountInPlace(Span<int> array)
{
    var dict = new Dictionary<int, int>(array.Length);
    foreach (var value in array)
    {
        var count = dict.GetValueOrDefault<int, int>(value, 0);
        dict[value] = count+1;
    }
    var i = 0;
    // Только вот тут самая главная проблема
    foreach (var (num, count) in dict.OrderByDescending(kv => kv.Value).ThenByDescending(kv=>kv.Key))
    {
        array.Slice(i, count).Fill(num);
        i+=count;
    }
}