Skocz do zawartości
pamparampa

[Java] Merge Sort

Rekomendowane odpowiedzi

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.

Udostępnij tego posta


Odnośnik do posta
Udostępnij na innych stronach

Masz je policzyć czy wypisać?

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

Udostępnij tego posta


Odnośnik do posta
Udostępnij na innych stronach

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ł

Udostępnij tego posta


Odnośnik do posta
Udostępnij na innych stronach

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

Udostępnij tego posta


Odnośnik do posta
Udostępnij na innych stronach

Jeśli chcesz dodać odpowiedź, zaloguj się lub zarejestruj nowe konto

Tylko zarejestrowani użytkownicy mogą komentować zawartość tej strony.

Zarejestruj nowe konto

Załóż nowe konto. To bardzo proste!

Zarejestruj się

Zaloguj się

Posiadasz już konto? Zaloguj się tutaj.

Zaloguj się tutaj

  • Przeglądający   0 użytkowników

    Brak zarejestrowanych użytkowników, przeglądających tę stronę.

×