Я хочу проверить временную сложность quickSort, но я не знаю, как генерировать массивы для тестирования в лучшем случае. В моей версии quickSort в качестве точки поворота используется последний элемент массива.
Как я могу создать массивы для тестирования Best Case of quickSort?
comment
Вы пробовали, чтобы все элементы были одинаковыми? Для большинства накатанных мною собственных реализаций это наихудший случай
- person Jeffrey schedule 27.10.2019
comment
В лучшем случае массив уже должен быть отсортирован (по умолчанию в порядке возрастания). Итак, сгенерируйте тестовый пример так, чтобы i-й элемент массива был строго больше, чем (i-1)-й элемент.
- person kiner_shah schedule 28.10.2019
comment
Уже отсортированы не в худшем случае для quickSort? Я понял, что в лучшем случае стержень будет в среднем положении после разбиения... но я не могу понять, как сгенерировать такой массив.
- person Loop24 schedule 28.10.2019
Ответы (1)
Предполагая, что все элементы массива различны, вы, очевидно, получите наихудший случай, если всегда будете выбирать либо самый маленький, либо самый большой элемент. Это даст вам худшую глубину рекурсии и максимальное количество сравнений.
Но в худшем случае вам также понадобится много обменов. Проверьте, сколько элементов ваша реализация быстрой сортировки перемещает, когда последний элемент является самым маленьким или самым большим элементом в массиве. Решите, что хуже. Затем расположите числа в вашем массиве так, чтобы последний элемент в каждом подмассиве всегда был наихудшим.
person
gnasher729
schedule
27.10.2019
