| « Структуры данных и алгоритмы. Теория. Рекуррентные уравнения. Динамическое программирование. | Структуры данных и алгоритмы. Практика. Сортировки и поиск элемента массива » |
Структуры данных и алгоритмы. Практическая работа. Простейшие алгоритмы сортировки: сортировка методом прямого обмена, прямой выборкой и вставкой
1) Необходимо создать реализацию функции, выполняющую сортировку массива символов (char) с помощью алгоритма сортировки прямой выборкой и вставкой. Проверить правильность работы алгоритма на примере строки текста вводимой пользователем с клавиатуры.
2) На основании ранее созданной функции сортировки создать ее реализацию в виде шаблонной функции, таким образом, мы сможем сортировать любые типы данных, для которых определены операции сравнения и копирования. Проверить правильность созданной шаблонной функции, выполнив сортировку массива целых чисел. Количество элементов 50, сами значения элементов должны генерироваться случайным образом в отрезке от 100 до 200.
3) Необходимо провести сравнительный анализ скорости работы не параметризированной и параметризированной версии функций для сортировки. Сортировке должны подлежать массивы символов (char). Значения данных массивов – это символы в интервале A-Z. Значения элементов должны генерироваться случайным образом. Результаты вывода работы программы должны быть в виде таблицы, например, так:
| Количество элементов | время, для не параметризированной версии | время, для параметризированной версии |
| 10 | 0 | 0 |
| 100 | 0 | 0 |
| 1000 | .. | .. |
| 10 000 | .. | .. |
| 100 000 | .. | .. |
| 1 000 000 (правда время будет настолько велико, что …, пожалуй, остановитесь на 10^5) | .. | .. |
5) В программе создать массив из 5 элементов “Chuman” и выполнить их сортировку с помощью параметризированной версии функции. Необходимо вывести на экран элементы данного массива до сортировки и после сортировки. С этой целью Вам необходимо в состав класса “Chuman” ввести метод “printMe”, который и будет выводить информацию о человеке на экран в виде:
“Chuman (fio=Vasyan Vasya; age=20; weight=87)”.При выполнении сортировки необходимо добиться упорядочения массива записей по полю ФИО, записи о людях должны быть расположены так, чтобы их фамилии были расположены в алфавитном порядке.
6) Продумать способ, как можно выполнять сортировку массива записей о людях по различным критериям. Пока на первый раз, для затравки, я предлагаю вам в качестве простейшего способа создать в составе класса “Chuman” статическое поле, например “m_mode”, типа:
enum TT_SortType {
by_FIO,
by_AGE,
by_WEIGHT
};
setSortType(TT_SortType)
Замечание: приведенная схема имеет ряд недостатков, поэтому если у Вас возникли идеи, почему и в чем недостаток схемы и возможные способы ее усовершенствования, то сообщайте мне (хорошие идеи будут вознаграждаться).
7) (Как часть данного задания было ваше д/з) Необходимо выполнить сортировку массива целых чисел (массив имеет размерность порядка 10^4 элементов, заполненных случайным образом) с помощью усовершенствованного алгоритма прямого обмена (оптимизация внешнего цикла, оптимизация внутреннего цикла до последней точки где был выполнен обмен). После того как была выполнена сортировка программа должна выполнить поиск случайного числа с помощью метода половинного деления. Накопите статистику о скорости работы алгоритма (оценка должна идти не в секундах или миллисекундах а в количестве операций деления) и проверьте насколько близки полученные результаты к эталонным log2n.
8) Создайте функцию, выполняющую сортировку массива целых чисел с помощью метода двоичной вставки. Определите для массива из 10^4 элементов количество операций сравнения и количество операций перемещения элементов между собой. Проверьте, как изменилось количество операций по сравнению с реализованном в первом задании алгоритме сортировки прямой вставкой.
| « Структуры данных и алгоритмы. Теория. Рекуррентные уравнения. Динамическое программирование. | Структуры данных и алгоритмы. Практика. Сортировки и поиск элемента массива » |