Autor logicznego modelu komputera John von Neumann opracował rekurencyjny algorytm sortowania danych, stosujący metodę dziel i zwyciężaj, zwany sortowaniem przez scalanie.
Zdefiniuj rekurencyjną procedurę Sortuj, której zadaniem jest posortowanie fragmentu tablicy od komórki lewy do komórki prawy, o następującym działaniu:
Sortuj(lewy, prawy) 1. Jeżeli obszar jest jednokomórkowy, tj.lewy=prawy , to jest on posortowany i nic nie rób 2. W przeciwnym przypadku: a) Oblicz środek:sr:=(lewy+prawy) div 2 b) Posortuj część lewą: Sortuj(lewy, sr) c) Posortuj część prawą: Sortuj(sr+1, prawy) d) Scal oba ciagi: Scal(lewy, prawy)
Kluczową czynnością w tym algorytmie jest operacja scalenia, czyli połączenia, dwóch posortowanych
rosnąco (dokładniej: niemalejąco) ciągów w jeden posortowany rosnąco ciąg liczb. Ciągi te zapisane są w tablicy
w komórkach: pierwszy od lewy do sr, drugi od sr+1 do prawy.
Po wykonaniu procedury Scal w obszarze od komórki lewy do komórki prawy powinien
zostać zapisany rosnący ciąg wynikowy - do wykonania tego zadania używa się tablicy pomocniczej.
Napisz program, który wczyta liczbę n i ciąg n liczb całkowitych, posortuje rosnąco ten ciąg za pomocą procedury Sortuj.
Pierwszy wiersz wejścia zawiera liczbę całkowitą n z zakresu
Po każdym wywołaniu procedury Scal wypisz w jednym wierszu numery komórek wskazujące scalany obszar tablicy, czyli indeksy lewy i prawy oraz w wierszu następnym całą tablicę liczb ciągu (bez spacji na końcu linii).
UWAGA:
Komórki tablicy numerujemy od 1, podobnie jak wyrazy ciągu liczbowego.
Dla danych podanych na wejściu:
6 23 45 14 35 30 44
Poprawną odpowiedzią jest wyjście:
1 2 23 45 14 35 30 44 1 3 14 23 45 35 30 44 4 5 14 23 45 30 35 44 4 6 14 23 45 30 35 44 1 6 14 23 30 35 44 45
Jeśli chcesz zobaczyć inny przykład odśwież tę stronę klawiszem F5
Opcje zadania:
Biblioteki : iostream iomanip cmath Limit czasu : 0.1 s Limit pamięci : 32 MB Słowa niedozwolone :