5. Сортировка черпаками

Если в процессе сортировки нужно хранить не только ключи, но и связанную с ними информацию, например, указатели на объекты, то нельзя обойтись подсчетом числа элементов одного вида, поскольку для каждого из элементов нужно сохранять связанную с ним информацию. В этом случае для каждого вида элементов нужно иметь свой "черпак" - массив, хранящий элементы данного вида. Алгоритм сортировки, как и в вышеописанном случае, состоит из двух этапов. На первом - заполняются черпаки, на втором - данные из черпаков сливаются в общий массив.

До сих пор разбиение элементов массива на виды осуществлялось с помощью представителей - к одному виду относились элементы с одним и тем же значением. Общий способ классификации состоит в задании классифицирующей функции - int Classification(int m, T item), которая для каждого элемента item возвращает число, задающее его вид. Аргумент m этой функции указывает максимальное число видов для этой функции классификации. Обычно предполагается, что значение, возвращаемое функцией, является целым числом в диапазоне [0, m-1], задавая номер вида. Примером такой функции классификации (оракула) является сортировочная шляпа из задачи Гарри Поттера, которая умеет по некоторым признакам ученика определить, к какому классу он должен принадлежать.

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.