Сценарии для сортировки выбором, сортировки вставками и быстрой сортировки

Вот мои комментарии к вашим комментариям:

Какой метод работает быстрее для массива со всеми одинаковыми ключами, сортировки выбором или сортировкой вставки?

Я думаю, что это будет похоже на случай, когда массив уже отсортирован, так что сортировка вставками будет линейной, а сортировка выбором — квадратичной.

Да, это правильно. Сортировка вставками будет выполнять O(1) работы для каждого элемента и посещать O(n) элементов при общем времени выполнения O(n). Сортировка выбором всегда выполняется за время Θ(n²) независимо от входной структуры, поэтому ее время выполнения будет квадратичным.

Какой метод работает быстрее для массива в обратном порядке, сортировки выбором или сортировкой вставками?

Я думаю, что они будут работать одинаково, так как значения в каждой позиции должны быть изменены. Наихудший сценарий для сортировки вставками — обратный порядок, так что это будет означать, что она квадратична, и тогда сортировка выбором уже будет квадратичной.

Вы правы, что оба алгоритма имеют квадратичное время выполнения. На самом деле алгоритмы должны иметь относительно сопоставимую производительность, поскольку они будут выполнять одинаковое общее количество сравнений.

Предположим, что мы используем сортировку вставками для случайно упорядоченного массива, элементы которого имеют только одно из трех значений. Является ли время выполнения линейным, квадратичным или чем-то средним?

Поскольку он отсортирован случайным образом, я думаю, это будет означать, что сортировка вставками должна будет выполнять во много раз больше операций, чем количество значений. Если это так, то это нелинейно. Таким образом, оно, вероятно, будет квадратичным или, возможно, немного ниже квадратичного.

Это должно занять квадратичное время (время Θ(n²)). Возьмите только элементы в задней трети массива. Примерно треть этих элементов будет равна 1, и чтобы вставить их в отсортированную последовательность, их нужно будет переместить выше 2/3 пути вниз по массиву. Следовательно, проделанная работа будет как минимум (n / 3)(2n / 3) = 2n² / 9, что является квадратичным.

Какое максимальное количество раз во время выполнения Quick.sort() самый большой элемент можно обменять на массив длины N?

Максимальное число не может быть передано больше раз, чем есть свободных мест, так как оно всегда должно приближаться к своей правильной позиции. Таким образом, переходя от первого к последнему ценностному споту, он будет обмениваться N раз.

Здесь ошибка одиночная. Когда массив имеет размер 1, самый большой элемент больше нельзя перемещать, поэтому максимальное количество перемещений будет равно N - 1.

Сколько сравнений сделает quick.sort() при сортировке массива из N одинаковых элементов?

При рисовании быстрой сортировки вокруг сравниваемых объектов на каждой фазе можно нарисовать треугольник, то есть N в высоту и N в ширину, площадь этого будет равна количеству выполненных сравнений, которое будет (N ^ 2)/2

Это действительно зависит от реализации Quick.sort(). Быстрая сортировка с троичным разделением выполнит всего O(n) работы, потому что все значения, равные опорной точке, исключаются из рекурсивных вызовов. Если этого не сделать, то ваш анализ будет правильным.

Надеюсь это поможет!