Сортировка массивов с элементами m типов
Приведенные выше алгоритмы сортировки описаны в предположении, что методу сортировки заранее известны и тип сортируемых элементов, и их возможные значения. Давайте рассмотрим, как может выглядеть метод сортировки, позволяющий сортировать элементы произвольных типов, возможные значения которых заранее неизвестны, но передаются методу сортировки в момент вызова в качестве одного из аргументов. Начну с рассмотрения частного случая, когда в массиве элементы двух видов. Главная цель примера не столько в том, чтобы продемонстрировать сам алгоритм - он достаточно прост, а в том, чтобы показать, как на C# написать универсальный алгоритм для элементов любого типа и с разными названиями видов. Хочется, чтобы алгоритм можно было использовать для классификации элементов 0 и 1, "мужчин" и "женщин", "красных" и "белых".
Добавим в класс SortService универсальный метод сортировки массивов с двумя видами элементов. Вот текст этого метода сортировки:
///
/// Сортировать массив,
/// Предусловие: Элементы массива принадлежат двум видам,
/// заданным в массиве Spacimen
///
///
сортируемый массив
///
массив представителей
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.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, алгоритм становится эквивалентным по сложности классическим алгоритмам сортировки.
Сортировка черпаками
Если в процессе сортировки нужно хранить не только ключи, но и связанную с ними информацию, например, указатели на объекты, то нельзя обойтись подсчетом числа элементов одного вида, поскольку для каждого из элементов нужно сохранять связанную с ним информацию. В этом случае для каждого вида элементов нужно иметь свой "черпак" - массив, хранящий элементы данного вида. Алгоритм сортировки, как и в вышеописанном случае, состоит из двух этапов. На первом - заполняются черпаки, на втором - данные из черпаков сливаются в общий массив.
До сих пор разбиение элементов массива на виды осуществлялось с помощью представителей - к одному виду относились элементы с одним и тем же значением. Общий способ классификации состоит в задании классифицирующей функции - int Classification(int m, T item), которая для каждого элемента item возвращает число, задающее его вид. Аргумент m этой функции указывает максимальное число видов для этой функции классификации. Обычно предполагается, что значение, возвращаемое функцией, является целым числом в диапазоне [0, m-1], задавая номер вида. Примером такой функции классификации (оракула) является сортировочная шляпа из задачи Гарри Поттера, которая умеет по некоторым признакам ученика определить, к какому классу он должен принадлежать.
Задачи
65. Создайте Windows-проект для задачи "Красные и белые".
66. Создайте Windows-проект для задачи Э. Дейкстры.
67. Создайте Windows-проект для задачи "Сортировочная шляпа".
68. Создайте Windows-проект для сортировки за линейное время массивов типа string, элементы которого могут принимать одно из трех значений, заданных в массиве представителей.
69. Создайте Windows-проект для сортировки за линейное время массивов типа string, элементы которого могут принадлежать одному из трех видов. Вид элемента определяется функцией классификации, передаваемой методу сортировки в качестве параметра.
70. Создайте Windows-проект для сортировки за линейное время массивов типа string, элементы которого могут принимать одно из четырех значений, заданных в массиве представителей.
71. Создайте Windows-проект для сортировки за линейное время массивов типа string, элементы которого могут принадлежать одному из четырех видов. Вид элемента определяется функцией классификации, передаваемой методу сортировки в качестве параметра.
72. Создайте Windows-проект для сортировки за линейное время массивов типа string, элементы которого могут принимать одно из m значений, заданных в массиве представителей.
73. Создайте Windows-проект для сортировки за линейное время массивов типа string, элементы которого могут принадлежать одному из m видов. Вид элемента определяется функцией классификации, передаваемой методу сортировки в качестве параметра.
74. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortTwoKinds - процедуру сортировки массива типа T, содержащего элементы двух видов. Алгоритм должен выполняться за время порядка O(n), где n - число элементов массива. Виды элементов задаются массивом представителей. Создайте Windows-проект, поддерживающий работу с этой DLL.
75. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortTwoKinds - процедуру сортировки массива типа T, содержащего элементы двух видов. Алгоритм должен выполняться за время порядка O(n), где n - число элементов массива. Деление элементов на два вида задается соответствующей функцией классификации, передаваемой процедуре сортировки в качестве параметра. Создайте Windows-проект, поддерживающий работу с этой DLL.
76. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortThreeKinds - процедуру сортировки массива типа T, содержащего элементы трех видов. Алгоритм должен выполняться за время порядка O(n), где n - число элементов массива. Виды элементов задаются массивом представителей. Создайте Windows-проект, поддерживающий работу с этой DLL.
77. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortThreeKinds - процедуру сортировки массива типа T, содержащего элементы трех видов. Алгоритм должен выполняться за время порядка O(n), где n - число элементов массива. Деление элементов на два вида задается соответствующей функцией классификации, передаваемой процедуре сортировки в качестве параметра. Создайте Windows-проект, поддерживающий работу с этой DLL.
78. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortFourKinds - процедуру сортировки массива типа T, содержащего элементы четырех видов. Алгоритм должен выполняться за время порядка O(n), где n - число элементов массива. Виды элементов задаются массивом представителей. Создайте Windows-проект, поддерживающий работу с этой DLL.
79. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortFourKinds - процедуру сортировки массива типа T, содержащего элементы четырех видов. Алгоритм должен выполняться за время порядка O(n), где n - число элементов массива. Деление элементов на два вида задается соответствующей функцией классификации, передаваемой процедуре сортировки в качестве параметра. Создайте Windows-проект, поддерживающий работу с этой DLL.
80. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortMKinds - процедуру сортировки массива типа T, содержащего элементы m видов. Виды элементов задаются массивом представителей. Создайте Windows-проект, поддерживающий работу с этой DLL.
81. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortMKinds - процедуру сортировки массива типа T, содержащего элементы m видов. Деление элементов на два вида задается соответствующей функцией классификации, передаваемой процедуре сортировки в качестве параметра. Создайте Windows-проект, поддерживающий работу с этой DLL.
Проекты
82. На основе рассмотренного в этом разделе класса SortService постройте собственный класс, включающий различные методы сортировки для разных значений числа видов m. Постройте Windows-интерфейс, позволяющий клиентам класса вызывать его методы для массивов разных типов.
83. Постройте проект, позволяющий сравнивать время, затрачиваемое компьютером на сортировку массива, когда применяются методы универсального класса SortService и аналогичные методы, написанные для конкретного типа данных. Цель проекта - анализ возможных потерь эффективности, как плата за универсальный характер методов сортировки.
84. Постройте проект, позволяющий сравнивать время, затрачиваемое компьютером на сортировку массива с элементами двух, трех, четырех и m видов, при использовании методов класса SortService и метода быстрой сортировки Хоара, встроенной в библиотеку FCL.
|
