Sortowanie za pomocą czarnej skrzynki

Załóżmy, że chcemy posortować listę z liczb rzeczywistych. Załóżmy, że otrzymujemy czarną skrzynkę, która może natychmiast posortować liczb rzeczywistych. Ile korzyści możemy zyskać dzięki tej czarnej skrzynce?$S$$n$$\sqrt n$

Na przykład, czy możemy posortować numery za pomocą tylko wywołań do czarnej skrzynki? Najlepszy algorytm, jaki znalazłem, wykorzystuje wywołań do czarnej skrzynki. Ale nie byłem w stanie go jeszcze poprawić. Oto mój algorytm podobny do sortowania według scalenia:$O(\sqrt n)$$n$

Najpierw podziel listę na listy o wielkości w przybliżeniu . Następnie użyj wywołań do czarnej skrzynki, aby posortować te listy. Na koniec połącz posortowane listy za pomocą czarnej skrzynki w następujący sposób:$S$ s$\sqrt n$$s_1, s_2, ..., s_{\sqrt n}$$\sqrt n$$\sqrt n$

Umieść najmniejsze elementy list na nowej liście , a następnie wywołaj czarną skrzynkę, aby ją posortować. Liczba w (pierwszy i najmniejszy element ) będzie najmniejsza liczba w . Możemy umieścić go na pierwszym miejscu listy wyników. Zakładając, że element jest wybrany z , zastąpić z drugiej najmniejszej element listy rodzaj i ponownie uruchomić czarna skrzynka na to, aby obliczyć drugą najmniejszą członka . Kontynuujemy, aż wszystkie elementy zostaną posortowane. Całkowita liczba wywołań czarnej skrzynki dla tej części będzie wynosićL [ 1 ] L S s j L [ 1 ] s j S n - $L$$L[1]$$L$$S$
$s_j$$L[1]$$s_j$$S$
$n - \sqrt n$. Dlatego ogólnie łączna liczba połączeń wyniesie .$n$

Z drugiej strony wygląda na to, że powinniśmy być w stanie uzyskać dolną granicę za pomocą dolnej granicy na porównaniach liczb potrzebnych do sortowania w następujący sposób: Możemy zaimplementować czarną skrzynkę za pomocą porównań. Jeśli możemy rozwiązać problem z wywołaniami do czarnej skrzynki i scaleniem w czasie liniowym, możemy posortować liczb rzeczywistych z porównaniami co jest niemożliwe.o($\sqrt n \lg \sqrt n = \frac{1}{2} \sqrt n \lg n$no(nlgn$o(\sqrt n)$$n$$o(n \lg n)$

Wydaje mi się, że moglibyśmy udowodnić, że jest dolną granicą liczby wywołań do czarnej skrzynki, ponieważ wiele porównań używanych w czarnej skrzynce byłoby współdzielonych i dlatego są one uwzględnione w naszym argumencie.$\Omega(n)$

AKTUALIZACJA: Jak sugerują inne posty, możliwe jest także .$\sqrt n \lg n$

Możliwe jest sortowanie za pomocą wywołań do czarnej skrzynki i bez porównań.$O(\sqrt n\log n)$

Najpierw rozważmy następujący problem zrównoważonego partycjonowania: biorąc pod uwagę elementów (gdzie ), je na dwie grupy, najmniejszy rozmiar co najmniej około , więc że wszystkie elementy w pierwszej grupie są mniejsze niż wszystkie elementy w drugiej grupie. Można to zrobić za pomocą wywołań do czarnej skrzynki. (Opiszę to później.) Następnie użyj szybkiego sortowania z tym algorytmem partycjonowania:A [ 1 .. m ] $m$$A[1..m]$m/4O(m/$\sqrt n \le m \le n$$m/4$$O(m/\sqrt 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.

Zakładając, że każdy krok partycji zabiera wywołania do czarnej skrzynki, powyższy algorytm, podany na wejściu , wykona wywołania do czarnej skrzynki, ponieważ drzewo rekurencji ma głębokość a każdy poziom drzewa ma w sumie wywołań do czarnej skrzynki.A[1 ..n]O($O(m/\sqrt n)$$A[1..n]$O(logn)O(n/$O(\sqrt n\log n)$$O(\log n)$$O(n/\sqrt n) = O(\sqrt n)$

Wykonaj krok partycjonowania w następujący sposób:

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.)

Myślę, że twoje pytanie zostało rozwiązane w artykule Beigela i Gilla „ Sortowanie n obiektów za pomocą k-sortera ” z 1990 roku, a streszczenie artykułu mówi wszystko:

K-sorter to urządzenie, które sortuje k obiektów w jednostce czasu. Złożoność algorytmu korzystającego z k-sortera jest zdefiniowana jako liczba aplikacji k-sortera. W tej mierze złożoność sortowania n obiektów jest zawarta między oraz4nlog$\frac{n \log n}{k \log k}$ , do warunków pierwszego rzędu in i k.$\frac{4n \log n}{k \log k}$

$O(\sqrt{n}\log n)$$n$

$k$$\sqrt{n}$$2(n/k)^2$$k$$2n/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=18$$k=4$$k$

$k/2$$k$

$O((n/k)^2)$$O((n/k)\log^2(n/k)) = O(\sqrt{n}\log^2 n)$$O((n/k)\log (n/k)) = O(\sqrt{n}\log n)$