Сортировка по черному ящику

20

Предположим, что мы хотим отсортировать список из действительных чисел. Предположим, что нам дан черный ящик, который может мгновенно отсортировать реальных чисел. Какое преимущество мы можем получить, используя этот черный ящик?n Snn

Например, можем ли мы отсортировать номера только с помощью вызовов в черный ящик? Лучший алгоритм, который я нашел, использует вызовов черного ящика. Но я не смог улучшить его дальше. Вот мой алгоритм, который похож на сортировку слиянием:нO(n)n

Сначала разбейте список на списков примерно с размером. Затем используйте вызовов черного ящика для сортировки этих списков. Наконец, объедините отсортированные списки, используя черный ящик следующим образом:S ы1,ев2,. , , ,сns1,s2,...,snnn

Поместите наименьшие элементы списков в новый список , затем вызовите черный ящик, чтобы отсортировать его. Число в (первый и наименьший элемент ) будет наименьшим номером в . Мы можем поставить его на первое место в списке вывода. Если предположить , что элемент был выбран из , заменим с вторым наименьшим элементом списка сортировки , и снова запустить черный ящик на нем , чтобы вычислить второй наименьший элемент из . Мы продолжаем, пока все элементы не отсортированы. Общее количество вызовов черного ящика для этой части будетL [ 1 ] L S s j L [ 1 ] s j S n - LL[1]LS
sjL[1]sjS
nn, Поэтому общее количество звонков будет .n

С другой стороны, похоже, что мы должны быть в состоянии получить нижнюю границу, используя нижнюю границу для сравнения чисел, необходимых для сортировки, следующим образом: Мы можем реализовать черный ящик, используя сравнений. Если мы сможем решить эту проблему с помощью вызовов в черный ящик и слияния в линейное время, мы можем отсортировать действительных чисел с помощью сравнений, что невозможно.o(nlgn=12nlgnno(nlgn)o(n)no(nlgn)

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

ОБНОВЛЕНИЕ: Как и в других сообщениях, также достижимо.nlgn

AmeerJ
источник
2
Там, кажется, опечатка в вашем комментарии. Вы хотели сказать: «Ни один алгоритм, использующий менее вызовов к машине, не может отсортировать действительных чисел с сравнениями»? ps: вы также должны быть осторожны с тем фактом, что нижняя граница справедлива только для алгоритмов сортировки, основанных на сравнении. NNlgNNlgNNNNlgNNlgN
Каве
8
Я думаю, что мы можем даже получить используя сортировочную сеть AKS. Их сеть можно рассматривать как экземпляр вашей модели, где черный ящик может сортировать блоки размером 2. Их алгоритмы используют раундов, каждый раунд вызывает 2-сортировщика раз. Один «раунд» 2-сортировщиков можно легко смоделировать с помощью -сортировщиков. O(logn)O(n)O(n)O(O(nlogn)O(logn)O(n)O(n)O(n) n
Винаяк Патхак
6
@VinayakPathak: разбейте входные данные на фрагмента размером , а затем отсортируйте фрагменты, используя сеть AKS, после замены каждого компаратора на -сортировщик. 2NN/2N
Джефф
1
@ Jɛ ff E: Да, отлично, это определенно выглядит проще, чем моя конструкция.
Винаяк Патхак
1
@ Jɛ ff E, ваши комментарии могут быть ответом. :)
Kaveh

Ответы:

15

Можно сортировать с помощью звонки в черный ящик и никаких сравнений.O(nlogn)

Сначала рассмотрим следующую проблему сбалансированного разбиения: дано элементов A [ 1 .. m ] (где mA[1..m]), разделите их на две группы, наименьший размер которых должен составлять не менееm/4, чтобы все элементы в первой группе были меньше, чем все элементы во второй группе. Это можно сделать с помощьюO(m/nmnm/4звонки в черный ящик. (Я опишу это позже.) Затем используйте быструю сортировку с этим алгоритмом разделения:O(m/n)

def qsort(A[1..m]):
   if m < sqrt(n): sort A with one call to the black box
   else:
     Partition A[1..m] into two groups as described above.
     Recursively qsort the first group.
     Recursively qsort the second group.

Предполагая, что каждый шаг разбиения занимает вызовы черного ящика, приведенный выше алгоритм, учитывая входA[1 ..n], сделаетO(O(m/n)A[1..n]обращается к черному ящику, потому что дерево рекурсии имеет глубинуO(logn),и каждый уровень дерева имеет в общей сложностиO(n/O(nlogn)O(logn)звонки в черный ящик.O(n/n)=O(n)

Сделайте шаг разбиения следующим образом:

def partition(A[1..m]):  (where sqrt(n) <= m <= n)
   Divide A into m/sqrt(n) groups of size sqrt(n) each.
   Sort each group with one call to the black box per group.
   Sort the medians of the groups with one call to the black box.
   (Note the number of groups is less than sqrt(n), because m <= n.)
   Let X be the median of the medians.
   Partition all m elements around X, using the black box as follows:
      For each group G, let Y be its median:
        Call the black box once on (G - {Y}) union {X}.
        (This gives enough information to order all elts w.r.t. X.)
Нил Янг
источник
На последнем шаге алгоритма partition (): «Разделить все m элементов вокруг X», не будет ли это использовано m дополнительных сравнений?
Винаяк Патхак
2
Посмотрите на строку, следующую за алгоритмом, она объясняет, как сделать этот шаг. Я отредактирую это, чтобы сделать это более ясным.
Нил Янг
24

Я думаю, что ваш вопрос был рассмотрен в статье Бейгеля и Джилла " Сортировка n объектов с использованием k-sorter " от 1990 года, и реферат статьи говорит сам за себя:

nlognklogk4nlognklogk

user14004
источник
Спасибо. Я не мог найти газету. Можете ли вы предоставить ссылку на документ или его доказательство?
AmeerJ
Также на Citeseerx .
Каве
8
k=nΘ(n)
12

O(nlogn)n

kn2(n/k)2k2n/k

BlockBubbleSort(X[0..n-1], k):
   m = floor(n/k)
   for i = 1 to m
      for j = 0 to m-1
          BlackBoxSort(X[j*k .. (j+1)*k-1])
      for j = 0 to m-1
          BlackBoxSort(X[j*k + k/2 .. (j+1)*k + k/2 - 1])

n=18k=4k

введите описание изображения здесь

k/2k

O((n/k)2)O((n/k)log2(n/k))=O(nlog2n)O((n/k)log(n/k))=O(nlogn)

Jeffε
источник
Ω(n lg(n))
2
O(n)
+1 за эту красивую картинку! Я могу ошибаться, но мне кажется, что это не совсем правильно (поправьте меня, если я ошибаюсь). Предполагая, что выходные данные находятся в порядке возрастания, если наименьший элемент находится в последней позиции, для него нет «пути» для «перемещения» в первую позицию. Изменение «для i = 1 до m» на «для i = 1 до m + 1», кажется, исправляет это, хотя это может привести к некоторым ненужным издержкам.
Джордж
@ Джордж Ой, ты прав; Мне нужен еще один слой!
Джефф