takie zadanie jest: :
dana jest tablica n liczb, przy czym wiadomo z góry,
że co najwyżej sqrt(n) liczb jest większych niż n. Napisz algorytm sortujšcy tę tablicę
w czasie lepszym niz n lg n.
i ja sobie wymyslilem zeby podzielic ta glowna tablice na dwie;
a-liczby mniejsze od n
b- liczby wieksze od n
nastepnie posortowac i zlaczyc. co sadzicie?
no dokładnie. potem tablicę a posortuj przez zliczanie a tablicę b przez wstawianie i masz sumaryczną złożoność liniową.
a mozesz mi jeszcze uzasadnic czemu przez zliczanie do tab A i czemu przez wstawianie do tab B?
a przez zliczanie bo uniwersum kluczy ma wielkość n dzięki czemu sortowanie przez zliczanie używa o(n) pamięci i ma taki sam czas działania.
b przez wstawianie bo przez zliczanie się nie da (brak wiadomości nt możliwych wartości klucza które mogą być bardzo duże) więc zostają algorytmy typu quicksort, heapsort, insertionsort, etc. z których każdy na zbiorze miary o(sqrt(n)) osiąga czas nie wyższy niż o(n).