Структуры данных и алгоритмы. Практика. Простейшие алгоритмы сортировок (сортировка методом пузырька, вставки, выборки). Часть 2
Замечание: предполагается, что вы приступаете к выполнению данного задания только после того, как сделали предыдущую первую практическую работу.1) Одним из недостатков метода сортировки пузырьком является то, что «тяжелые» элементы поднимаются быстро по направленю движения внутреннего цикла, а вот против движения - спуск легких идет очень медленно (одно перемещение за один внутренний цикл). Необходимо самостоятельно создать программную реализацию алгоритма сортировки методом шейкера. В этом алгоритме необходимо чередовать направления движения внутреннего цикла.
2) Как вы знаете, существует возможность сортировки произвольных типов данных, если конечно для них определено понятие упорядоченности по некоторому критерию. В предыдущей работе вы создали класс “Chuman” (человек) и выполняли его сортировку по критерию сравнения ФИО человека. В случае применения классического C, использование шаблонов и перегруженных операторов сравнения не возможно. Поэтому применяют следующий пример:
void psevdoShablonSort (void * arr , int countElements , int SizeOfOneElement);
Для того, чтобы выполнять сравнение элементов, необходим критерий упорядочения. Поэтому используется понятие функционалов, и функция, выполняющая сравнение, передается в качестве еще одного параметра функции сортировки.
typedef int (*UserDefinedCompareFunction)(const void * elt_a , const void * elt_b);
void psevdoShablonSort (void * arr , int countElements , int SizeOfOneElement,
UserDefinedCompareFunction cmp)
void *memcpy( void *dest, const void *src, size_t count );
3) Проведите оценку скорости работы реализованной в предыдущем задании функции и шаблонной версии этой же функции. Оценку проводить на массиве целых чисел, размер массива вводится пользователем и не превышает 10^9 элементов. Сами же значения должны генерироваться случайным образом в отрезке от -1000 до 1000.
4) При анализе алгоритмов сортировки вводят понятие беспорядка. Под беспорядком понимаю количественную меру рассчитываемую по правилу: это количество таких пар элементов которые расположены не в правильном порядке. Когда говорим пара подразумевается не обязательно соседние элементы, а вообще любые пары.
Для массива: <strong>15 , 23 , 11 , 40 , 34 , 29</strong> Примеры пар увеличивающих беспорядок: <strong>(15, 11), (23, 11), (40, 34), (40, 29), (34, 29)</strong>.Итак, задание: для заданного массива, размером не более 20 элементов, (элементы вводятся пользователем) необходимо найти такие элементы, которые:
4.1) Вносят в массив наибольший беспорядок; 4.2) Вносят в массив наименьший беспорядок.5) Для массива записей “Chuman” выполнить сортировку методом прямого выбора (выборки). Для уменьшения затрат на перестановку элементов использовать прием с индексами элементов массива. Каждому элементу массива данных поставить в соответствие специальный элемент массива порядковых номеров. Таким образом при выполнении перестановки можно перемещать не сами элементы, а их индексы.
6) Оценить скорость работы созданного в задании # 5 алгоритма сортировки с оригинальной (алгоритм сортировки методом прямого выбора с перестановкой самих элементов) где индексы не используются. Объем массива > 10 000, заполнение случайным образом.
Домашнее задание
В текстовом файле хранится информация об школьниках в формате:
ФИО Возраст ПолНеобходимо прочитать данные из файла и упорядочить их по паре критериев: вначале должна идти сортировка по классу (вычисляется на базе возраста), а затем необходимо выполнить сортировку по ФИО в алфавитном порядке. После чтения, данные должны быть помещены в массив структур “CStudent”. После сортировки вывести данный массив структур на экран.