Соседние элементы в результатах быстрой сортировки: гарантирует ли алгоритм их прямое сравнение?
Гарантируется ли алгоритмом быстрой сортировки прямое сравнение соседних элементов выходного массива?
Другими словами: В ходе сортировки алгоритм быстрой сортировки выполняет (k-2)2^k+2 сравнения в лучшем случае и 2^(2k-1)-3*2^(k-1)+1 сравнения в наихудший сценарий, когда количество сортируемых элементов (N) выражается как N=2^k-1.
Это много сравнений, но можем ли мы быть уверены, что соседние элементы, появляющиеся в отсортированном порядке в выходном массиве «a[]», сравнивались напрямую хотя бы один раз в ходе работы алгоритма? Так:
cmp(a[1], a[2]); cmp(a[2], a[3]); cmp(a[3], a[4]); ... ; cmp(a[N-1], a[N]);
Например, сортировка вставкой или пузырьковая сортировка.
Я подозреваю, что некоторые утверждения по этому поводу будут основываться на уникальных значениях ключей или подразумевать их.
Связано с тем, что, я думаю, вы делаете: Какой алгоритм сортировки использует наименьшее количество сравнений?
Ответы 1
Да! Рассмотрим дерево, образованное различными операциями над разделами, со сводным элементом раздела, связанным с этим узлом. Узлы увеличиваются при последовательном обходе. Для любого заданного немаксимального узла узел, следующий сразу за ним в отсортированном порядке, является либо предком (указывая на то, что, когда этот узел был опорным, этот узел сравнивался с ним), либо потомком (указывая обратное).
Я не уверен, как бы вы воспользовались этой гарантией, но она есть.
В более общем смысле, этим свойством обладает любой алгоритм сортировки на основе сравнения. Рассмотрим два узла, которые оказываются последовательными в отсортированном порядке. В какой-то момент они должны были непосредственно сравниваться друг с другом, потому что никакая транзитивная цепочка сравнений не могла бы иначе доказать, что левое меньше правого.
Например, предположим, что отсортированный порядок содержит кусочки...foo, bar, baz, qux.... Вполне возможно, что foo и qux никогда не сравнивались друг с другом: вместо этого каждый из них мог быть сравнен с bar или baz, или каждый из них мог быть сравнен друг с другом, а затем bar и baz сравнивались друг с другом. Но вы знаете, что foo и bar сравнивались напрямую, потому что никакой другой процесс не мог установить, что порядок должен был быть именно таким, а не ...bar, foo, baz, qux.... В конце концов, нет другого элемента, который мог бы помочь.
Юи правы. Но есть крайний случай, когда сравнения транзитивны, когда несколько элементов равны. Не знаю, что будет потом...
@vals При трехсторонней сортировке вместо этого вы бы сказали, что все соседние классы эквивалентности были напрямую сравнены хотя бы один раз. Я мог видеть, как можно реализовать трехходовую быструю сортировку, чтобы иметь только это более слабое свойство, но «нормальный» способ сделать это также даст более сильное свойство.
@Sneftel: Я все еще анализирую твой ответ. Кроме того, что касается вашего вопроса: я бы использовал эту гарантию, чтобы избежать повторения одних и тех же сравнений после сортировки массива. В стандартной библиотеке языка C реализация qsort() использует определяемую пользователем функцию сравнения. Я хотел бы проделать дополнительную работу внутри этой функции и воспользоваться преимуществами уже выполненных сравнений, чтобы мне не приходилось повторять их после того, как алгоритм быстрой сортировки выполнит свою работу. В моем случае эти сравнения очень дороги, поскольку на каждое сравнение приходится в среднем 65536 байт!
@GeorgeRobinson Звучит хорошо, но имейте в виду, что даже если у вас не было этой гарантии, вы все равно можете использовать мемоизацию, чтобы избежать повторного расчета необходимых последовательных сравнений.
@derpirscher: По вашему мнению, какой алгоритм сортировки дает такую гарантию?