Если в процессе сортировки нужно хранить не только ключи, но и связанную с ними информацию, например, указатели на объекты, то нельзя обойтись подсчетом числа элементов одного вида, поскольку для каждого из элементов нужно сохранять связанную с ним информацию. В этом случае для каждого вида элементов нужно иметь свой "черпак" - массив, хранящий элементы данного вида. Алгоритм сортировки, как и в вышеописанном случае, состоит из двух этапов. На первом - заполняются черпаки, на втором - данные из черпаков сливаются в общий массив.
До сих пор разбиение элементов массива на виды осуществлялось с помощью представителей - к одному виду относились элементы с одним и тем же значением. Общий способ классификации состоит в задании классифицирующей функции - 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<T> и аналогичные методы, написанные для конкретного типа данных. Цель проекта - анализ возможных потерь эффективности, как плата за универсальный характер методов сортировки.
84. Постройте проект, позволяющий сравнивать время, затрачиваемое компьютером на сортировку массива с элементами двух, трех, четырех и m видов, при использовании методов класса SortService и метода быстрой сортировки Хоара, встроенной в библиотеку FCL.
