Сортировка со средним сравнением

Существует ли алгоритм сортировки, основанный на сравнении, который использует среднее из сравнений ?$\mathrm{lg}(n!)+o(n)$

Существование алгоритма сравнения в худшем случае является открытой проблемой, но среднего случая достаточно для рандомизированного алгоритма с ожидаемыми сравнениями l g ( n ! ) + O ( n ) для каждого входа , Значение l g ( n ! ) + O ( n ) состоит в том, что это o ( n ) сравнений с оптимальными, тратя в среднем только $\mathrm{lg}(n!)+o(n)$$\mathrm{lg}(n!)+o(n)$$\mathrm{lg}(n!)+o(n)$$o(n)$ сравнения на элемент.$o(1)$

Так как у меня уже есть такой алгоритм, я включаю его в качестве ответа (используя формат Q / A ), но я приветствую дополнительные ответы, включая другие алгоритмы, был ли такой алгоритм уже известен, улучшая , и худший - case l g ( n ! ) + o ( n ) .$o(n)$$\mathrm{lg}(n!)+o(n)$

Предыдущая работа:
сортировка слиянием использует сравнения (даже в худшем случае). Сортировка с вставкой слиянием (также известная как сортировка Форда-Джонсона) также использует сравнения l g ( n ! ) + Θ ( n ), но с гораздо меньшей константой в Θ ( n ) . Улучшенная средняя сложность для сортировки на основе сравнения (от Kazuo Iwama и Junichi Teruyama) - их (1,2) алгоритм вставки напоминает часть моего ответа ниже.$\mathrm{lg}(n!)+ Θ(n)$
$\mathrm{lg}(n!)+ Θ(n)$$Θ(n)$

Обновление: я расширил этот ответ в статье Сортировка со средним сравнением $\mathrm{lg}(n!)+o(n)$ .

Да, такой алгоритм существует. Я докажу только границу , но при вероятном предположении рандомизации мы также получим l g ( n ! ) + O ( n 1 - ε ) . Я также опишу попытку для n 0,5 + o ( 1 ) и O ( n 0,5 - ε ) .$\mathrm{lg}(n!)+o(n)$$\mathrm{lg}(n!)+O(n^{1-ε})$$n^{0.5+o(1)}$$O(n^{0.5-ε})$

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

Отправной точкой является сортировка вставкой с двоичного поиска , чтобы решить , куда вставить следующий элемент в отсортированный подмножество . Когда ( 1 - ε ) 2 m ≤ | S | ≤ 2 m - 1 , вставка использует не более m сравнений, которые (с точки зрения энтропии) оптимальны с точностью до O ( ε ) аддитивного коэффициента (и для сложности в среднем случае 2 m ≤ | S | ≤ ( 1 +) ε ) 2 $S$$(1-ε)2^m ≤ |S| ≤ 2^m-1$$m$$O(ε)$$2^m ≤ |S| ≤ (1+ε) 2^m$тоже работает). Теперь, когда не близко к степени 2, вставка элемента A является неоптимальной (даже в среднем случае и независимо от того, как мы уравновешиваем каждый запрос), но если тратить o ( 1 ) сравнений, мы можем направить A к приблизительно равномерному распределению на отрезке длины S, близком к степени 2, мы получаем желаемую оптимальность.$|S|$$A$$o(1)$$A$$S$

Мы достигаем этого, добавляя элементы в пакетах, а иногда эффективно сравнивая элементы пакета друг с другом, так что интервал соответствующий элементу A, уменьшается квазислучайным образом (и с распределением вероятности A внутри интервала почти равномерные), и , когда длина интервала достаточно близко к власти 2, делая бинарный поиск для вставки A .$S$$A$$A$$A$

Общие конструкции

Мы будем хранить подмножество отсортированных элементов, и для каждого несортированного элемента A мы будем отслеживать минимальный интервал I A в S, где известно, что A находится. | Я А | длина I A ; I A = I B является тождеством интервалов.$S$$A$$I_A$$S$$A$$|I_A|$$I_A$$I_A=I_B$

