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$ $\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$ $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. $\sqrt n \lg \sqrt n = \frac{1}{2} \sqrt n \lg n$ $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$

ds.algorithms sorting decision-trees

— AmeerJ
źródło

Wygląda na to, że w twoim komentarzu jest literówka. Czy chciałeś powiedzieć: „żaden algorytm używający mniej niż wywołań do maszyny nie może posortować liczb rzeczywistych z mniej niż porównań ?” ps: należy również uważać na fakt, że dolna granica tylko algorytmów sortowania opartych na porównaniu.

\sqrt{N}

$\sqrt{N}$

N

$N$

N \lg N

$N\lg N$

N \lg N

$N\lg N$

— Kaveh

Myślę, że możemy nawet uzyskać za pomocą sieci sortującej AKS. Ich sieć może być traktowana jako utworzenie modelu, w którym czarna skrzynka może sortować bloki o rozmiarze 2. Ich algorytmy używają rund , przy czym każda runda wywołuje 2-sorter razy. Jedną „rundę” 2-sorterów można łatwo zasymulować za pomocą -sorterów.

O (\sqrt{n} \log n)

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

O (\log n)

$O(\log n)$

O (n)

$O(n)$

O (n)

$O(n)$

O (\sqrt{n})

$O(\sqrt{n})$

\sqrt{n}

$\sqrt{n}$

— Vinayak Pathak,

@VayayakPathak: Podziel dane wejściowe na o rozmiarze , a następnie posortuj te części za pomocą sieci AKS, po zamianie każdego komparatora na -sorter.

2 \sqrt{N}

$2\sqrt{N}$

\sqrt{N} / 2

$\sqrt{N}/2$

\sqrt{N}

$\sqrt{N}$

— Jeffε 17.03.13

@ Jɛ ﬀ E: Tak, świetnie, to zdecydowanie wygląda na prostsze niż moja konstrukcja.

— Vinayak Pathak,

@ Jɛ ﬀ E, twoje komentarze mogą być odpowiedzią. :)

— Kaveh

Odpowiedzi:

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: $m$ $A[1..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. $O(m/\sqrt n)$ $A[1..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.)

— Neal Young
źródło

W ostatnim kroku algorytmu partition (): „Podziel wszystkie m elementów na X”, czy nie będzie to wymagało dodatkowych porównań?

— Vinayak Pathak,

Zobacz wiersz tuż za algorytmem, wyjaśnia, jak wykonać ten krok. Zedytuję to, aby to było jaśniejsze.

— Neal Young,

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 między oraz $\frac{n \log n}{k \log k}$ , do warunków pierwszego rzędu in i k. $\frac{4n \log n}{k \log k}$

— użytkownik 14004
źródło

Dziękuję Ci. Nie mogłem znaleźć papieru. Czy możesz podać link do dokumentu lub jego dowód?

— AmeerJ 17.03.13

link do artykułu

— Neal Young

Również na citeseerx .

— Kaveh

k = \sqrt{n}

$k=\sqrt{n}$

Θ (\sqrt{n})

$\Theta(\sqrt{n})$

$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$

wprowadź opis zdjęcia tutaj

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

— Jeffε
źródło

Ω (\sqrt{n} l g (n))

$\Omega(\sqrt n\ lg(n))$

O (\sqrt{n})

$O(\sqrt{n})$

+1 za ładne zdjęcie! Mogę się mylić, ale wydaje mi się, że nie jest to całkowicie poprawne (popraw mnie, jeśli się mylę). Zakładając, że dane wyjściowe są w porządku rosnącym, jeśli najmniejszy element znajduje się w ostatniej pozycji, nie ma „ścieżki” do „podróży” do pierwszej pozycji. Zmiana „dla i = 1 na m” na „dla i = 1 na m + 1” wydaje się to poprawiać, chociaż może to powodować pewne niepotrzebne koszty ogólne.

— George

@George Ups, masz rację; Potrzebuję jeszcze jednej warstwy!

— Jeffε