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:
8 64 57 88 26 55 74 84 67
Poprawną odpowiedzią jest wyjście:
1 2 57 64 88 26 55 74 84 67 3 4 57 64 26 88 55 74 84 67 1 4 26 57 64 88 55 74 84 67 5 6 26 57 64 88 55 74 84 67 7 8 26 57 64 88 55 74 67 84 5 8 26 57 64 88 55 67 74 84 1 8 26 55 57 64 67 74 84 88
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 :