# Informatyka — zadanie 2.2

> Źródło: matura.lol — https://matura.lol/question/maturazai-informatyka-inf-2018-05/zad/2.2
> Wersja Markdown strony zadania (dla asystentów AI). Przy cytowaniu podaj matura.lol i link powyżej.

- arkusz: Informatyka · Matura · maj 2018 (rozszerzona)
- rok: 2018
- poziom: rozszerzona
- typ: open
- punkty: 4
- działy: Programowanie i algorytmika, algorytmy

## Treść

Zadanie 2.2. (0-4)
Napisz algorytm (w pseudokodzie lub wybranym języku programowania), który przestawi
elementy tablic X i Y tak, aby szczyty były uporządkowane w kolejności, w której obserwator
widzi je od lewej do prawej strony. Aby otrzymać maksymalną ocenę, Twój algorytm powinien
mieć złożoność czasową kwadratową lub mniejszą.
Algorytm może używać wyłącznie instrukcji sterujących, operatorów arytmetycznych,
operatorów logicznych, porównań i przypisań do zmiennych. Zabronione jest używanie funkcji
bibliotecznych dostępnych w językach programowania.
Specyfikacja:
Dane:
n
- liczba całkowita dodatnia
X[1 n] - tablica liczb całkowitych
Y[1 n] - tablica liczb całkowitych dodatnich
Para (X[i], Y[i]) to współrzędne jednego szczytu, i = 1, 2, …, n.
Żadne dwa szczyty nie leżą w jednej linii z obserwatorem.
Wynik:
X[1 n], Y[1 n] - tablice zawierające współrzędne danych szczytów, uporządkowanych
w kolejności, w której obserwator widzi je od lewej do prawej strony.
Algorytm
MIN_1R

## Rozwiązanie — maturazai.pl (AI)

## Poprawna odpowiedź

**Algorytm - sortowanie bąbelkowe (bubble sort) wg ilorazu X[i]/Y[i]:**

powtarzaj n-1 razy:
dla i = 1, 2, , n-1 wykonuj:
jeżeli X[i+1]/Y[i+1] < X[i]/Y[i]:
t ← X[i]
X[i] ← X[i+1]
X[i+1] ← t
t ← Y[i]
Y[i] ← Y[i+1]
Y[i+1] ← t

## Sposób 1 - sortowanie bąbelkowe

**Idea:** w każdym przejściu "bąbel" (największy nieuporządkowany element) wędruje na koniec. Powtarzając n-1 razy, mamy gwarancję pełnego posortowania.

**Klucz porównania:** `X[i]/Y[i]` (kąt nachylenia od obserwatora).

**Zamiana par (X[i], Y[i]) ↔ (X[i+1], Y[i+1])** - zamieniamy OBIE tablice synchronicznie.

## Sposób 2 - implementacja Python

```python
def sortuj_szczyty(X, Y):
n = len(X)
for k in range(n - 1):
for i in range(n - 1 - k): # optymalizacja: ostatnie k jest posortowane
if X[i+1] / Y[i+1] < X[i] / Y[i]:
X[i], X[i+1] = X[i+1], X[i]
Y[i], Y[i+1] = Y[i+1], Y[i]
return X, Y

X = [3, -2, 2, 1]
Y = [4, 2, 1, 3]
print(sortuj_szczyty(X, Y))
# Posortowane: D(-2,2), A(1,3), B(3,4), C(2,1)
# X = [-2, 1, 3, 2], Y = [2, 3, 4, 1]

## Sposób 3 - sortowanie przez wybieranie (selection sort)

Alternatywa - w każdym przejściu wybieramy minimum z reszty i wymieniamy z pozycją k:

dla k = 1, 2, , n-1 wykonuj:
min_idx ← k
dla i = k+1, , n wykonuj:
jeżeli X[i]/Y[i] < X[min_idx]/Y[min_idx]:
min_idx ← i
zamień X[k] z X[min_idx]
zamień Y[k] z Y[min_idx]

**C++ (selection sort):**
```cpp
void sortuj(int X[], int Y[], int n) {
for (int k = 0; k < n - 1; k++) {
int min_idx = k;
for (int i = k + 1; i < n; i++) {
// X[i]/Y[i] < X[min_idx]/Y[min_idx]
if ((long long)X[i] * Y[min_idx] < (long long)X[min_idx] * Y[i]) {
min_idx = i;
}
}
if (min_idx != k) {
int tx = X[k]; X[k] = X[min_idx]; X[min_idx] = tx;
int ty = Y[k]; Y[k] = Y[min_idx]; Y[min_idx] = ty;
}
}
}

## Sposób 4 - sortowanie przez wstawianie (insertion sort)

dla k = 2, , n wykonuj:
i ← k
dopóki i > 1 oraz X[i]/Y[i] < X[i-1]/Y[i-1] wykonuj:
zamień X[i] z X[i-1]
zamień Y[i] z Y[i-1]
i ← i - 1

