W tym zadaniu zajmujemy się algorytmami działającymi na n-elementowej tablicy liczb całkowitych A[1..n], gdzie n jest dodatnią liczbą całkowitą.
Poniżej zapisano rekurencyjną procedurę W, której parametrem jest liczba całkowita j z przedziału [1, n].
Poniższe algorytmy S1 i S2 różnią się tylko kolejnością wywoływania procedury W.
Algorytm S1: dla i = 2, …, n wykonaj W( i )
Algorytm S2: dla i = n, n-1, …, 2 wykonaj W( i )
Dla każdego z algorytmów S1, S2 podanych w zadaniu 5.2. zdecyduj, czy jest on algorytmem sortującym. Odpowiedź uzasadnij.
cena_gazu.txt czestosc.txt dane1_3.txt dane1_4.txt dane2_3.txt dane2_4.txt dane3.txt dane4.txt dane6.txt dane6przyklad.txt dane8.txt gaz.txt pracownicy.txt rejestr_aktywnosci.txt szyfrogram.txt zamowienia.txt
Poniżej zapisano rekurencyjną procedurę W, której parametrem jest liczba całkowita j z przedziału [1, n].
procedura W( j ):
jeśli j > 1 to:
jeśli A[ j ] < A[ j – 1] to:
v ← A[ j ]
A[ j ] ← A[ j – 1]
A[ j – 1] ← v
W( j – 1)
Poniższe algorytmy S1 i S2 różnią się tylko kolejnością wywoływania procedury W.
Algorytm S1: dla i = 2, …, n wykonaj W( i )
Algorytm S2: dla i = n, n-1, …, 2 wykonaj W( i )
Dla każdego z algorytmów S1, S2 podanych w zadaniu 5.2. zdecyduj, czy jest on algorytmem sortującym. Odpowiedź uzasadnij.