An (n) algorytm sortowania

Question

To jest zadanie domowe, więc chciałbym uniknąć pełnych odpowiedzi i dużo preferować wskazówki, jeśli to możliwe.

Biorąc pod uwagę tablicę losowych liczb całkowitych A [1 ... x], program powinien zwrócić pierwsze elementy tablicy y w rosnącej kolejności, gdzie 1 < = y < = sqrt (x). Zasadniczo, biorąc pod uwagę tablicę [5,9,2,8] i y = 2, program powinien powrócić [2,5].

Odpowiedź "sortuj pierwszy, zwróć pierwsze rzeczy" jest niedostępna, ponieważ najlepsze, co możemy zrobić, to n * czas logowania z łączeniem lub quicksort. Odpowiedź zatem musi polegać na tym, że zwracamy tylko co najwyżej sqrt (x), a jedyną inną odpowiedzią, jaką mam do tej pory, jest wyszukiwanie w pętli minimalnego elementu w tablicy, usunięcie minimum z tablica, stashing go w nowej tablicy, powiedzieć B, i powtarzając proces na teraz mniejszej wersji zmodyfikowanej od a o długości X-1, co daje nam czas działa tak:

x + (x-1) + (x-2) + ... + (x-y) 

to zlicza iteracji pętli for min-search i daje nam co najwyżej y lub sqrt (x) iteracji w najgorszym scenariuszu i jest co najwyżej x pozycji w tablicy. Mamy więc sqrt (x) * x, który jest lepszy niż O (n * logn), ale wciąż nie całkiem O (n): /.

Answer 1

Podpowiedź: Załóżmy, że miał O (n) algorytm czas, aby wybrać y ^th elementu ...

Answer 2

Właściwie sqrt (x) rośnie szybciej niż log (x), więc O (x * sqrt (x)) jest gorsze niż O (n * log (x)). Więc nie zrobiłeś (jeszcze) lepiej niż sortowania całej listy.

Istnieje kilka sposobów rozwiązania tego problemu. Dla jednego z nich spójrz na http://en.wikipedia.org/wiki/Sorting_algorithm#Summaries_of_popular_sorting_algorithms i spójrz na wszystkie popularne algorytmy sortowania. Który algorytm może dać Ci kilka pierwszych elementów najskuteczniej?

Answer 3

< gdzie 1 = y < = sqrt (x)

Uwaga co to wymaganie daje. Jeżeli Y ≤ √ x, to y log Y ≤ (√ x ln x)/2 ∈ O (x ^{i frac12;} ln x) ⊂ O (x).

Sortowanie przez filtr może wychodzić z okna, ale filtrowanie i sortowanie jest dopuszczalne.

Answer 4

Dla y, użyj pomysłów szybkiego sortowania, wybierając losową liczbę i podziel ją na dwie części. Część 1 (mniejsza) i część 2 (większa).
Jeśli długość Część1 < y, a następnie do strefy na część 2, w którym Y '= Y - len (Part1) Jeśli długość Part1> Y, a następnie do strefy na Part 1, w którym Y' = Y Jeśli długość Part 1 == y, a następnie posortuj Part1.

do partycjonowania, średnia powinna być niemal w czasie O (n) (Nie mogę zatwierdzić go teraz, ale jest bardzo szybki) (postaram się znaleźć jakiś materiał dla tej części) ..
sortowania y wymaga ylog (y) < sqrt (x) log (sqrt (x)) -> 1/2 * sqrt (x) * log (x) < 1/2 * sqrt (x) * sqrt (x) => 1/2 x.

Answer 5

Potrzebujesz tylko podpowiedzi, prawda?

Przeczytaj komentarz przez random_hacker bardzo ostrożnie na w przypadku, gdy przegapiłeś dużą wskazówkę, że on daje. Istnieje jeden algorytm sortowania tablicy, w którym mała, drobna zmiana spowoduje wygenerowanie algorytmu.

Ogólnie, jeśli y nie jest ograniczone do sqrt (x), otrzymujemy algorytm działający w O (x + y * log x), który jest O (x), jeśli y = O (x/log x), co oczywiście ma miejsce, gdy y < = sqrt (x).