[Java] Merge Sort

[pamparampa]

Witam. Potrzebuję napisać usprawnienie do algorytmu merge sort, który polega na wykrywaniu podciągów rosnących. Mam już sam algorytm sortowania, teraz zastanawiam się jak się zabrać za to usprawnienie. Mógłby ktoś opisać krok po kroku jak taki algorytm wykonać? Samo wykrywanie mniej więcej wiem jak zrobić, ale zastanawiam się głównie nad następującymi rzeczami:

- Kiedy mamy szukać podciągów rosnących? Tylko na samym początku, czy np. w każdym poziomie rekurencji?

- Czy lepiej szukać podciągów o jakiejkolwiek długości, czy o długości większej niż jakaś stała?

- Co dokładnie zrobić, kiedy już znajdę taki ciąg?

Proszę o pomoc. Pozdrawiam.

[Floodnik]

Masz je policzyć czy wypisać?

Czy może znaleźć najdłuższy?

[pamparampa]

mam znaleźć ciągi rosnące (nie wiem czy wszystkie, czy tylko te dłuższe) i wykorzystać to, że one są już uporządkowane, do tego, żeby algorytm merge sort szybciej działał

[Floodnik]

No to napotykamy problem: "co autor miał na myśli" :)

Pierwsze, co mi przychodzi do głowy, to przed wywołaniem rekurencyjnym sprawdzić, czy dany podciąg(lewa, prawa połówka) jest już posortowany, zwyczajnie przebiegając przez niego. Jeśli tak, nie robić wywołania.

Czy to rozwiązuje nasze zadanie?

Nie wiem. JAKIEŚ usprawnienie to jest - w przypadku niektórych ciągów(np. dla już posortowanego ciągu zrobisz tylko jedną pętlę, wyjdzie liniowy czas, normalny mergesort by standardowo jechał wszystkie wywołania). Więc teoretycznie zadanie zostało wykonane. Choć nie znajdujemy wszystkich podciągów rosnących... To by było imo bez sensu, mogłoby nawet zwiększyć złożoność.

 

PS. Pisząc poprzedni post nie zwróciłem uwagi na to, że to miało być usprawnienie MergeSorta, a nie dodatkowa funkcjonalność(dlatego łapałem się za głowę o co chodzi). Przepraszam :P