Zadanie i plik z danymi
https://cke.gov.pl/images/_EGZAMIN_MATURALNY_OD_2023/Informatory/Informator_EM2023_informatyka.pdf
Pseudokod poprawiony
"Przykładowo dla" A ← [4, 2, 1, 5, 3] n ← długość(A)
dla i = 2, 3, ..., n
v ← A[i]
j ← i
dopóki (j > 1) oraz (v < A[j - 1]) wykonuj
A[j] ← A[j - 1]
j ← j - 1
A[j] ← v
wypisz "A = " + A
Wyjaśnienia
Zadanie 4.1. (0–1)
W algorytmie Sortowanie przez wstawianie (SortW) operacja dominująca to przypisanie A[j] ← A[j - 1], które jest wykonywane wewnątrz pętli while. Minimalna i maksymalna liczba operacji dominujących będzie zależała od konkretnej sytuacji.
Minimalna liczba operacji dominujących:
Najmniejsza ilość operacji dominujących będzie miała miejsce, gdy tablica A jest już w pełni uporządkowana, tzn. gdy dla każdego i = 2, 3, ..., n, wartość A[i] jest większa lub równa A[i-1]. Wtedy w pętli while warunek (v < A[j - 1]) nigdy nie będzie spełniony, więc pętla nie zostanie wykonana dla żadnego i. Ostatecznie, minimalna liczba operacji dominujących wynosi 0.
Maksymalna liczba operacji dominujących:
Największa ilość operacji dominujących wystąpi, gdy tablica A jest odwrotnie posortowana, tzn. gdy dla każdego i = 2, 3, ..., n, wartość A[i] jest mniejsza od A[i-1]. Wtedy pętla while zostanie wykonana dla każdego i, przechodząc przez całą długość tablicy. W każdym przypadku, wewnątrz pętli, wykona się przypisanie A[j] ← A[j - 1]. Ostatecznie, maksymalna liczba operacji dominujących wynosi (n - 1) + (n - 2) + ... + 1 = (n * (n - 1)) / 2.
Zadanie 4.2. (0–1)
W najgorszym przypadku (gdy tablica jest odwrotnie posortowana), algorytm wykonuje około (n * (n - 1)) / 2 operacji dominujących, co jest złożonością kwadratową względem liczby elementów n w tablicy.
Zadanie 4.3. (0–2)
ifstream plik("dane4.txt");
ofstream wynik("zadanie4_3.txt");
const int n = 2023;
int x[n];
for (int i=0; i<n; i++)
plik >> x[i];
int liczba=0, maxi=0;
for(int i=1; i<n; i++){
int par=0;
for(int j=0; j<i; j++)
if (x[i] > x[j])
par++;
if (par >= liczba){
liczba=par;
maxi=i;
}
}
wynik<<maxi+1;