случайная сортировка слиянием

Question

Мне задали следующий вопрос в книге алгоритмов:

Предположим, что сортировка слиянием реализована для разделения файла в произвольной позиции, а не точно в середине.Сколько сравнений будет использовано таким способом для сортировки n элементов в среднем?

Спасибо.

Answer 1

Чтобы привести вас к ответу, рассмотрите следующие более конкретные вопросы:

Предположим, что разделение всегда составляет 10%, или 25%, или 75%, или 90%.В каждом случае: как это влияет на глубину рекурсии?Сколько сравнений должно быть на уровень рекурсии?

Answer 2

Вы можете получить верхнюю границу 2n * H_ {n - 1} <= 2n ln n, используя тот факт, что объединение двух списков общей длины n обходится не более чем в n сравнений.Анализ аналогичен анализу рандомизированной быстрой сортировки (см. <a href="http://www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0123.pdf" rel="nofollow">http://www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0123.pdf).

) Сначала предположим, что мы разбили список длины n на 2 списка L и R. Мы возьмем первый элемент R для сравнения со всемиэлементов L и последнего элемента L для сравнения со всеми элементами R. Даже если они не могут быть точными выполненными сравнениями, общее количество сравнений, за которые мы взимаем, равно n, как требуется.

Это обрабатывает один уровень рекурсии, а как насчет остальных? Мы продолжаем, концентрируясь только на «справа налево» сравнениях, которые происходят между первым элементом R и каждым элементом L на всех уровнях рекурсии(по симметрии это будет половина фактического ожидаемого итога.) Вероятность того, что j-й элемент сравнивается с i-м элементом, равна 1 / (j - i), где j> i. Чтобы увидеть это, обратите внимание, что элемент j сравнивается сэлемент i именно тогда, когда это первый элемент, выбранный в качестве «элемента разбиения» из множества {i + 1, ..., j}.то есть, элементы i и j разделяются на два списка, как только список, в котором они находятся, разделяется на некоторый элемент из {i + 1, ..., j}, и элемент j взимается за сравнение с i точно, когда элементj является элементом, выбранным из этого набора.

Таким образом, ожидаемое общее количество сравнений с участием j не более H_n (то есть 1 + 1/2 + 1/3 ..., где числослагаемых не более n - 1).Суммирование по всем возможным j дает n * H_ {n - 1}.Это учитывалось только для сравнения «справа налево», поэтому окончательная верхняя граница равна 2n * H_ {n - 1}.

Answer 3

Я частично согласен с @Armen, они должны быть сопоставимы.

Но: рассмотрим случай, когда они разбиты посередине. Чтобы объединить два списка длин n, нам понадобится 2*n - 1 сравнения (иногда меньше, но мы будем считать его фиксированным для простоты), каждый из которых выдает следующее значение. Было бы log2(n) уровней слияний, что дает нам приблизительно n*log2(n) сравнений.

Теперь рассмотрим случайное разбиение: максимальное число сравнений, необходимое для объединения списка длиной n1 с одним списком длины n2, составит n1 + n2 - 1. Тем не менее, среднее число будет близко к нему, потому что даже для самых несчастных сплитов 1 и n-1 нам понадобится в среднем n/2 сравнений. Таким образом, мы можем считать, что стоимость слияния за уровень будет такой же, как в четном случае.

Разница в том, что в случайном случае число уровней будет больше, и мы можем считать, что n для следующего уровня будет max(n1, n2) вместо n/2. Это max(n1, n2) будет иметь тенденцию быть 3*n/4, что дает нам приблизительную формулу

n*log43(n) // where log43 is log in base 4/3

что дает нам

n * log2(n) / log2(4/3) ~= 2.4 * n * log2(n)

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