Сортування колекцій

1. Вступ

Якщо ви коли-небудь мали ящик із шкарпетками, у якому намагалися знайти пару, ви вже стикалися з проблемою сортування. Коли все лежить як попало, пошук потрібної речі перетворюється на квест. У програмуванні з колекціями — та сама історія.

Сортування — це процес упорядкування елементів колекції за певним критерієм (наприклад, за алфавітом, за значенням, датою тощо). Це важливо для:

• Відображення даних користувачеві (ніхто не любить хаос).
• Спрощення пошуку (наприклад, бінарний пошук можливий лише у відсортованих колекціях).
• Порівняння, складання звітів, експорту та інших операцій.

Питання на мільйон: «А якщо у мене всього п’ять елементів, можна не сортувати?» — теоретично так, але щойно п’ять перетворюються на п’ятсот чи п’ять тисяч, без автоматизації не обійтися.

У .NET є два основні підходи до сортування:

• Зміна вихідної колекції (наприклад, сортування List<T> методом Sort).
• Створення нової відсортованої копії колекції (наприклад, клонування масиву, а потім сортування).

Сортування списків за допомогою методу .Sort()

Метод Sort() є у класу List<T>, оскільки цей клас реалізує інтерфейс IList<T>, надає доступ за індексом і дозволяє змінювати порядок елементів.

Приклад — сортування чисел за зростанням:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var numbers = new List<int> { 5, 2, 9, 1, 5, 6 };
        numbers.Sort();
        Console.WriteLine("Сортування за зростанням:");
        foreach(var number in numbers)
        {
            Console.Write($"{number} "); // 1 2 5 5 6 9
        }
    }
}

Тут відбувається сортування «на місці»: вихідний список numbers змінюється, елементи у ньому переставляються.

Сортування рядків

Сортування чудово працює і для рядків:

var words = new List<string> { "апельсин", "яблуко", "банан", "груша" };
words.Sort();
Console.WriteLine(string.Join(", ", words)); // апельсин, банан, груша, яблуко

Цікавий факт: за замовчуванням рядкове сортування відбувається за порядком Unicode, а не за «людським» алфавітом (особливо для різних мов, враховуйте це у багатомовних застосунках).

2. Сортування за власними правилами

Іноді сортування «за замовчуванням» не підходить. Наприклад, ви хочете відсортувати користувачів не за іменем, а за віком чи датою реєстрації.

Сортування за допомогою лямбда-виразу (метод Sort(Comparison<T>))

Метод Sort можна викликати так, щоб передати спеціальне правило сортування — функцію порівняння двох елементів.

Сортування користувачів за віком:

class User
{
    public string Name { get; set; }
    public int Age { get; set; }
}

// ...

var users = new List<User>
{
    new User { Name = "Аліса", Age = 30 },
    new User { Name = "Боб", Age = 25 },
    new User { Name = "Єва", Age = 35 }
};

users.Sort((u1, u2) => u1.Age.CompareTo(u2.Age));

foreach (var user in users)
{
    Console.WriteLine($"{user.Name}: {user.Age}");
}
// Виведення:
// Боб: 25
// Аліса: 30
// Єва: 35

Як це працює? Лямбда (u1, u2) => u1.Age.CompareTo(u2.Age) повертає від’ємне число, якщо u1 молодший, додатне — якщо старший, і 0, якщо вік збігається.

Використання інтерфейсу IComparer<T>

Іноді варто винести правило сортування в окремий клас, наприклад, якщо у вас багато колекцій і складна логіка.

class UserAgeComparer : IComparer<User>
{
    public int Compare(User x, User y)
    {
        return x.Age.CompareTo(y.Age);
    }
}

// ...

var users = new List<User>{ /* ... */ };
users.Sort(new UserAgeComparer()); // тепер сортування за віком

Це зручно, якщо сортування потрібне в різних частинах застосунку або сортувань багато.

Сортування за кількома полями вручну

Якщо в деяких користувачів однаковий вік, але ви хочете відсортувати їх за іменем усередині однієї вікової групи:

users.Sort((u1, u2) => {
    int ageCompare = u1.Age.CompareTo(u2.Age);
    if (ageCompare != 0)
        return ageCompare;
    else
        return u1.Name.CompareTo(u2.Name);
});

Тепер сортування спочатку за віком, потім — за іменем.

3. Сортування копії колекції (без зміни оригіналу)

Якщо ви не хочете змінювати вихідний список, скопіюйте його перед сортуванням:

var copy = new List<int>(numbers);
copy.Sort();

Для користувацьких об’єктів — так само:

var usersCopy = new List<User>(users);
usersCopy.Sort((a, b) => a.Age.CompareTo(b.Age));

4. Сортування масивів

З масивами (T[]) усе теж доволі просто:

