Skocz do zawartości

[Java] Merge Sort


pamparampa

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.

Odnośnik do komentarza
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

Odnośnik do komentarza
Udostępnij na innych stronach

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

Jedynie 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ę poniżej.

Zaloguj się
  • Ostatnio przeglądający   0 użytkowników

    • Brak zarejestrowanych użytkowników przeglądających tę stronę.
×
×
  • Dodaj nową pozycję...