Задание № 3588

Студент

Роздин Иван

Задача

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

Состояние

Завершено

Баллов

5

Назначено

07.10.2021, 08:40

Завершено

18.11.2021, 09:06

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

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 нечетное, уже сортированный массив, массив из одинаковых чисел. Дополнительно реализовать тест генерации случайных массивов случайного размера, сортировкой и последующей проверкой.

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

Действия