„Prawie sortujące” liczby całkowite w czasie liniowym

Interesuje mnie sortowanie tablicy dodatnich wartości liczb całkowitych w czasie liniowym (w modelu pamięci RAM z jednolitą miarą kosztów, tj. Liczby całkowite mogą mieć wielkość logarytmiczną, ale przyjmuje się, że operacje arytmetyczne na nich przyjmą czas jednostkowy). Oczywiście nie jest to możliwe w przypadku algorytmów sortowania opartych na porównaniu, więc jestem zainteresowany obliczeniem sortowania „przybliżonego”, tj. Obliczeniem pewnej permutacji z , która tak naprawdę nie jest klasyfikowane w ogóle, ale „dobrym przybliżeniem” z posortowanej wersji L . Zakładam, że sortujemy liczby całkowite w malejącej kolejności, ponieważ sprawia to, że kontynuacja jest nieco przyjemniejsza w stwierdzeniu, ale oczywiście można by sformułować problem na odwrót.$L = v_1, \ldots, v_n$$v_{\sigma(1)}, \ldots, v_{\sigma(n)}$$L$$L$

Jednym z możliwych kryteriów przybliżonego sortowania jest (*): pozwalając $N$ być $\sum_i v_i$ , dla każdego $1 \leq i \leq n$ , wymagamy, aby $v_{\sigma(i)} \leq N/i$ (tj. lista „quasi-posortowana” jest ograniczona od góry przez malejącą funkcję $i \mapsto N/i$ ). Łatwo zauważyć, że faktyczny sort spełnia to: $v_{\sigma(2)}$ może być większy niż $v_{\sigma(1)}$ więc jest co najwyżej $(v_{\sigma(1)} + v_{\sigma(2)})/2$ czyli $\leq N/2$ , i ogólnie $v_{\sigma(i)}$ może być większy niż $(\sum_{j \leq i} v_{\sigma(i)})/i$ który jest $\leq N/i$.

Na przykład wymaganie (*) można osiągnąć za pomocą poniższego algorytmu (sugerowanego przez @Louis). Moje pytanie brzmi: czy istnieją prace nad tym zadaniem „prawie sortowania” liczb całkowitych w czasie liniowym, poprzez nałożenie jakiegoś wymogu, takiego jak (*), który spełniłby prawdziwy sort? Czy poniższy algorytm lub jego wariant ma ustaloną nazwę?

Edycja: poprawiono algorytm i dodano więcej wyjaśnień

Algorytm:

INPUT: V an array of size n containing positive integers
OUTPUT: T

N = Σ_{i<n} V[i]
Create n buckets indexed by 1..n
For i in 1..n
| Add V[i] into the bucket min(floor(N/V[i]),n)
+

For bucket 1 to bucket n
| For each element in the bucket
| | Append element to T
| +
+

Ten algorytm działa zgodnie z przeznaczeniem z następujących powodów:

1. Jeśli element znajduje się w wiadrze wówczas . $v$$j$$v ≤ N/j$

   $v$ jest wstawiane do wiadra , a zatem j ≤ \ lfloor N / v \ rfloor ≤ N / v$j=\min(N/v,n)$$j ≤ \lfloor N/v\rfloor ≤ N/v$

2. Jeśli element znajduje się w wiadrze albo lub . $v$$j$$N/(j+1) < v$$j=n$

   $v$j = min ( N / v , n ) j = ⌊ N / v ⌋ j = n j = ⌊ N / v ⌋ j ≤ N / v < j + 1 N / ( j + 1 ) < v jest wstawiane do segmentu , a zatem lub . W pierwszym przypadku co oznacza a zatem .$j=\min(N/v,n)$$j = \lfloor N/v \rfloor$$j=n$$j=\lfloor N/v\rfloor$$j ≤ N/v < j+1$$N/(j+1) < v$

3. Dla istnieje najwyżej elementów w wiadrach od 1 do .$j<n$$j$$j$

   Niech i niech będzie całkowitą liczbą elementów w jednym z segmentów 1..j. Do 2. mamy, że każdy element w segmencie (z ) jest taki, że . Dlatego suma wszystkich elementów w segmentach od do jest większa niż . Ale ta suma jest również mniejsza niż zatem a zatem co daje nam lub .$j<n$$k$$v$$i$$i ≤ j$$N/(j+1)≤N/(i+1)<v$$K$$1$$j$$k×N/(J+1)$$K$$N$$k×N/(j+1) < K ≤ N$$k/(j+1) < 1$$k<j+1$$k≤j$

4. $T$ spełnia (*) tj. -ty element jest taki, że$j$$T$$T[j] ≤ N/j$

   Do 3. mamy, że , ty element , pochodzi z wiadra z dlatego .$T[j]$$j$$T$$i$$i ≥ j$$T[j] ≤ N/i ≤ N/j$

5. Algorytm ten zajmuje czas liniowy.

   Obliczenie zajmuje czas liniowy. Wiadra mogą być implementowane za pomocą połączonej listy, która ma wstawianie i iterację . Zagnieżdżona pętla działa tyle razy, ile jest elementów (tj. razy).$N$$O(1)$$n$

Brzmi to bardzo podobnie do algorytmu ASort. Zobacz ten artykuł autorstwa Giesen i in. glin.:

https://www.inf.ethz.ch/personal/smilos/asort3.pdf

Niestety czas działania nie jest dość liniowy. Powyższy artykuł dowodzi, że dowolny oparty na porównaniu algorytm losowy algorytm uszeregujący elementów w obrębie n 2 / ν ( n ) ma dolną granicę n ∗ l o g ( ν ( n ) ) (przy założeniu ν ( n ) < n ).$n$$n^2/\nu(n)$$n*log (\nu(n))$$\nu(n) < n$

EDYTUJ , w odpowiedzi na wyjaśnienia w pytaniu:

To, co robisz, to po prostu rodzaj wiadra . Jednak algorytm sortowania segmentowego nie jest w tym przypadku liniowy. Problem: musisz zsumować liczby naturalne, a następnie wykonać podział na każdym z nich. Ponieważ liczby są nieograniczone pod względem wielkości, nie jest już operacją o stałym czasie. Wykonanie większej liczby liczb będzie wymagało więcej czasu.$N/V[i]$

Jak długo jeszcze? Dzielenie zależy od liczby cyfr, więc jest to , razy n operacji dzielenia. To chyba brzmi znajomo. :)$lg(n)$$n$

Jak się okazuje, moje pytanie jest jednak zupełnie nieistotne. Rzeczywiście, pracuję na maszynie RAM z jednolitą miarą kosztów (tj. Mamy rejestry, których rejestry niekoniecznie muszą mieć stały rozmiar, ale mogą przechowywać na wejściu liczby całkowite o wielkości logarytmicznej, a operacje na tych rejestrach zajmują stały czas, w tym przynajmniej dodatek). W rzeczywistości w tym modelu sortowanie liczb całkowitych (przez zasadniczo wykonanie sortowania radix) może odbywać się w czasie liniowym. Wyjaśnia to w artykule z 1996 r. Grandjean, Sortowanie, czas liniowy i problem satysfakcji .

(To nie odpowiada na moje pytanie, czy istnieją dobrze zbadane pojęcia „prawie sortowania” zestawu liczb całkowitych, ale aby były interesujące, prawdopodobnie potrzebne byłyby te słabsze pojęcia, aby były łatwiejsze do wyegzekwowania, tj. Praca nad słabszym model lub w jakiś sposób uruchomić w czasie podliniowym. Jednak obecnie nie jestem świadomy sensu, w którym by tak było).