Пусть будет: сравнивать A с B , а затем (в случайном порядке) сравнивать A и B с соответствующими элементами S, пока их интервалы не пересекаются (или имеют длину 1). Элемент S выбирается (в согласованном порядке) , чтобы сделать вероятности для сравнения как можно ближе к 1/2 , насколько это возможно, при условии , что , когда С о т р г е называется, ( , Б $\mathrm{Compare}(A,B)$$A$$B$$A$$B$$S$$S$$\mathrm{Compare}$$(A,B)$равномерно распределена на . Из-за дизъюнктности в конце концов, С о т р г е сохраняет однородность предположение.$I_A⨯I_B$$\mathrm{Compare}$

Следующие разделы могут быть прочитаны независимо друг от друга.

алгоритм$\mathrm{lg}(n!)+o(n)$

Дано: отсортированный список и пакет из m несортированных элементов; m ∈ ω ( 1 ) ∩ o ( | S | ) ; неотсортированные элементы являются случайными по отношению к S .$S$$m$$m∈ω(1)∩o(|S|)$$S$

Повторите (1) - (3), пока это возможно:
1. Выберите два элемента и B из партии с I A = I B (любой выбор будет работать). 2. Запуск С о т р г е ( , Б ) . 3. Если | Я А | достаточно близко к степени 2, ^{(примечание 1)} удалите A из партии (не забывая I A ); и сделать так же с B . Наконец: вставьте все элементы в$A$$B$$I_A=I_B$
$\mathrm{Compare}(A,B)$
$|I_A|$$A$$I_A$$B$
и завершить сортировку.$S$

Примечание 1: для «достаточно близко» любая относительная ошибка (как функция m ) работает до тех пор, пока элементы m - o ( m ) будут удалены на шаге (4) (возможно, примечанием 2). При предположительном предположении рандомизации, используя c log log m / log m, относительная ошибка фиксирует m ( 1 - log - Θ ( c ) m ) элементов, позволяя a l g ( n ! $o(1)$$m$$m-o(m)$$c \log \log m / \log m$$m(1-\log^{-Θ(c)}m)$ алгоритм сортировки среднего сравнения.$\mathrm{lg}(n!)+O(n \log \log n / \log n)$

Примечание 2: Поскольку одна и та же последовательность сравнений приводит к одному и тому же ограничивающему интервалу, почти все элементы пройдут этап (1) раз (если не будут удалены на этапе 4). В начале, если A < B и мы выбираем A , мы сравниваем A с элементом S [ ≈ ( 1 - 1 / $Ω(\log m)$$A < B$$A$$A$, и каждое применение шага (3) кAимеетO(1)вероятность уменьшения| ЯА| в≈1/(1-1/$S[≈(1-1/\sqrt{2})|S|]$$A$$O(1)$$|I_A|$раз. Теперь для каждого отношенияa>1, которое не является рациональной степенью 2, имеем∀ε>0∀d>0∃m,n∈$≈1/(1-1/\sqrt{2})$$a>1$, и поэтому мы получаемоценкуo(n).$∀ε>0 ∀d>0 ∃m,n∈\mathbb{N} \,\, 1-ε < \frac{a^m}{d2^n} < 1+ε$$o(n)$

Вероятный алгоритм $\mathrm{lg}(n!)+O(n^{1-ε})$

По модулю предположения рандомизации мы можем достичь среднего сравнения следующим образом.$\mathrm{lg}(n!)+O(n^{1-ε})$

• Произвольно перемешайте элементы и отсортируйте первую половину в список , сохранив вторую половину как несортированную партию.$S$

• 
  $A∈\text{batch}$$G = \{ B∈\text{batch}: |P(A < B) - 0.5| < n^{-0.51ε} \}$$G$$A$$S$
  

  1. $B∈G$$Θ(1)$$\mathrm{Compare}(A,B)$$|I_A|$$n^{-ε}$$\mathrm{Compare}(A,B)$$|I_A|$$n^{-ε}$$A$$S$
     
  2. $B∈G$$\mathrm{Compare}(A,B)$$B∈G$

$A$$n^{Θ(1)}$$n^{Θ(1)}$$Θ(\log n)$$ε$$\mathrm{lg}(n!)+O(n^{1-ε})$$A$$B$

$\mathrm{Compare}(A,B)$$ε≈(1-ε)/4/\log_{4/3} 2 ≈ 0.09$

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

$\mathrm{lg}(n!)+n^{0.5+o(1)}$

$|S|=n$$n$$I_A$$|I_A|$$n^{1-o(1)}$$\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$$A < S[i]$$n^{0.5+o(1)}$
$\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$

$S$

$\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$$|I_A|/2^{\lfloor \mathrm{lg} |I_A| \rfloor}$$\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$

$\mathrm{Compare}(A,B)$$P(A < B)≈0.5$$I_A$$I_A$$\mathrm{Compare}$$k=ω(1)$$k=ω(1)$$k$$S$$O(\log_k n + \log k)$$k$$Θ(\log k)$$k$

$1/2+n^{-0.5}$$O(1/n)$$n^{o(1)}$$n^{0.5+o(1)}$

$\mathrm{lg}(n!)+O(n^{0.5-ε})$$|S|+n^{0.5+ε}$$≈n^{0.5+ε}$$≈n^{0.5+ε}$$n^{0.5-ε/2+o(1)}$$S$$n^ε$$I_A$$Θ(n^{ε/2})$$n^{1-o(1)}$$n^{ε/2-o(1)}$$\mathrm{lg}(n!)+O(n^{1-ε})$$O(n^{0.5-ε'})$$ε$

$\mathrm{lg}(n!)+o(n)$$1.5n+o(n)$$(2+ε)n-O(1)$