int[] numbers = { 4, 2, 9, 7 };
Array.Sort(numbers); // змінюється оригінальний масив

Для «власного» сортування:

Array.Sort(numbers, (a, b) => b.CompareTo(a)); // сортування за спаданням

Зверніть увагу, що Array.Sort змінює оригінальний масив, а не повертає новий. Якщо треба зберегти оригінал, скопіюйте масив заздалегідь:

int[] oldNumbers = { 3, 2, 1 };
int[] copy = (int[])oldNumbers.Clone();
Array.Sort(copy);

5. «Сортування» словників (Dictionary<TKey, TValue>)

Dictionary<TKey, TValue> — це неупорядкована колекція за своєю суттю (тобто не гарантує порядок під час ітерації). Але іноді хочеться отримати «відсортовані пари».

Щоб отримати відсортовані ключі або значення, створіть список, скопіюйте туди пари й відсортуйте як треба:

var dict = new Dictionary<string, int>
{
    { "яблуко", 2 },
    { "апельсин", 5 },
    { "груша", 3 }
};

// Сортування за ключем:
var keyValueList = new List<KeyValuePair<string, int>>(dict);
keyValueList.Sort((a, b) => a.Key.CompareTo(b.Key));
foreach (var kv in keyValueList)
{
    Console.WriteLine($"{kv.Key}: {kv.Value}");
}

// Сортування за значенням:
keyValueList.Sort((a, b) => a.Value.CompareTo(b.Value));
foreach (var kv in keyValueList)
{
    Console.WriteLine($"{kv.Key}: {kv.Value}");
}

Якщо треба отримати відсортований список ключів або значень:

var sortedKeys = new List<string>(dict.Keys);
sortedKeys.Sort();

var sortedValues = new List<int>(dict.Values);
sortedValues.Sort();

Але пам’ятайте, що структура Dictionary не змінюється — ви просто отримуєте відсортований перебір. У .NET 9 з’явиться OrderedDictionary<TKey, TValue>, який зберігатиме порядок елементів. Не часто, але іноді така структура справді потрібна.

6. Корисні нюанси

Чи обов’язково реалізовувати інтерфейс порівняння?

Усе просто: якщо ви хочете, щоб ваші об’єкти «знали», як їх порівнювати (наприклад, за датою чи іменем), реалізуйте інтерфейс IComparable<T>.

class Product : IComparable<Product>
{
    public string Name { get; set; }
    public decimal Price { get; set; }

    public int CompareTo(Product other)
    {
        return Price.CompareTo(other.Price);
    }
}

Тепер ви можете робити так:

var products = new List<Product> { /* ... */ };
products.Sort(); // сортує за ціною

Якщо порівняння за замовчуванням не підходить — використовуйте IComparer<T> або передавайте лямбду, як показано вище.

Сортування списку користувачів за алфавітом

Припустімо, у нашому застосунку є список користувачів:

List<string> users = new List<string> { "Віктор", "Анна", "Катерина", "Борис" };
users.Sort(); // тепер users відсортований: Анна, Борис, Віктор, Катерина

Розподіл завдань за терміновістю

class Task
{
    public string Title { get; set; }
    public int Priority { get; set; } // 1 — терміново, 2 — важливо, 3 — можна відкласти
}

var todo = new List<Task>
{
    new Task { Title = "Зробити домашку", Priority = 2 },
    new Task { Title = "Купити хліб", Priority = 1 },
    new Task { Title = "Подивитись серіал", Priority = 3 }
};

todo.Sort((a, b) => a.Priority.CompareTo(b.Priority));

foreach (var task in todo)
    Console.WriteLine($"{task.Priority}: {task.Title}");

Порівняння способів сортування

List<T>

Sort()

T[]

Array.Sort()

Dictionary<TKey, TValue>

7. Типові помилки та нюанси сортування

Сортування на місці — змінює вихідну колекцію! Якщо вхідні дані не мають змінюватися — скопіюйте їх заздалегідь.

Спроба сортувати незмінювану колекцію (наприклад, ReadOnlyCollection<T>) призведе до помилки виконання.

Порівняння рядків у різних культурах: сортування рядків (особливо з кирилицею, умлаутами тощо) може відрізнятися на різних локалях. Для коректного сортування використовуйте Comparer.Create(...) з потрібною культурою.

Сортування словників не змінює їх структуру — завжди повертається нова послідовність пар (або новий список).

Для складного порядку використовуйте інтерфейс IComparer<T> із вашою логікою.

Ось приклад неправильного підходу (типова пастка):

var numbers = new List<int> { 1, 2, 3 };
var sorted = numbers.Sort(); // ПОМИЛКА: Sort() повертає void!

Правильно:

numbers.Sort(); // змінює numbers на місці

// Якщо потрібна нова колекція:
var sorted = new List<int>(numbers);
sorted.Sort();