Chcę napisać program w Javie, który sortuje tablicę przez scalanie iteracyjnie, oraz wykonuje scalanie dwóch podtablich posortowanych w miejscu, czyli bez dodatkowej tablicy. Mam problem z funkcją scalającą. Próbowałem już na wiele sposobów. Jak to zrobić.
Te sposoby są bardzo skomplikowane. Nie da się tego zrobić prościej?
OK. Algo jest rekurencyjni i ma złożoność O(n lg n) - samo merge'owanie. Stad cały mergesort będzie miał O(n lg n lg n).
Na wejściu jest ciąg który składa się z dwóch rosnących podciągów.
Pomysł polega na tym, że bierzemy środkowy element z dłuższego i znajdujemy go w krótszym. Potem robimy reverse'a na ciągu elementów pomiędzy tymi dwoma elementami. Wtedy powstaje ciąg który jest najpierw rosnący, później malejący, później rosnący i później malejący. Ciągu malejące odwracamy. Powstają cztery rosnące podciągi, z tym że dwa pierwsze ciągi mają wszystkie elementy mniejsze niż w ostatnich dwóch. Należy więc rekurencyjnie zrobić merge na dwóch parach podciągów: tych z przodu i tych z tyłu.
Rozmiar największego podproblemu to maksymalnie 75% rozmiaru wejścia (na danym poziomie rekurencji), więc poziomów rekurencji jest logarytmiczna ilość.
Przy zastosowaniu ostrożności da się zaimplementować algorytm tak by działał przy powtarzających się elementach.
Zarejestruj się i dołącz do największej społeczności programistów w Polsce.
Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.