Должна ли сортировка сравнения сравнивать все соседние ячейки?

Быстрая сортировка и сортировка слиянием всегда сравнивают соседние элементы. Только когда два элемента не сравниваются, это когда алгоритм знает, что между ними есть элемент. Я думаю, что то же самое относится и к большинству других алгоритмов сортировки О (пlog п).

Я подозреваю, что нет. Рассмотрим группу значений, полностью состоящую из дубликатов одного значения. Они разделены на 2 группы A и B, так что ни одно значение в группе A не превышает любое значение в группе B. Затем они сортируются внутри себя. Конец значения A и начало B сравнивать не нужно.

Не знаю, есть ли этому практический пример, но подумать об этом интересно.

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

Для такого рода проблем (как и более общий подход сравнения-сортировки-n-log-n) будет эффективен (мини) аргумент "противник" - попробуйте сломать любой алгоритм, который на некоторых входных данных не работает. сделайте такое сравнение.

Идея очень похожа на более общее доказательство «сортировки для сравнения требуют O (n log n) сравнений», так что я полагаю, вы либо видели это недавно, либо собираетесь охватить это в своем классе.

Да, если нет хотя бы трех одинаковых элементов. Без этого невозможно гарантировать правильную сортировку. Единственный способ избежать сравнения всех пар - использовать транзитивный принцип.

A[i] > A[j] and A[j] > A[k] implies A[i] > A[k].

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

Каждый правильный алгоритм должен сравнивать соседние ячейки, если они не равны. Доказательство. Допустим противное. A [i] и A [i + 1] в окончательном массиве не сравнивались (A [i] <A [i + 1). Что произойдет, если их позиции поменять местами в исходном массиве? Все сравнения, выполненные алгоритмом, дают те же результаты, что и в исходном прогоне (*), поэтому он выполняет ту же перестановку, поэтому их конечные позиции меняются местами, что делает алгоритм некорректным.

(*) Это следует из того факта, что A [i] и A [j] смежны.

из-за моего английского, извините .. я не очень хорошо владею английским.

@see Анимированные алгоритмы сортировки: http://vision.bc.edu/~dmartin/teaching/sorting/anim-html/all.html

этот сайт показывает сравнение 8 алгоритмов сортировки: Вставка · Выбор · Пузырь · Оболочка · Слияние · Куча · Быстрый · Quick3

Сортировка оболочки не сравнивает соседние ячейки. Вот так они получают некоторую эффективность по сравнению с медленными сортировками (пузырь, вставка, выбор).