Сортировка списка (list) одна из наиболее популярных задача, встающих перед разработчиками. К счастью платформа .NET создана и создается с учетом этих потребностей, поэтому все что вам нужно сделать — это выбрать какой из методов сортировки использовать в своих программах.
В этой статье мы рассмотрим различные методы сортировки списков, а так же сравним их между собой.
Сортировку списка можно произвести тремя различными способами.
- С помощью метода Sort
- С помощью LINQ
- С помощью собственной реализации алгоритмов сортировки
Примечание. Способы сортировки, изложенные в этой статье, в целом применимы и к другим коллекциям .NET.
Sort: сортировка списка
Метод Sort относится непосредственно к классу List. Прежде, чем вдаваться в подробности давайте рассмотрим пример.
Пример программы, использующей метод Sort класса List для сортировки списка чисел (C# .NET)
using System;
using System.Collections.Generic;
namespace ListSort
{
class Program
{
static void Main(string[] args)
{
// Создаем список.
var list = new List<int>{44, 10, 5, 35, 5, 20};
// Сортируем.
list.Sort();
// Проверям.
foreach (var value in list)
{
Console.WriteLine(value);
}
Console.ReadLine();
}
}
}
Вывод консоли
5
5
10
20
35
44
Мы получили список, отсортированный по возрастанию. Как это работает?
Алгоритм сортировки
В методе Sort используется алгоритм под название QuickSort. В этой реализации осуществляется нестрогая сортировка, то есть сохранение порядка двух одинаковых элементов не гарантируется. Сложность алгоритма в среднем составляет O(n*log n), где n равно числу элементов списка; в худшем случае порядок сложности составляет O(n^2), что совсем неплохо.
Интерфейс IComparable
Вы можете создать список, содержащий строки, дробные числа, экземпляры различных классов, но сортировка все равно будет работать. Откуда метод List узнает как сортировать элементы? С помощью интерфейса IComparable. Большая часть встроенных типов и некоторые стандартные классы реализуют этот интерфейс. Вы можете реализовать его в своих классах.
Сортировка в обратном порядке
Вы так можете захотеть отсортировать элементы списка в обратном порядке. Используйте для этого метод Reverse.
Пример программы, сортирующей элементы списка в обратном порядке (по убыванию) (C# .NET)
// Сортируем.
list.Sort();
// Меняем порядок элементов.
list.Reverse();
// Проверям.
foreach (var value in list)
{
Console.WriteLine(value);
}
Вывод консоли
44
35
20
10
5
5
LINQ: сортировка списка
Так как коллекция List реализует интерфейс IEnumerable, то с объектами этого типа может использовать LINQ. Рассмотрим пример. В нем используется метод OrderBy, который возвращает новую отсортированную коллекцию. Обратите внимание на подключание пространства имен System.Linq.
Пример программы, сортирующей с использованием OrderBy LINQ (C# .NET)
using System;
using System.Collections.Generic;
using System.Linq;
namespace ListSort
{
class Program
{
static void Main(string[] args)
{
// Создаем список.
var list = new List<string>{"Анна", "Юля", "Маша"};
// Сортируем с помощью LINQ.
var sortedList = list.OrderBy(x => x);
// Проверям.
foreach (var value in sortedList)
{
Console.WriteLine(value);
}
Console.ReadLine();
}
}
}
Вывод консоли
Анна
Маша
Юля
По умолчанию метод OrderBy сортирует элементы по возрастанию, но вы можете отсортировать элементы и в обратном порядке (по убыванию), используя метод OrderByDescending.
же после вызова метода OrderBy.
Она откладывается до обращения
к элементам новой коллекции.
Метод OrderBy возвращает объект типа IOrderedEnumerable<T> его особенность, да и особенность практических всех методов, относящихся к LINQ, в том, что сортировка не выполняется сразу же после вызова метода OrderBy. Она откладывается до того момента, когда отсортированные элементы, фактически, не будут запрошены. У нас это происходит сразу же, в итераторе foreach.
Другими словами это просто декоратор, мы устанавливаем некий флаг, который сообщает среде исполнения кода, что когда мы обратимся к этой коллекции, нам нужны будут отсортированные элементы, а сейчас выполнять сортировку не надо. В этом нет ничего страшного, это очень полезная особенность. Но об этом следует написать отдельную стать.
Если вам по каким-то причинам необходимо выполнить сортировку сразу же, то используйте метод ToList:
var sortedList = list.OrderBy(x => x).ToList();
Алгоритм сортировки
В методе OrderBy используется тот же алгоритм, что и в методе Sort (QuickSort), за тем исключением что гарантируется порядок одинаковых элементов (такой же какой был до сортировки).
Дополнительные возможности
В примере, вы могли заметить, что в метод OrderBy было передано лямбда-выражение вида x => x. Это очень мощный инструмент, так как с помощью подобного выражения мы можем задать более сложные условия сортировки.
Предположим, у нас есть класс User, мы используем его для хранения информации о пользователях. Нам необходимо отобразить, отсортированный по имени список пользователей. Как это сделать?
Пример программы сортировки объектов произвольного типа, находящихся в списке List (C# .NET)
using System;
using System.Collections.Generic;
using System.Linq;
namespace ListSort
{
// Класс, объекты которого мы хотим упорядочить.
class User
{
public int Id;
public string Username;
public override string ToString()
{
return "[" + Id + "]: " + Username;
}
}
class Program
{
static void Main(string[] args)
{
// Создаем список.
var list = new List<User>();
list.Add(new User { Id = 1, Username = "Lover" });
list.Add(new User { Id = 2, Username = "Anna" });
list.Add(new User { Id = 3, Username = "Moneyman" });
list.Add(new User { Id = 4, Username = "Gorlem" });
// Сортируем с помощью LINQ.
var sortedList = list.OrderBy(x => x.Username);
// Проверям.
foreach (var value in sortedList)
{
Console.WriteLine(value);
}
Console.ReadLine();
}
}
}
Вывод консоли
[2]: Anna
[4]: Gorlem
[1]: Lover
[3]: Moneyman
С помощью лямбда-выражения x => x.Username мы указали какое свойство объекта использовать для сравнения при сортировке.
Примечание. Для более удобного и изящного вывода результата в консоль мы переопределили метод ToString.
Реализация собственного алгоритма сортировки
Если вы подумали, что я сейчас напишу примеры подобной реализации, то вы немного ошиблись. Я крайне не рекомендую заниматься изобретение велосипедов. Алгоритмы сортировки, реализованных в методах Sort и OrderBy имеют оптимальную скорость для большинства практических задач.
В некоторых случаях, больше связанных с обработкой исследовательских данных вам могут понадобиться специфические алгоритмы, но тогда лучше задуматься о другом, действительно ли списки подходят вам для этой цели? Рассмотрите возможность использования других коллекций. Вы можете узнать больше об алгоритмах сортировки здесь.
Сравнение Sort и OrderBy
На самом деле здесь сравнивать нечего, метод OrderBy является более обобщенным и принадлежит интерфейсу IEnumerable. Он используется не только для списков, но и для других .NET коллекций. Фактически это просто удобная оболочка вокруг метода Sort. Другими словами, вызывая метод OrderBy, вы взываете метод Sort. При этом теряете производительность на декорировании этого вызова и причем существенно.
Посмотрим на цифры, для этого используем benchmark от Julien Lebosquain
Тестирование производительности методов Sort и OrderBy (C# .NET)
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
namespace ListSort
{
class Program
{
private static List<int> CreateList(int size)
{
// Заполняем список случайными элементами
var random = new Random(589134554);
var list = new List<int>(size);
for (int i = 0; i < size; ++i) list.Add(random.Next());
return list;
}
private static void Benchmark(int size, bool output = true)
{
// Два списка для сравнения, один будем
List<int> list1 = CreateList(size);
List<int> list2 = CreateList(size);
// Таймер выполнения сортировки
Stopwatch stopwatch = Stopwatch.StartNew();
// Тест метода Sort
list1.Sort();
stopwatch.Stop();
double elapsedSort = stopwatch.Elapsed.TotalMilliseconds;
if (output) Console.WriteLine("List({0}).Sort(): {1}ms (100%)", size, elapsedSort);
stopwatch.Restart();
// Тест метода OrderBy (ToList - обязательно, чтобы выполнить сортировку немедленно)
list2.OrderBy(i => i).ToList();
stopwatch.Stop();
double elapsedOrderBy = stopwatch.Elapsed.TotalMilliseconds;
if (output) Console.WriteLine("List({0}).OrderBy(): {1}ms ({2:.00%})", size, elapsedOrderBy, elapsedOrderBy / elapsedSort);
}
internal static void Main()
{
// Разогрев
Benchmark(1000, false);
// Тесты с разным количеством значений в списках
Benchmark(10);
Benchmark(100);
Benchmark(1000);
Benchmark(10000);
Benchmark(100000);
Benchmark(1000000);
Console.ReadKey();
}
}
}
Вывод консоли
List(10).Sort(): 0,0025ms (100%)
List(10).OrderBy(): 0,0157ms (628,00%)
List(100).Sort(): 0,0068ms (100%)
List(100).OrderBy(): 0,0294ms (432,35%)
List(1000).Sort(): 0,0758ms (100%)
List(1000).OrderBy(): 0,3107ms (409,89%)
List(10000).Sort(): 0,8969ms (100%)
List(10000).OrderBy(): 4,0751ms (454,35%)
List(100000).Sort(): 10,8541ms (100%)
List(100000).OrderBy(): 50,3497ms (463,88%)
List(1000000).Sort(): 124,1001ms (100%)
List(1000000).OrderBy(): 705,0707ms (568,15%)
Что и требовалось доказать, использование метода Sort дает нам выигрыш в производительности, в среднем, более чем в 4 раза.
Заключение
Мы рассмотрели использование использование методов Sort и OrderBy для сортировки списков. Узнали как выполнить обратную сортировку, сортировку объектов произвольных типов. Так же мы выяснили, что выигрыш в производительности в 4-5 раз достигает при использовании метода Sort, вместо OrderBy.
Не стоит бояться использования метода OrderBy, это очень удобный инструмент для сортировки произвольных объектов в произвольных коллекциях. Если ваша коллекция не служит для хранения огромного количества элементов, то разницы в скорости между Sort и OrderBy вы не заметите, но сэкономите время на разработке приложения.
Дополнительные материалы
Узнайте больше об использовании списков List на примерах.
Изучите другие коллекции .NET, помимо списков.
Прочитали статью и у вас остались вопросы?
Задайте их в группе .NET сообщество разработчиков в ВКонтатке.
В течение короткого времени вы получите бесплатный ответ от специалистов.