**Pascal:**
```pascal
procedure InsertionSort(var X, Y: array of LongInt; n: Integer);
var k, i, tx, ty: Integer;
begin
for k := 1 to n - 1 do begin
i := k;
while (i > 0) and (X[i] * Y[i-1] < X[i-1] * Y[i]) do begin
tx := X[i]; X[i] := X[i-1]; X[i-1] := tx;
ty := Y[i]; Y[i] := Y[i-1]; Y[i-1] := ty;
i := i - 1;
end;
end;
end;

## Reference informatyczny - sortowanie

> Reference - Sortowanie bąbelkowe (bubble sort):
> - Powtarza n-1 razy: porównuje sąsiadów i zamienia jeśli nieuporządkowani.
> - **Złożoność**: O(n²) najgorszy/średni, O(n) najlepszy (z flagą "swap").
> - **Pamięć**: O(1) dodatkowa (in-place).
> - **Stabilność**: stabilny (nie zamienia równych).
>
> Reference - Sortowanie przez wybieranie (selection sort):
> - W każdym przejściu wybiera minimum i zamienia z pozycją k.
> - **Złożoność**: O(n²) zawsze.
> - **Niestabilny** (zamiana minimum z pozycją k niszczy kolejność).
>
> Reference - Sortowanie przez wstawianie (insertion sort):
> - Bierze kolejny element i wstawia go w odpowiednie miejsce wśród posortowanych.
> - **Złożoność**: O(n²) najgorszy, O(n) najlepszy (dane już posortowane).
> - **Stabilny**, **in-place**, **adaptywny**.
>
> Reference - Sortowanie z funkcją porównawczą (klucz):
> - Zamiast `a[i] < a[j]` używamy `klucz(a[i]) < klucz(a[j])`.
> - Tu: `klucz(i) = X[i] / Y[i]`.
> - Synchronicznie zamieniamy WSZYSTKIE elementy powiązane z indeksem (tu X i Y).

## Schemat oceniania CKE

> Klucz CKE (zadanie 2.2, max 4 pkt):
> - **1 pkt** - poprawna konstrukcja zewnętrznej pętli sortowania
> - **1 pkt** - poprawna konstrukcja wewnętrznej pętli
> - **1 pkt** - poprawne porównanie elementów (iloraz X/Y)
> - **1 pkt** - poprawna zamiana elementów uwzględniająca **OBA** X i Y
>
> **Uwaga: za algorytm o złożoności WIĘKSZEJ niż kwadratowa - maksymalnie 3 pkt.**

## Typowe pułapki

- **Zamiana tylko X bez Y** - strata 1 pkt. Synchronizacja par jest KRYTYCZNA.
- **Zamiana tylko Y bez X** - j.w.
- **Sortowanie po samym X** zamiast X/Y - błędna kolejność (np. D(-2,2) zaszedłby przed A(1,3), ale gdyby było C(2,1) i A(1,3), to A miało większe X niż źle).
- **Złożoność O(n³)** - przy sortowaniu z dodatkową pętlą wewnątrz porównań. Strata 1 pkt.
- **Użycie funkcji bibliotecznej `sorted()` / `qsort`** - **zabronione przez treść**.
- **Off-by-one** w pętlach - pamiętaj o indeksowaniu od 1 w pseudokodzie.
- **Niepoprawne zamiana** - bez zmiennej tymczasowej `t` można nadpisać wartości.

## Złożoność obliczeniowa

- **Czas**: O(n²) - dwie zagnieżdżone pętle do n.
- **Pamięć**: O(1) dodatkowa (in-place, tylko zmienna `t` lub `min_idx`).
- **Operacje porównania**: do n(n-1)/2.
- **Operacje zamiany**: do n(n-1)/2 w bubble; do n-1 w selection.

Dla maksymalnej oceny (4 pkt) wystarcza kwadratowa - to jest mile widziane przez klucz CKE.

## Linki

- [dane JSON](https://matura.lol/api/question/maturazai-informatyka-inf-2018-05/zad/2.2)
- [otwórz w wyszukiwarce](https://matura.lol/?problem=maturazai-informatyka-inf-2018-05%2Fzad%2F2.2)

## Podobne zadania

- [Zadanie 2.2](https://matura.lol/question/informatyka-2026-czerwiec-matura-rozszerzona/zad/2.2) — Zadanie 2.2. (0-4) W pseudokodzie lub w zadeklarowanym języku programowania zapisz algorytm, który oblicza największe takie k, dla którego tablica T jest k-podo
- [Zadanie 2.2](https://matura.lol/question/informatyka-2020-lipiec-matura-rozszerzona/zad/2.2) — Zadanie 2.2. (0-4) Napisz w wybranej przez siebie notacji (w postaci pseudokodu, listy kroków lub w wybranym języku programowania) algorytm, który dla danej dod
- [Zadanie 2.3](https://matura.lol/question/informatyka-2019-maj-matura-stara-podstawowa/zad/2.3) — Zadanie 2.3. (4 pkt) Zapisz w wybranej przez siebie notacji (pseudokod, lista kroków, wybrany język programowania, schemat blokowy) algorytm wypisujący takie dw
- [Zadanie 2.3](https://matura.lol/question/informatyka-2018-czerwiec-matura-rozszerzona/zad/2.3) — Zadanie 2.3. (0-2) Aby przyśpieszyć rekurencyjne obliczanie wartości n-tego wyrazu ciągu Fibonacciego, można skorzystać z następujących wzorów, prawdziwych dla 

_Ostatnia aktualizacja danych: 2026-10-03_