Сортировка массивов с элементами m типов

Приведенные выше алгоритмы сортировки описаны в предположении, что методу сортировки заранее известны и тип сортируемых элементов, и их возможные значения. Давайте рассмотрим, как может выглядеть метод сортировки, позволяющий сортировать элементы произвольных типов, возможные значения которых заранее неизвестны, но передаются методу сортировки в момент вызова в качестве одного из аргументов. Начну с рассмотрения частного случая, когда в массиве элементы двух видов. Главная цель примера не столько в том, чтобы продемонстрировать сам алгоритм - он достаточно прост, а в том, чтобы показать, как на C# написать универсальный алгоритм для элементов любого типа и с разными названиями видов. Хочется, чтобы алгоритм можно было использовать для классификации элементов 0 и 1, "мужчин" и "женщин", "красных" и "белых".

Добавим в класс SortService универсальный метод сортировки массивов с двумя видами элементов. Вот текст этого метода сортировки:

/// <summary>/// Сортировать массив, /// Предусловие: Элементы массива принадлежат двум видам,/// заданным в массиве Spacimen/// </summary>/// <param name="ar">сортируемый массив</param>/// <param name="Spacimen">массив представителей</param>public static void SortTwoKinds(T[] ar, T[] Spacimen){ int start = 0, finish = ar.Length - 1; T val1 = Spacimen[0], val2 = Spacimen[1]; while (start < finish) { while ((start < finish) && (ar[start].CompareTo(val1) == 0)) start++; while ((start < finish) && (ar[finish].CompareTo(val2) == 0)) finish--; //обмен T temp = ar[start]; ar[start] = ar[finish]; ar[finish] = temp; start++; finish--; }}

Тот факт, что элементы сортируемого массива могут быть экземплярами произвольного класса T, обеспечивается тем, что класс SortService является универсальным классом с параметром T. Тот факт, что виды элементов могут иметь произвольные значения, обеспечивается тем, что методу сортировки передается массив Spacimen, хранящий представителей массива - возможные значения элементов массива.

Покажем теперь, как клиентский класс может вызывать метод сортировки в конкретной ситуации:

public void TestSortRedAndWhite() { //Два вида элементов int m = 2; string[] cand = new string[m]; cand[0] = "red"; cand[1] = "white"; //Моделирование массива ar Random rnd = new Random(); const int n = 10; string[] ar = new string[n]; for (int ind, i = 0; i < n; i++) { ind = rnd.Next(0, m); ar[i] = cand[ind]; } Console.WriteLine("Массив до сортировки!"); for (int i = 0; i < n; i++) Console.Write(ar[i] + " "); Console.WriteLine(); //Сортировка массива ar SortService<string>.SortTwoKinds(ar,cand); Console.WriteLine("Массив после сортировки!"); for (int i = 0; i < n; i++) Console.Write(ar[i] + " "); Console.WriteLine(); }

Рассмотренный алгоритм вряд ли целесообразно обобщать на случай, когда число видов более четырех. Тем не менее, можно построить эффективный алгоритм, когда число видов m известно и оно заведомо меньше n - числа элементов в массиве. В этом случае можно построить алгоритм сортировки, работающий за время . Идея алгоритма достаточно прозрачна. За один проход по сортируемому массиву посчитаем, сколько элементов каждого вида находится в массиве. Для хранения этой информации потребуется дополнительный массив Counts размерности m, элемент которого Counts[i] задает число элементов вида Spacimen[i] в сортируемом массиве. Используя этот массив и массив Spacimen, можно за время O(n) заполнить сортируемый массив элементами, следующими в нужном порядке. Основное время алгоритма уходит на формирование массива Counts, поскольку для каждого элемента нужно определить, какому виду он принадлежит, что требует проведения поиска в массиве Spacimen. Для поиска можно использовать метод SearchBarrier, на что уйдет время порядка O(m). Время можно сократить до , если использовать бинарный поиск, предварительно отсортировав массив Spacimen. Заметьте, на сортировку и хранение отсортированного массива понадобится дополнительное время порядка и дополнительная память. Когда число видов m сравнимо по порядку с числом элементов n, алгоритм становится эквивалентным по сложности классическим алгоритмам сортировки.