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

Question

Должен ли сортировщик сравнения сравнивать самые большие значения A [i] и самые большие A [i + 1]? Я думаю, что любое сравнение должно, но я не уверен. Я проверил сортировку слиянием, сортировку вставкой и быструю сортировку, и в каждом из них необходимо сравнить самые большие значения A [i] и самые большие A [i + 1].

Answer 1

Каждый правильный алгоритм должен сравнивать соседние ячейки, если они не равны. Доказательство: предположим иначе. A [i] и A [i + 1] в конечном массиве не сравнивались (A [i]

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

Answer 5

из-за моего английского, извините .. я не влиятельный в английском.

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

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

Answer 6

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

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

Answer 7

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

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

Answer 8

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