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:
7 85 52 70 22 95 95 23
Poprawną odpowiedzią jest wyjście:
1 2 52 85 70 22 95 95 23 3 4 52 85 22 70 95 95 23 1 4 22 52 70 85 95 95 23 5 6 22 52 70 85 95 95 23 5 7 22 52 70 85 23 95 95 1 7 22 23 52 70 85 95 95
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 :