Какой тип ввода отличается от сортировки сортировки?

Question

1. В каком тестовом примере вставка сортировки выполняется лучше, чем сортировка сортировки? Четко опишите тестовый пример.

2. Почему сортировка сортировки хуже, чем сортировка вставки в этом случае?

Я ответил на первый вопрос так:

О (п). Когда сортировке вставки присваивается список, он принимает текущий элемент и вставляет его в соответствующую позицию списка, настраивая список при каждом вставке. Это похоже на размещение карт в карточной игре.

И второй вопрос:

Поскольку выбор Сортировать всегда делает п (п-1)/2 сравнений, но в худшем случае это будет только когда-либо делать п-1 свопы.

Но я не уверен в своих ответах, советах?

Answer 1

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

Для случая, когда выбор сортировки превосходит вставку сортировки, нам нужно быть немного сложнее. Наихудший случай сортировки вставки - это когда массив ввода отсортирован в обратном порядке. В этом случае он составляет Θ (n) сравнения и Θ (n) свопы. Сравните это с сортировкой сортировки, которая всегда делает Θ (n) сравнениями и O (n) свопами. Если сравнения и свопы занимают примерно одинаковое количество времени, то выбор сортировки может быть быстрее, чем сортировка вставки, но вам нужно будет профилировать его, чтобы узнать. Действительно, это сводится к реализации. Хорошая реализация сортировки вставки может фактически испортить неудачную реализацию сортировки в этом случае.

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