Недавно я увидел быструю сортировку на Haskell. Всего 2 строчки. И решил попробовать написать аналогичную сортировку на C#. Получилось еще лучше — всего одна строчка, хоть и длинная и совсем не такая изящная. Подробности под катом.
Вот сама сортировка:
private static Func<int[], int[]> QSortArray =
arr => arr.Length.Equals(0)
? new int[] {}
: (QSortArray(Array.FindAll(arr, num => num.CompareTo(arr[0]) < 0))
.Concat(Array.FindAll(arr, num => num.CompareTo(arr[0]) == 0))
.Concat(QSortArray(Array.FindAll(arr, num => num.CompareTo(arr[0]) > 0)))).ToArray();
Выглядит сложновато, да, но при знании используемых тут методов разобраться вполне можно. Как работает Func<> проще всего посмотреть в MSDN, а остальное я поясню:
Тернарный оператор сравнивает длину массива с нулем. Если длина массива нулевая, то возвращает пустой массив. Если длина ненулевая, начинается самое интересное: сначала находятся все элементы из массива, меньшие первого, с помощью Array.FindAll и сортируются. Аналогично со всеми элементами, равными первому (этих, сортировать, разумеется, не нужно), большими первого. Затем все это «склеивается» с помощью Concat, который возвращает тип IEnumerable, поэтому в конце мы приводим все к массиву методом ToArray(). Подробнее об используемых методах можно посмотреть опять же, в MSDN.
private static Func<List<int>, List<int>> QSortList =
arr => arr.Count.Equals(0)
? new List<int>()
: (QSortList(arr.FindAll(num => num.CompareTo(arr[0]) < 0))
.Concat(arr.FindAll(num => num.CompareTo(arr[0]) == 0))
.Concat(QSortList(arr.FindAll(num => num.CompareTo(arr[0]) > 0)))).ToList();
private static Func<IEnumerable<int>, IEnumerable<int>> QSortEnumerable =
arr => arr.Count().Equals(0)
? new List<int>()
: (QSortEnumerable(arr.Where(num => num.CompareTo(arr.First()) < 0)).
Concat(arr.Where(num => num.CompareTo(arr.First()) == 0)).
Concat(QSortEnumerable(arr.Where(num => num.CompareTo(arr.First()) > 0))));
Сортировка, разумеется, значительно медленнее библиотечной — раз в 20 (тестировал на массиве из 5 миллионов чисел: моя сортировка 10 секунд, библиотечная — 0.5 секунды), так что практическую ценность вряд ли имеет. Другого ожидать от алгоритма в одну строку и не стоило, хотя она все равно намного быстрее практически любой квадратичной.
