Студент

Герасимов Фёдор

Задача

Быстрая сортировка произвольных массивов

Состояние

Завершено

Баллов

5

Назначено

30.09.2019, 09:10

Завершено

14.10.2019, 10:27

Реализовать алгоритм быстрой сортировки, работающий с массивами произвольного типа (развитие задачи сортировки массива целых чисел).

void my_qsort(const void *ptr,
              size_t count, size_t size,
              int (*cmp)(const void *, const void *));

где:

• ptr — указатель на начало массива,
• count — количество элементов в массиве,
• size — размер одного элемента,
• cmp — функция сравнения, которая возвращает число больше нуля, если первый аргумент больше второго, число меньше нуля, если первый меньше второго, и ноль, если аргументы равны.

Работу алгоритма протестировать с помощью assert. Особое внимание уделить краевым случаям: count=0, count=1, count четное, count нечетное, уже сортированный массив, массив из одинаковых чисел. Дополнительно реализовать тест генерации случайных массивов случайного размера, сортировкой и последующей проверкой.

Для реализации рандомизированной быстрой сортировки можно обратиться к задаче «Перетасовка».