C++ · Etap 2 · Lekcja 12

Sortowanie — wszystko po kolei

Polecenie sort(v.begin(), v.end()) już znasz. Ta lekcja pokazuje, ile da się z nim zrobić: sortować rosnąco i malejąco liczby, napisy i pary, wyciągać z ułożonych danych medianę, k-ty element, powtórzenia i najbliższych sąsiadów, sortować według własnej reguły i kilku kryteriów naraz, sortować numery zamiast wartości i liczyć miejsca w rankingu, a na koniec błyskawicznie szukać w posortowanych danych (lower_bound) i rozwiązywać zadania „najpierw posortuj, potem bierz po kolei”. Po drodze zajrzysz pod maskę: sam napiszesz sortowanie przez wybieranie, bąbelkowe, przez wstawianie i przez zliczanie — każde z animacją krok po kroku. Po każdej części czekają ćwiczenia ze sprawdzarką.

69 ćwiczeń w trakcie lekcji28 zadań w bazie na koniec97 ze sprawdzarką C++
Filmy z OKI

Wolisz obejrzeć?

Olimpijskie Koło Informatyczne nagrywa swoje zajęcia i udostępnia je za darmo. Poniżej 6 odcinków o tym temacie — dobre uzupełnienie, jeśli wolisz obejrzeć niż przeczytać.

Materiały Olimpijskiego Koła Informatycznego — kanał zewnętrzny. Kliknięcie odtwarza film tutaj, bez opuszczania strony.

Co już umiesz i czego się nauczysz

Ta lekcja zakłada, że przerobiłeś wszystkie poprzednie: Typy zmiennych, Input / Output, If / Else, While loop, For loop, Modulo, Tablice, String, Pair i Vector. Najbardziej przydadzą się dwie ostatnie: z lekcji o vectorze — strzałki begin() i end() oraz zakres [od, do), a z lekcji o parach — porównywanie par i para (wartość, numer).

Po co osobna lekcja, skoro sort(v.begin(), v.end()) już znasz? Bo ta jedna linijka to dopiero początek. Wyobraź sobie listę 30 wyników ze sprawdzianu. Kto był trzeci? Jaki wynik jest środkowy? Czy dwie osoby mają tyle samo punktów? Które dwa wyniki są najbliżej siebie? Na nieułożonej liście każde z tych pytań wymaga osobnej pętli, a czasem pętli w pętli. Na ułożonej odpowiedź po prostu leży na właściwym miejscu. Dlatego sortowanie to najczęstszy pierwszy krok w rozwiązaniach zadań olimpijskich: najpierw ułóż, potem myśl.

Uczymy się tak samo jak poprzednio. Przepisuj przykłady do swojego edytora i uruchamiaj je. Przy pytaniach „Co wypisze program?” najpierw narysuj sobie vector na kartce — rząd pudełek z numerami pod spodem — i odpowiedz w głowie, a dopiero potem sprawdzaj. W części 4 możesz też oglądać algorytmy w animacjach, krok po kroku. Po każdej części rób ćwiczenia w sprawdzarce. Lekcja jest długa: rób przerwy i nie przechodź dalej, dopóki ćwiczenia z poprzedniej części nie przestaną sprawiać Ci kłopotu.

CZĘŚĆ 01–03

sort i co z niego wynika

Rosnąco i malejąco, liczby, napisy i litery, k-ty element i mediana, a potem równe obok siebie, unique i najbliżsi sąsiedzi.

CZĘŚĆ 04

Pod maską

Sortowanie przez wybieranie, bąbelkowe, przez wstawianie i przez zliczanie — sam je napiszesz i obejrzysz w animacjach.

CZĘŚĆ 05–07

Sortowanie po swojemu

Własna reguła porównania (lambda), kilka kryteriów naraz, stable_sort, sortowanie numerów i miejsca w rankingu.

CZĘŚĆ 08–09

Sortowanie w akcji

Szukanie przez połowienie, lower_bound i upper_bound, a na koniec pomysły zachłanne: posortuj i bierz po kolei.

Przypomnienie: złota zasada sprawdzarki Sprawdzarka porównuje Twoje wyjście z oczekiwanym znak po znaku, więc wypisujesz dokładnie to, o co prosi zadanie — bez „Podaj liczby:” i bez dodatkowych słów. Spacje na końcu wiersza są ignorowane, więc wypisywanie vectora pętlą z cout << x << " " jest w porządku. Uważaj natomiast na spacje w środku wiersza i na to, czy każdy element ma być w osobnym wierszu, czy wszystkie w jednym.

Mapa lekcji

sort — wszystko po kolei jedną linijką

Zaczynamy spokojnie, od tego, co już trochę znasz. W tej części dokładnie zobaczysz, co znaczy „posortować”, jak sortować vector, zwykłą tablicę i napis, w jakiej kolejności ustawiają się słowa (to potrafi zaskoczyć!), jak posortować tylko kawałek i jak sprawdzić, czy coś już jest posortowane.

Co to znaczy „posortować”?

Posortować to ustawić elementy po kolei: od najmniejszego do największego. Robisz to codziennie, nawet o tym nie myśląc — gdy ustawiasz się w szeregu według wzrostu, gdy układasz karty w ręce albo gdy szukasz swojego nazwiska na liście, która jest ułożona alfabetycznie. Komputer robi to samo, tylko z liczbami, literami i napisami.

Te same pięć liczb, tylko ustawione po kolei. Nic nie znika i nic nie dochodzi — zmienia się wyłącznie kolejność.

A co, jeśli niektóre liczby się powtarzają? Wtedy równe liczby stają obok siebie: z liczb 5, 2, 8, 2, 5 robi się 2, 2, 5, 5, 8. Taki ciąg nie jest ściśle rosnący (2 i 2 są równe), więc matematycy mówią na niego niemalejący — każdy następny element jest większy albo równy poprzedniemu. W treściach zadań zwykle pisze się po prostu „posortuj rosnąco”, a chodzi właśnie o to: równe obok siebie, w dowolnej kolejności między sobą.

Niemalejąco: dwójki obok siebie (niebieskie), piątki obok siebie (pomarańczowe). Każdy element jest większy albo równy poprzedniemu.
Rosnąco, niemalejąco, malejąco Rosnąco: 1 3 5 7 (każdy większy od poprzedniego). Niemalejąco: 1 3 3 7 (większy albo równy). Malejąco: 7 5 3 1. Nierosnąco: 7 3 3 1. Gdy zadanie mówi „rosnąco”, a w danych mogą być powtórzenia — chodzi o niemalejąco. sort robi dokładnie to.

sort na vectorze — pierwszy pełny program

Polecenie sort dostaje dwie strzałki z lekcji o vectorze: v.begin() — strzałkę na pierwszy element, i v.end() — strzałkę za ostatnim. Sortuje wszystko od pierwszej strzałki (wliczamy) do drugiej (nie wliczamy), czyli cały vector. Mieszka w bibliotece <algorithm>, ale <bits/stdc++.h> ma ją w środku, więc nic nie dopisujesz.

pierwszy_sort.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (auto &x : v) cin >> x;      // 1. wczytaj

    sort(v.begin(), v.end());        // 2. posortuj

    for (auto x : v) cout << x << " ";   // 3. wypisz
    cout << "\n";
    return 0;
}
▶ Wejście
6 7 -3 9 1 5 1
▶ Wyjście
-3 1 1 5 7 9

Każdy program z sortowaniem ma te same trzy kroki: wczytaj, posortuj, wypisz (albo policz coś na posortowanych danych).

Zwróć uwagę: sort nie wypisuje niczego i nie tworzy nowego vectora. Przestawia elementy w środku tego samego vectora v. Po tej linijce v jest po prostu ułożony.

Liczby ujemne nie są problemem: −3 jest mniejsze od 1, więc stoi na początku. Dwie jedynki stanęły obok siebie.

sort na zwykłej tablicy: t i t + n

Zwykła tablica nie ma begin() ani end(), ale ma coś równie dobrego: sama nazwa tablicy t działa jak strzałka na element t[0], a t + n — jak strzałka na miejsce numer n, czyli tuż za ostatnim z n elementów. Dlatego piszesz sort(t, t + n) — dokładnie jak w lekcji o parach.

Tablica ma 5 elementów (numery 0–4). t pokazuje pudełko 0, a t + 5 — miejsce za ostatnim. sort(t, t + 5) sortuje wszystkie pięć.
tablica.cpp
int t[5] = {4, 8, 1, 9, 2};
sort(t, t + 5);
for (int i = 0; i < 5; i++) cout << t[i] << " ";
cout << "\n";

int u[6] = {0, 7, 3, 6, 5, 1};   // liczymy od 1: u[1]..u[5]
int n = 5;
sort(u + 1, u + n + 1);
for (int i = 1; i <= n; i++) cout << u[i] << " ";
cout << "\n";
▶ Wyjście
1 2 4 8 9 1 3 5 6 7

Drugi przykład to częsty zwyczaj na olimpiadzie: elementy trzyma się w pudełkach od 1 do n, a pudełko 0 zostaje puste. Wtedy sortujesz od u + 1 (pudełko 1) do u + n + 1 (miejsce za pudełkiem n).

Najważniejsza zasada jest ta sama co przy vectorze: druga strzałka pokazuje miejsce, którego już nie bierzemy.

t + n, a nie t + n - 1 Częsty błąd: sort(t, t + n - 1). Wygląda logicznie („ostatni element ma numer n − 1”), ale druga strzałka nie jest wliczana — więc ostatni element zostaje poza sortowaniem i stoi tam, gdzie stał. Program działa „prawie” dobrze, co jest najgorszym rodzajem błędu. Zapamiętaj: sort(t, t + n) dla pudełek 0..n−1 i sort(t + 1, t + n + 1) dla pudełek 1..n.

Słowa po kolei: porządek słownikowy

Vector napisów sortuje się tak samo: sort(s.begin(), s.end()). Słowa ustawią się w porządku słownikowym — tak jak w słowniku albo w dzienniku. Pamiętasz z lekcji o napisach, jak C++ porównuje dwa napisy? Idzie od lewej, litera po literze, i rozstrzyga na pierwszej różnicy. Gdy jedno słowo jest początkiem drugiego, krótsze stoi wcześniej. Zobacz, co z tego wynika:

slowa.cpp
vector<string> s = {"kotek", "ala", "kot", "Zosia", "ania", "10", "9"};
sort(s.begin(), s.end());
for (auto x : s) cout << x << "\n";
▶ Wyjście
10 9 Zosia ala ania kot kotek
parapierwsza różnicakto wcześniej
"ala" i "ania"'l' i 'n'ala — l jest przed n
"kot" i "kotek"kot się skończyłkot — krótszy, gdy jest początkiem
"Zosia" i "ala"'Z' (kod 90) i 'a' (kod 97)Zosia — wielkie litery są przed małymi
"10" i "9"'1' i '9'10 — bo znak '1' jest przed '9'

Dwie rzeczy zaskakują prawie każdego. Po pierwsze, wszystkie wielkie litery są przed wszystkimi małymi: „Zosia” stoi przed „ala”, bo komputer porównuje kody znaków, a kody wielkich liter (65–90) są mniejsze od kodów małych (97–122). Cyfry mają kody jeszcze mniejsze (48–57), więc stoją przed literami. Po drugie, liczby zapisane jako napisy sortują się jak słowa: „10” stoi przed „9”, bo porównujemy pierwsze znaki '1' i '9'. Liczba 10 jest większa od 9, ale napis „10” jest „mniejszy” od napisu „9”.

Liczby trzymaj w int, nie w string Jeśli chcesz sortować liczby według wartości, wczytuj je do int albo long long. Napis „100” stanie przed „20”, a „-5” przed „-10”, bo napisy porównują się znak po znaku, a nie według wartości.

Litery w napisie

Napis to w środku rząd znaków — prawie jak vector. Dlatego sort(s.begin(), s.end()) ustawia po kolei litery jednego napisu. Znaki porównują się po kodach, więc spacje (kod 32) idą na sam początek, potem cyfry, wielkie litery i na końcu małe.

litery.cpp
string s = "banan";
sort(s.begin(), s.end());
cout << s << "\n";

string t = "Ala ma kota";
sort(t.begin(), t.end());
cout << "[" << t << "]\n";
▶ Wyjście
aabnn [ Aaaaklmot]

W drugim przykładzie dwie spacje wylądowały na początku, potem wielkie A, potem cztery małe a i reszta liter po kolei. Nawiasy kwadratowe wypisaliśmy tylko po to, żeby spacje było widać.

Sortowanie liter ma piękne zastosowanie: anagramy. Dwa słowa są anagramami, gdy składają się z tych samych liter, tylko w innej kolejności — jak „kot” i „tok”. Po posortowaniu liter oba zamieniają się w to samo: „kot”. Wystarczy więc posortować litery obu słów i porównać wyniki przez ==.

anagramy.cpp
string a = "kajak", b = "jakak", c = "kajko";
string sa = a, sb = b, sc = c;      // kopie — oryginały zostają
sort(sa.begin(), sa.end());
sort(sb.begin(), sb.end());
sort(sc.begin(), sc.end());
cout << sa << " " << sb << " " << sc << "\n";
cout << a << " i " << b << ": " << (sa == sb) << "\n";
cout << a << " i " << c << ": " << (sa == sc) << "\n";
▶ Wyjście
aajkk aajkk ajkko kajak i jakak: 1 kajak i kajko: 0

Zwróć uwagę na kopie: sortujemy sa, a nie a. Gdybyśmy posortowali samo a, stracilibyśmy oryginalne słowo i nie dałoby się go już wypisać.

Tylko kawałek

Z lekcji o vectorze pamiętasz, że strzałki nie muszą obejmować całości. Kawałek od numeru a do numeru b włącznie sortujesz tak: sort(v.begin() + a, v.begin() + b + 1). To + 1 jest potrzebne, bo druga strzałka pokazuje pudełko, którego już nie bierzemy. Reszta vectora zostaje nietknięta.

kawalek.cpp
vector<int> v = {9, 7, 5, 3, 1, 8, 6};
int a = 1, b = 4;
sort(v.begin() + a, v.begin() + b + 1);   // numery 1..4
for (auto x : v) cout << x << " ";
cout << "\n";
sort(v.begin() + 4, v.end());             // od numeru 4 do końca
for (auto x : v) cout << x << " ";
cout << "\n";
▶ Wyjście
9 1 3 5 7 8 6 9 1 3 5 6 7 8
Niebieskie: posortowany kawałek 1..4. Pomarańczowe: drugie sortowanie, od numeru 4 do końca. Pudełko 0 (z dziewiątką) cały czas stoi na miejscu.

sort zmienia vector — czasem potrzebna kopia

Po sort pierwotna kolejność jest stracona — vector nie pamięta, jak wyglądał wcześniej. Czasem to nie szkodzi (gdy pytają tylko o ułożone liczby), ale czasem potrzebujesz obu wersji: na przykład, żeby porównać, które elementy stały już na swoich miejscach. Wtedy robisz kopię: vector<int> w = v; i sortujesz kopię.

kopia.cpp
vector<int> v = {3, 1, 2, 4, 5};
vector<int> w = v;              // kopia
sort(w.begin(), w.end());
int naMiejscu = 0;
for (int i = 0; i < (int)v.size(); i++) {
    if (v[i] == w[i]) naMiejscu++;
}
cout << naMiejscu << "\n";
▶ Wyjście
2
Zielone pudełka mają w v i w w tę samą liczbę — czwórka i piątka już stały na swoich miejscach.

Czy to już jest posortowane?

Ciąg jest posortowany niemalejąco wtedy, gdy każde dwa sąsiednie elementy stoją dobrze: v[i] <= v[i + 1]. Wystarczy więc przejść po sąsiadach i poszukać pary, w której lewy jest większy od prawego. Jeśli takiej pary nie ma — ciąg jest posortowany. To samo robi gotowe polecenie is_sorted(v.begin(), v.end()), które zwraca true albo false.

czy_posortowane.cpp
vector<int> v = {1, 3, 3, 8, 6, 9};
int zle = -1;                     // numer pierwszej złej pary
for (int i = 0; i + 1 < (int)v.size(); i++) {
    if (v[i] > v[i + 1]) {
        zle = i;
        break;
    }
}
if (zle == -1) cout << "posortowane\n";
else cout << "zle przy numerze " << zle << ": " << v[zle] << " > " << v[zle + 1] << "\n";
cout << is_sorted(v.begin(), v.end()) << "\n";
▶ Wyjście
zle przy numerze 3: 8 > 6 0

Warunek pętli to i + 1 < v.size(), bo porównujemy v[i] z v[i + 1] — ostatnie i musi mieć jeszcze sąsiada po prawej.

Uwaga na znak: posortowane niemalejąco to v[i] <= v[i + 1], więc „źle” to v[i] > v[i + 1]. Dwa równe elementy obok siebie są w porządku.

is_sorted wypisane przez cout daje 1 (tak) albo 0 (nie) — jak każdy bool.

Inne typy działają tak samo

sort potrafi ustawić po kolei wszystko, co da się porównać znakiem <: liczby long long i double, znaki char, napisy, a nawet pary — te porównują się najpierw po first, a przy remisie po second, jak w lekcji o parach. Wrócimy do nich w części 6.

inne_typy.cpp
vector<double> d = {3.5, -1.25, 2, 0.5};
sort(d.begin(), d.end());
for (auto x : d) cout << x << " ";
cout << "\n";
vector<char> z = {'k', 'C', '7', 'a'};
sort(z.begin(), z.end());
for (auto x : z) cout << x << " ";
cout << "\n";
vector<pair<int, int>> p = {{2, 5}, {1, 9}, {2, 1}};
sort(p.begin(), p.end());
for (auto [a, b] : p) cout << a << "," << b << " ";
cout << "\n";
▶ Wyjście
-1.25 0.5 2 3.5 7 C a k 1,9 2,1 2,5

Znaki: cyfra '7' (kod 55) przed wielkim 'C' (67), a ono przed małymi 'a' (97) i 'k' (107).

Pary: (1, 9) jest pierwsza, bo ma najmniejsze first. Pary (2, 5) i (2, 1) remisują na first, więc rozstrzyga second: 1 < 5.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
vector<int> v = {5, 3, 8, 3};
sort(v.begin(), v.end());
for (auto x : v) cout << x;
Pokaż odpowiedź
3358Równe trójki stają obok siebie na początku.
Co wypisze ten fragment?
string s = "Kot";
sort(s.begin(), s.end());
cout << s;
Pokaż odpowiedź
KotNic się nie zmieniło! Wielkie K (kod 75) jest przed małymi o (111) i t (116), a o przed t — litery już stały po kolei.
Co wypisze ten fragment?
vector<string> s = {"b", "B", "a"};
sort(s.begin(), s.end());
for (auto x : s) cout << x;
Pokaż odpowiedź
BabWielkie B jest przed wszystkimi małymi literami.
Co wypisze ten fragment?
int t[5] = {5, 4, 3, 2, 1};
sort(t, t + 3);
for (int i = 0; i < 5; i++) cout << t[i];
Pokaż odpowiedź
34521Sortujemy tylko pudełka 0, 1, 2 (liczby 5, 4, 3). Pudełka 3 i 4 stoją bez zmian.
Co wypisze ten fragment?
vector<int> v = {9, 1, 8, 2, 7};
sort(v.begin() + 1, v.end());
for (auto x : v) cout << x;
Pokaż odpowiedź
91278Sortujemy od numeru 1 do końca: 1, 8, 2, 7 → 1, 2, 7, 8. Dziewiątka w pudełku 0 zostaje.
Co wypisze ten fragment?
vector<string> s = {"3", "100", "20"};
sort(s.begin(), s.end());
for (auto x : s) cout << x << " ";
Pokaż odpowiedź
100 20 3To napisy, więc porównujemy pierwsze znaki: '1' < '2' < '3'. Wartości liczb nie mają tu znaczenia.
Co wypisze ten fragment?
vector<int> v = {1, 2, 2, 3};
cout << is_sorted(v.begin(), v.end());
Pokaż odpowiedź
1Równe dwójki obok siebie nie psują porządku niemalejącego.
Co wypisze ten fragment?
string a = "lato", b = "tola";
sort(a.begin(), a.end());
sort(b.begin(), b.end());
cout << a << " " << (a == b);
Pokaż odpowiedź
alot 1Oba słowa mają litery a, l, o, t — po posortowaniu są identyczne, więc to anagramy.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Malejąco, k-ty element i mediana

W rankingach zwykle chcemy odwrotnie: najlepszy wynik na górze. W tej części poznasz trzy sposoby sortowania malejąco i zobaczysz, że w posortowanym vectorze każde pytanie w stylu „kto jest k-ty?” albo „jaki wynik jest środkowy?” ma odpowiedź pod konkretnym numerem pudełka.

Sposób 1: sort, a potem reverse

Ten sposób znasz z lekcji o vectorze: najpierw ustawiasz rosnąco, a potem odwracasz kolejność poleceniem reverse. Najmniejszy element ląduje na końcu, największy — na początku.

sort_reverse.cpp
vector<int> v = {4, 9, 1, 7, 3};
sort(v.begin(), v.end());        // 1 3 4 7 9
reverse(v.begin(), v.end());     // 9 7 4 3 1
for (auto x : v) cout << x << " ";
cout << "\n";
▶ Wyjście
9 7 4 3 1
Dwa kroki, ale za to bardzo łatwe do zapamiętania.

Sposób 2: strzałki od tyłu — rbegin() i rend()

Vector ma też strzałki, które chodzą od tyłu. Literka r w nazwie znaczy reverse — odwrotnie. v.rbegin() pokazuje ostatni element i przesuwa się w lewo, a v.rend() stoi tuż przed pierwszym — to „koniec” dla kogoś, kto idzie od prawej do lewej.

rbegin() stoi na ostatnim pudełku (numer 4) i idzie w lewo. rend() stoi przed pudełkiem 0 — tam kończy się droga od tyłu. Dla porównania: end() stoi za ostatnim.

Co się stanie, gdy dasz sort strzałki od tyłu? sort ustawi elementy rosnąco w kolejności, w jakiej je widzi, czyli od prawej do lewej. Jeśli patrząc od prawej liczby rosną, to patrząc normalnie, od lewej — maleją. Jedna linijka i gotowe: sort(v.rbegin(), v.rend()).

rbegin.cpp
vector<int> v = {4, 9, 1, 7, 3};
sort(v.rbegin(), v.rend());
for (auto x : v) cout << x << " ";
cout << "\n";
string s = "banan";
sort(s.rbegin(), s.rend());
cout << s << "\n";
▶ Wyjście
9 7 4 3 1 nnbaa

Działa też dla napisów: litery ustawiają się od końca alfabetu.

Ta sztuczka wygląda tajemniczo, ale w praktyce to po prostu „przepis na malejąco”. Nie musisz za każdym razem analizować, dlaczego działa.

Sposób 3: gotowa reguła greater

sort może dostać trzeci argument: regułę, która mówi, który z dwóch elementów ma stać wcześniej. Domyślna reguła to „mniejszy przed większym”. C++ ma gotową regułę odwrotną: greater<int>() — „większy przed mniejszym”. W nawiasach ostrych piszesz typ elementów vectora. O własnych regułach będzie cała część 5.

greater.cpp
vector<int> v = {4, 9, 1, 7, 3};
sort(v.begin(), v.end(), greater<int>());
for (auto x : v) cout << x << " ";
cout << "\n";
vector<string> s = {"ola", "ewa", "zosia", "ala"};
sort(s.begin(), s.end(), greater<string>());
for (auto x : s) cout << x << " ";
cout << "\n";
▶ Wyjście
9 7 4 3 1 zosia ola ewa ala

Wszystkie trzy sposoby dają ten sam wynik. Wybierz jeden i się go trzymaj. sort(v.rbegin(), v.rend()) jest najkrótszy, greater<int>() najłatwiej przeczytać, a sort + reverse najłatwiej zapamiętać.

Uwaga na typ: dla vector<long long> piszesz greater<long long>(), dla napisów greater<string>(). Nawiasy () na końcu są obowiązkowe.

W posortowanym każdy ma swój adres

Po posortowaniu rosnąco odpowiedzi na wiele pytań po prostu leżą pod znanymi numerami. Zakładamy, że v ma n elementów, numerowanych od 0:

pytaniepo sort rosnącodla 3 5 5 8 10 12 (n = 6)
najmniejszyv[0]3
największyv[n - 1]12
k-ty najmniejszy (k od 1)v[k - 1]k = 2: 5
k-ty największyv[n - k]k = 2: 10
k najmniejszychv[0] … v[k - 1]k = 3: 3 5 5
k największychv[n - k] … v[n - 1]k = 3: 8 10 12
v[1] = 5 to 2. najmniejszy (k − 1 = 1). v[4] = 10 to 2. największy (n − k = 6 − 2 = 4). Gdy liczby się powtarzają, „druga najmniejsza” może być równa pierwszej — tu v[1] = v[2] = 5.
adresy.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    for (auto &x : v) cin >> x;
    sort(v.begin(), v.end());
    cout << "najmniejszy: " << v[0] << "\n";
    cout << "najwiekszy: " << v[n - 1] << "\n";
    cout << k << ". od dolu: " << v[k - 1] << "\n";
    cout << k << ". od gory: " << v[n - k] << "\n";
    return 0;
}
▶ Wejście
7 3 40 85 72 91 66 85 58
▶ Wyjście
najmniejszy: 40 najwiekszy: 91 3. od dolu: 66 3. od gory: 85

Po sortowaniu: 40 58 66 72 85 85 91. Trzeci od dołu to v[2] = 66. Trzeci od góry to v[7 − 3] = v[4] = 85 — ten sam wynik co drugi od góry, bo dwie osoby mają po 85.

Wzór v[n - k] łatwo sprawdzić dla k = 1: v[n - 1], czyli ostatni — największy. Zgadza się.

Mediana — wartość środkowa

Mediana to liczba, która po posortowaniu stoi w samym środku: połowa liczb jest od niej mniejsza (albo równa), połowa — większa (albo równa). Dlaczego nie średnia? Bo średnią potrafi zepsuć jedna dziwna liczba. Pięć osób zarabia 2000, 2100, 2300, 2500 i 50 000 zł. Średnia to 11 780 zł — nikt tyle nie zarabia! Mediana to 2300 zł i ona naprawdę mówi, ile zarabia „typowa” osoba.

Gdy n jest nieparzyste, środek jest jeden: v[n / 2] (dzielenie całkowite). Dla n = 5 to v[2] — przed nim stoją dwa elementy i za nim dwa. Gdy n jest parzyste, środki są dwa: v[n / 2 - 1] i v[n / 2]. Wtedy medianą zwykle nazywa się ich średnią — ale zawsze czytaj, co dokładnie mówi zadanie.

Dla n = 5 środek to v[2]. Dla n = 6 środki są dwa: v[2] = 4 i v[3] = 8, więc mediana to (4 + 8) / 2 = 6.
mediana.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (auto &x : v) cin >> x;
    sort(v.begin(), v.end());
    cout << fixed << setprecision(1);
    if (n % 2 == 1) {
        cout << (double)v[n / 2] << "\n";
    } else {
        cout << (v[n / 2 - 1] + v[n / 2]) / 2.0 << "\n";
    }
    return 0;
}
▶ Wejście 1
5 2500 2000 50000 2300 2100
▶ Wyjście 1
2300.0
▶ Wejście 2
6 9 1 12 4 3 8
▶ Wyjście 2
6.0

Dzielimy przez 2.0, a nie przez 2. Pamiętasz pułapkę z pierwszej lekcji? (3 + 4) / 2 to 3, bo dzielenie dwóch liczb całkowitych obcina część po przecinku. (3 + 4) / 2.0 to 3.5.

W gałęzi z nieparzystym n zamieniamy liczbę na double, żeby obie odpowiedzi wyglądały tak samo — z jedną cyfrą po kropce.

Uwaga na ogromne liczby: suma dwóch liczb rzędu 2 miliardów nie mieści się w int. W zadaniach z dużymi wartościami trzymaj je w long long.

Najlepsze k: suma i próg

Po posortowaniu k największych liczb stoi na końcu, w pudełkach od n − k do n − 1. Suma k najlepszych wyników to po prostu suma tego kawałka. A teraz pytanie podchwytliwe: do finału przechodzi k najlepszych zawodników, ale remisy na granicy też przechodzą. Ile osób awansuje? Próg to wynik k-tego najlepszego, czyli v[n - k], a awansują wszyscy z wynikiem co najmniej takim jak próg — może ich być więcej niż k.

prog.cpp
vector<int> v = {70, 85, 90, 85, 60, 85, 95};
int n = v.size(), k = 3;
sort(v.begin(), v.end());           // 60 70 85 85 85 90 95
long long suma = 0;
for (int i = n - k; i < n; i++) suma += v[i];
int prog = v[n - k];
int ile = 0;
for (auto x : v) {
    if (x >= prog) ile++;
}
cout << "suma " << k << " najlepszych: " << suma << "\n";
cout << "prog: " << prog << ", awansuje: " << ile << "\n";
▶ Wyjście
suma 3 najlepszych: 270 prog: 85, awansuje: 5
Trzy najlepsze wyniki (niebieskie) to 85, 90, 95 — suma 270. Próg to v[7 − 3] = v[4] = 85. Pomarańczowe pudełka też mają 85, więc też awansują: razem 5 osób.

Cyfry liczby: największa i najmniejsza

Ciekawe zadanie: z cyfr liczby 30 521 ułóż największą i najmniejszą możliwą liczbę. Wczytujemy liczbę jako napis — wtedy każda cyfra to osobny znak i możemy je sortować. Największa liczba to cyfry malejąco: 53 210. Najmniejsza to cyfry rosnąco: 01 235… ale liczba nie może zaczynać się od zera! Rozwiązanie: po posortowaniu rosnąco znajdź pierwszą cyfrę różną od zera i zamień ją z cyfrą na początku. Z 01 235 robi się 10 235.

cyfry.cpp
string s = "30521";
string duza = s, mala = s;
sort(duza.rbegin(), duza.rend());     // 53210
sort(mala.begin(), mala.end());       // 01235
int i = 0;
while (i < (int)mala.size() && mala[i] == '0') i++;
if (i < (int)mala.size()) swap(mala[0], mala[i]);
cout << duza << " " << mala << "\n";
▶ Wyjście
53210 10235
Pętla while szuka pierwszej niezerowej cyfry (i = 1). Zamieniamy ją z pierwszym znakiem i dostajemy najmniejszą liczbę bez zera na początku: 10235. Warunek i < size() chroni przed liczbą złożoną z samych zer.
Sprawdź się w głowie

Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
vector<int> v = {4, 1, 3};
sort(v.rbegin(), v.rend());
for (auto x : v) cout << x;
Pokaż odpowiedź
431Strzałki od tyłu dają kolejność malejącą.
Co wypisze ten fragment?
vector<int> v = {2, 9, 2, 5};
sort(v.begin(), v.end(), greater<int>());
for (auto x : v) cout << x;
Pokaż odpowiedź
9522Większy przed mniejszym; równe dwójki obok siebie na końcu.
Co wypisze ten fragment?
vector<int> v = {7, 2, 9, 4, 1};
sort(v.begin(), v.end());
cout << v[1] << " " << v[v.size() - 2];
Pokaż odpowiedź
2 7Po sortowaniu: 1 2 4 7 9. v[1] to drugi najmniejszy (2), a v[n - 2] to drugi największy (7).
Co wypisze ten fragment?
vector<int> v = {5, 1, 4, 2, 3};
sort(v.begin(), v.end());
cout << v[v.size() / 2];
Pokaż odpowiedź
3n = 5, środek to v[2] w ciągu 1 2 3 4 5.
Co wypisze ten fragment?
vector<int> v = {4, 1, 3, 2};
sort(v.begin(), v.end());
cout << (v[1] + v[2]) / 2;
Pokaż odpowiedź
2Pułapka! Środki to 2 i 3, ale 5 / 2 w liczbach całkowitych daje 2. Żeby dostać 2.5, dziel przez 2.0.
Co wypisze ten fragment?
string s = "2024";
sort(s.rbegin(), s.rend());
cout << s;
Pokaż odpowiedź
4220Cyfry malejąco — to największa liczba, jaką da się z nich ułożyć.
Co wypisze ten fragment?
vector<int> v = {10, 30, 20, 30};
sort(v.begin(), v.end());
cout << v[v.size() - 2];
Pokaż odpowiedź
30Po sortowaniu: 10 20 30 30. Drugi największy to v[2] = 30 — taki sam jak pierwszy, bo trzydziestki są dwie.
Co wypisze ten fragment?
vector<int> v = {5, 1, 5, 3};
sort(v.begin(), v.end());
int s = 0;
for (int i = 2; i < 4; i++) s += v[i];
cout << s;
Pokaż odpowiedź
10Po sortowaniu: 1 3 5 5. Pętla sumuje dwa ostatnie, czyli dwa największe: 5 + 5.
Ćwiczenia · teraz Ty

9 ćwiczeń do tej części

0 / 9 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

2.1 Od największejłatwe✓ zaliczone Wypisz liczby od największej do najmniejszej. sort(v.rbegin(), v.rend())greater<int>()sort + reverse Rozwiąż 2.2 K-ta od dołu i od góryłatwe✓ zaliczone Podaj k-tą najmniejszą i k-tą największą liczbę. v[k - 1]v[n - k]powtórzenia Rozwiąż 2.3 Medianałatwe✓ zaliczone Znajdź wartość środkową — także wtedy, gdy liczb jest parzyście wiele. v[n / 2]średnia dwóch środkowych/ 2.0long long Rozwiąż 2.4 Próg awansułatwe✓ zaliczone Do finału wchodzi k najlepszych — i wszyscy, którzy remisują z k-tym. Ilu ich jest? v[n - k]remis na granicyliczenie ≥ Rozwiąż 2.5 Najlepsze kłatwe✓ zaliczone Wypisz k największych liczb od największej i ich sumę. sort malejącopierwsze klong long Rozwiąż 2.6 Największa i najmniejsza z cyfrśrednie✓ zaliczone Z cyfr liczby ułóż największą i najmniejszą liczbę — bez zera na początku. stringsort malejącopierwsza niezerowa cyfraswap Rozwiąż 2.7 Noty sędziówśrednie✓ zaliczone Odrzuć k najniższych i k najwyższych not, a resztę zsumuj. sortpomijanie końcówsuma kawałka Rozwiąż 2.8 Wicemistrzśrednie✓ zaliczone Drugi najlepszy wynik — inny niż najlepszy. Ilu zawodników go ma? sort malejącoróżne wartościprzypadek BRAK Rozwiąż 2.9 Silni na słabychśrednie✓ zaliczone Podziel 2n graczy na dwie równe drużyny tak, by różnica sił była jak największa. sortn największychn najmniejszychlong long Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

Po sortowaniu: równe obok siebie, najbliżsi obok siebie

Sortowanie robi z danymi dwie bardzo pożyteczne rzeczy. Po pierwsze: równe wartości stają obok siebie, więc łatwo je policzyć i pogrupować. Po drugie: liczby bliskie sobie też stają obok siebie, więc najmniejszą różnicę znajdziesz, patrząc tylko na sąsiadów. W tej części wykorzystasz obie te rzeczy.

Równe liczby tworzą grupy

Spójrz na liczby 5, 2, 8, 2, 5, 5. W nieposortowanym ciągu piątki są porozrzucane i żeby je policzyć, trzeba przejrzeć wszystko. Po posortowaniu wszystkie piątki tworzą jeden kawałek bez przerw — będziemy go nazywać grupą.

Trzy grupy: dwie dwójki (niebieskie), trzy piątki (pomarańczowe) i jedna ósemka (zielona). Każda grupa to kawałek bez przerw.

Ile jest różnych liczb?

W posortowanym ciągu nowa wartość zaczyna się dokładnie tam, gdzie v[i] != v[i - 1] — element różni się od swojego lewego sąsiada. Pierwszy element zawsze zaczyna grupę. Liczba różnych wartości to więc 1 plus liczba miejsc, w których coś się zmienia.

ile_roznych.cpp
vector<int> v = {5, 2, 8, 2, 5, 5};
sort(v.begin(), v.end());          // 2 2 5 5 5 8
int roznych = 1;
for (int i = 1; i < (int)v.size(); i++) {
    if (v[i] != v[i - 1]) roznych++;
}
cout << roznych << "\n";
▶ Wyjście
3
iv[i − 1]v[i]różne?roznych
start———1
122nie1
225tak2
355nie2
455nie2
558tak3
Bez sortowania to nie działa Na nieposortowanych danych 5, 2, 5 ten sam kod naliczy 3 „różne”, bo dwie piątki nie stoją obok siebie. Najpierw sort, potem liczenie. Ten sam kod nie zadziała też dla pustego vectora (zaczynamy od 1) — w zadaniach n jest zwykle co najmniej 1, ale warto o tym pamiętać.

Grupa po grupie: wartość i ile razy

Teraz chcemy wypisać każdą wartość razem z liczbą jej wystąpień. Użyjemy schematu z dwoma numerami: i to początek grupy, a j biegnie w prawo, dopóki widzi tę samą wartość. Gdy j się zatrzyma, grupa to pudełka od i do j − 1, ma j − i elementów, a następna grupa zaczyna się w j — więc i przeskakuje na j.

grupy.cpp
vector<int> v = {5, 2, 8, 2, 5, 5};
sort(v.begin(), v.end());
int n = v.size();
int i = 0;
while (i < n) {
    int j = i;
    while (j < n && v[j] == v[i]) j++;
    cout << v[i] << " x" << j - i << "\n";
    i = j;                          // skok na początek następnej grupy
}
▶ Wyjście
2 x2 5 x3 8 x1
Druga grupa: i = 2 (pierwsza piątka), j zatrzymało się na 5 (ósemka jest już inna). Grupa ma j − i = 3 elementy. Potem i = j = 5 i zaczynamy od ósemki.

Ten schemat warto zapamiętać — przyda się w wielu zadaniach. Zauważ warunek j < n && v[j] == v[i]: najpierw sprawdzamy, czy j nie wyszło za vector, a dopiero potem czytamy v[j]. Odwrotna kolejność czytałaby pudełko spoza vectora.

Pewnie pamiętasz z lekcji o tablicach tablicę liczników, która robi podobną rzecz. Działa jednak tylko dla małych liczb — dla liczby 1 000 000 000 potrzebowałbyś miliarda liczników! Sortowanie i grupy działają dla dowolnych wartości: ogromnych, ujemnych, a nawet napisów.

Najczęstsza wartość

Najczęstsza wartość to ta z najdłuższą grupą. Przechodzimy grupa po grupie i zapamiętujemy najlepszą. Jeśli kilka wartości remisuje, zwykle zadanie każe wybrać najmniejszą — a ponieważ grupy idą od najmniejszych wartości, wystarczy zmieniać zapamiętaną wartość tylko przy ściśle dłuższej grupie (znak >, nie >=).

najczestsza.cpp
vector<int> v = {4, 7, 4, 1, 7, 9, 7, 4};
sort(v.begin(), v.end());          // 1 4 4 4 7 7 7 9
int n = v.size();
int najW = v[0], najIle = 0;
int i = 0;
while (i < n) {
    int j = i;
    while (j < n && v[j] == v[i]) j++;
    if (j - i > najIle) {           // ściśle więcej
        najIle = j - i;
        najW = v[i];
    }
    i = j;
}
cout << najW << " (" << najIle << " razy)\n";
▶ Wyjście
4 (3 razy)

Czwórki i siódemki występują po 3 razy. Najpierw trafiamy na grupę czwórek (3 > 0, zapamiętujemy). Grupa siódemek też ma 3, ale 3 nie jest większe od 3 — zostaje czwórka, czyli mniejsza z remisujących wartości.

Gdybyś napisał >=, wygrałaby siódemka — ostatnia z remisujących.

unique — powtórzenia znikają jedną linijką

Często chcesz zostawić tylko różne wartości. Służy do tego zestaw dwóch poleceń, który pisze się zawsze razem:

unique_wzor.cpp
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

Jak to działa? unique przechodzi po vectorze i z każdej grupy stojących obok siebie równych elementów zostawia jeden, przesuwając je na początek. Vectora jednak nie skraca: na końcu zostają jakieś śmieci, a unique zwraca strzałkę na miejsce, w którym się zaczynają — nowy koniec. Dlatego od razu wołamy erase, który usuwa wszystko od tej strzałki do end().

unique ustawia różne wartości na początku (zielone) i zwraca strzałkę na pierwszy „śmieć”. erase usuwa kawałek od tej strzałki do end() — zostaje dokładnie 2, 5, 8.
unique.cpp
vector<int> v = {5, 2, 8, 2, 5, 5};
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
cout << v.size() << ":";
for (auto x : v) cout << " " << x;
cout << "\n";
▶ Wyjście
3: 2 5 8
unique_bez_sort.cpp
vector<int> v = {5, 2, 5, 5, 2};
v.erase(unique(v.begin(), v.end()), v.end());
cout << v.size() << ":";
for (auto x : v) cout << " " << x;
cout << "\n";
▶ Wyjście — bez sortowania
4: 5 2 5 2
unique bez sort to pułapka unique zbija tylko powtórzenia, które stoją obok siebie. W przykładzie po prawej sklejone zostały tylko dwie piątki ze środka — reszta została. Zawsze: najpierw sort, potem unique, a unique zawsze razem z erase.

Najbliżsi sąsiedzi

Przy prostej drodze stoją domy. Które dwa stoją najbliżej siebie? Naiwnie: sprawdź każdą parę domów — przy 100 000 domów to 5 miliardów par, o wiele za dużo. Sprytnie: posortuj pozycje. Dwa najbliższe domy na pewno staną wtedy obok siebie — wystarczy porównać tylko sąsiadów: v[i + 1] - v[i].

Dlaczego? Weźmy trzy domy a ≤ b ≤ c. Odległość od a do c to (b − a) + (c − b) — jest co najmniej tak duża jak każda z dwóch krótszych. Dom, który stoi „pomiędzy”, zawsze jest bliżej. Dlatego para nie-sąsiadów nigdy nie wygra z parą sąsiadów.

sasiedzi.cpp
vector<int> v = {40, 7, 22, 31, 12, 60};
sort(v.begin(), v.end());           // 7 12 22 31 40 60
int najmniej = v[1] - v[0];
int najwiecej = v[1] - v[0];
for (int i = 0; i + 1 < (int)v.size(); i++) {
    int d = v[i + 1] - v[i];
    najmniej = min(najmniej, d);
    najwiecej = max(najwiecej, d);
}
cout << "najblizej: " << najmniej << "\n";
cout << "najwieksza przerwa: " << najwiecej << "\n";
▶ Wyjście
najblizej: 5 najwieksza przerwa: 20
Różnice sąsiadów: 5, 10, 9, 9, 20. Najmniejsza (niebieskie): 7 i 12. Największa przerwa (pomarańczowe): między 40 a 60.

Okno k elementów: najmniejszy rozrzut

Trener chce wybrać do sztafety k zawodników o jak najbardziej podobnym czasie — tak, żeby różnica między najszybszym a najwolniejszym z nich była jak najmniejsza. Po posortowaniu najlepiej wybrać k zawodników stojących kolejno obok siebie. Każde takie „okno” od numeru i do i + k − 1 ma rozrzut v[i + k - 1] - v[i] (ostatni minus pierwszy), i spośród okien wybieramy najlepsze.

okno.cpp
vector<int> v = {50, 41, 63, 47, 58, 44};
int k = 3;
sort(v.begin(), v.end());           // 41 44 47 50 58 63
int najlepiej = v[k - 1] - v[0];
for (int i = 0; i + k - 1 < (int)v.size(); i++) {
    najlepiej = min(najlepiej, v[i + k - 1] - v[i]);
}
cout << najlepiej << "\n";
▶ Wyjście
6
Okna po 3: (41..47) rozrzut 6, (44..50) rozrzut 6, (47..58) rozrzut 11, (50..63) rozrzut 13. Najlepsze: 6.

Dlaczego wybór „z dziurami” nie może być lepszy? Jeśli wybierzesz k zawodników i między najszybszym a najwolniejszym z nich stoi ktoś niewybrany, możesz wymienić na niego jednego ze skrajnych — rozrzut nie wzrośnie. Wymieniając tak dalej, dojdziesz do okna bez dziur, które jest co najmniej tak dobre.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Ile różnych liczb wypisze ten program?
vector<int> v = {3, 1, 3, 2, 1};
sort(v.begin(), v.end());
int r = 1;
for (int i = 1; i < 5; i++) if (v[i] != v[i - 1]) r++;
cout << r;
Pokaż odpowiedź
3Po sortowaniu: 1 1 2 3 3. Wartość zmienia się dwa razy (1→2, 2→3), więc różnych jest 1 + 2 = 3.
Co wypisze ten fragment?
vector<int> v = {3, 1, 3, 1, 3};
sort(v.begin(), v.end());
int i = 0;
while (i < 5) {
    int j = i;
    while (j < 5 && v[j] == v[i]) j++;
    cout << v[i] << ":" << j - i << " ";
    i = j;
}
Pokaż odpowiedź
1:2 3:3Po sortowaniu: 1 1 3 3 3 — dwie grupy.
Co wypisze ten fragment?
vector<int> v = {1, 1, 2, 1};
v.erase(unique(v.begin(), v.end()), v.end());
cout << v.size();
Pokaż odpowiedź
3Bez sortowania! unique skleja tylko dwie jedynki z początku: zostaje 1 2 1.
Co wypisze ten fragment?
vector<int> v = {1, 1, 2, 1};
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
cout << v.size();
Pokaż odpowiedź
2Teraz jedynki stoją obok siebie: 1 1 1 2 → 1 2.
Co wypisze ten fragment?
vector<int> v = {10, 4, 7, 15};
sort(v.begin(), v.end());
int m = 1000;
for (int i = 0; i + 1 < 4; i++) m = min(m, v[i + 1] - v[i]);
cout << m;
Pokaż odpowiedź
3Po sortowaniu 4 7 10 15, różnice sąsiadów: 3, 3, 5.
Co wypisze ten fragment?
vector<int> v = {1, 5, 6, 10};
int k = 2, b = 1000;
for (int i = 0; i + k - 1 < 4; i++) b = min(b, v[i + k - 1] - v[i]);
cout << b;
Pokaż odpowiedź
1Okna po 2 elementy: (1, 5), (5, 6), (6, 10) — rozrzuty 4, 1, 4.
Co wypisze ten fragment?
vector<int> v = {4, 2, 4, 2, 7};
sort(v.begin(), v.end());
int w = v[0], best = 0, i = 0;
while (i < 5) {
    int j = i;
    while (j < 5 && v[j] == v[i]) j++;
    if (j - i > best) { best = j - i; w = v[i]; }
    i = j;
}
cout << w << " " << best;
Pokaż odpowiedź
2 2Dwójki i czwórki są po dwie. Remis wygrywa pierwsza grupa, czyli mniejsza wartość — bo zmieniamy tylko przy >.
Co wypisze ten fragment?
vector<string> s = {"kot", "pies", "kot", "mysz", "pies", "kot"};
sort(s.begin(), s.end());
s.erase(unique(s.begin(), s.end()), s.end());
for (auto x : s) cout << x << " ";
Pokaż odpowiedź
kot mysz piesGrupy działają też dla napisów: zostają różne słowa, alfabetycznie.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Jak sortuje komputer? Sortowanie ręcznie

sort to gotowe narzędzie i w zadaniach będziesz go używać prawie zawsze. Mimo to warto raz zobaczyć, jak można sortować samemu. Po pierwsze — to świetny trening pętli, ifów i swap. Po drugie — zadania czasem pytają o przebieg konkretnego algorytmu: „ile zamian zrobi sortowanie bąbelkowe?”. Po trzecie — zrozumiesz, dlaczego jedne sposoby są szybkie, a inne wolne.

Poznasz cztery metody. Przy każdej jest animacja: klikaj „Krok ▸”, żeby oglądać algorytm ruch po ruchu, albo „Odtwórz”, żeby leciał sam. Pod słupkami jest opis tego, co dzieje się w danym kroku, i numery pudełek. „Nowe liczby” losuje inne dane — sprawdź, czy przewidzisz następny ruch!

Sortowanie przez wybieranie

Pomysł jest taki, jak przy ustawianiu szeregu na WF-ie. Wybierz najniższą osobę i postaw ją na pierwszym miejscu. Z pozostałych wybierz najniższą i postaw na drugim. I tak dalej. Po angielsku: selection sort.

W programie: w rundzie numer i szukamy najmniejszego elementu w kawałku od i do końca (zapamiętujemy jego numer m) i zamieniamy go z elementem v[i]. Po tej rundzie pudełko i jest gotowe i już go nie ruszamy.

Sortowanie przez wybieranie — animacja
Animacja działa po włączeniu JavaScriptu.
wybieranie.cpp
vector<int> v = {5, 2, 4, 1, 3};
int n = v.size();
for (int i = 0; i < n - 1; i++) {
    int m = i;                      // numer najmniejszego od i do końca
    for (int j = i + 1; j < n; j++) {
        if (v[j] < v[m]) m = j;
    }
    swap(v[i], v[m]);               // najmniejszy na miejsce i
    for (auto x : v) cout << x << " ";
    cout << "\n";
}
▶ Wyjście
1 2 4 5 3 1 2 4 5 3 1 2 3 5 4 1 2 3 4 5
runda iszukamy wnajmniejszypo zamianie
05 2 4 1 31 (m = 3)1 2 4 5 3
12 4 5 32 (m = 1)1 2 4 5 3
24 5 33 (m = 4)1 2 3 5 4
35 44 (m = 4)1 2 3 4 5

W rundzie 1 najmniejszy już stał na swoim miejscu (m = i), więc swap zamienia element sam ze sobą — nic się nie dzieje i ciąg się nie zmienia. Ostatniej rundy (i = n − 1) nie ma, bo jeden element, który został, sam stoi na właściwym miejscu.

Ile porównań v[j] < v[m] wykona ta metoda? W pierwszej rundzie n − 1, w drugiej n − 2, … w ostatniej 1. Razem (n − 1) + (n − 2) + … + 1 = n·(n − 1) / 2. Dla n = 5 to 10, dla n = 1000 to prawie pół miliona, dla n = 100 000 — prawie 5 miliardów. Zapamiętaj tę liczbę, wrócimy do niej.

Sortowanie bąbelkowe

Tu porównujemy tylko sąsiadów. Idziemy od lewej do prawej i gdy dwaj sąsiedzi stoją w złej kolejności (lewy większy od prawego), zamieniamy ich miejscami. Po jednym takim przejściu — rundzie — największy element na pewno „wypłynie” na sam koniec, jak bąbelek powietrza w wodzie. Stąd nazwa: bubble sort. W następnej rundzie na przedostatnie miejsce wypłynie drugi największy, i tak dalej.

Sortowanie bąbelkowe — animacja
Animacja działa po włączeniu JavaScriptu.
babelkowe.cpp
vector<int> v = {5, 1, 4, 2, 8};
int n = v.size();
int zamian = 0;
for (int runda = 0; runda < n - 1; runda++) {
    bool bylaZamiana = false;
    for (int j = 0; j + 1 < n - runda; j++) {
        if (v[j] > v[j + 1]) {
            swap(v[j], v[j + 1]);
            zamian++;
            bylaZamiana = true;
        }
    }
    cout << "po rundzie " << runda + 1 << ":";
    for (auto x : v) cout << " " << x;
    cout << "\n";
    if (!bylaZamiana) break;        // nic się nie zmieniło — koniec
}
cout << "zamian: " << zamian << "\n";
▶ Wyjście
po rundzie 1: 1 4 2 5 8 po rundzie 2: 1 2 4 5 8 po rundzie 3: 1 2 4 5 8 zamian: 4

Runda 1: 5 i 1 — zamiana; 5 i 4 — zamiana; 5 i 2 — zamiana; 5 i 8 — dobrze. Piątka przepłynęła trzy miejsca w prawo, a ósemka stoi na końcu.

Runda 2: zamienia się tylko para 4 i 2. Runda 3: nic się nie zamienia — wszystko już stoi po kolei, więc break kończy pętlę. Bez tej flagi bylaZamiana program niepotrzebnie wykonałby jeszcze rundę 4.

Warunek j + 1 < n - runda: w każdej kolejnej rundzie pomijamy końcówkę, bo tam stoją już największe, gotowe elementy.

Zamiany bąbelków = pary w złej kolejności Każda zamiana sąsiadów naprawia dokładnie jedną parę elementów, które stały w złej kolejności (lewy większy od prawego). Takie pary nazywa się inwersjami. Dlatego sortowanie bąbelkowe robi dokładnie tyle zamian, ile jest inwersji w ciągu. W ciągu 5 1 4 2 8 inwersje to (5, 1), (5, 4), (5, 2) i (4, 2) — cztery, tak jak zamian w programie obok.

Sortowanie przez wstawianie

Tak układasz karty w ręce: lewa część ręki jest już ułożona, bierzesz kolejną kartę i wsuwasz ją w odpowiednie miejsce, przesuwając większe karty w prawo. Po angielsku: insertion sort.

W programie: dla każdego i od 1 do n − 1 zapamiętujemy x = v[i]. Potem idziemy w lewo od j = i − 1 i dopóki v[j] > x, przesuwamy v[j] o jedno pudełko w prawo. Gdy natrafimy na element nie większy od x (albo dojdziemy do początku), x wskakuje w zwolnione miejsce j + 1.

Sortowanie przez wstawianie — animacja
Animacja działa po włączeniu JavaScriptu.
wstawianie.cpp
vector<int> v = {7, 3, 5, 1, 6};
int n = v.size();
for (int i = 1; i < n; i++) {
    int x = v[i];                    // karta, którą wstawiamy
    int j = i - 1;
    while (j >= 0 && v[j] > x) {
        v[j + 1] = v[j];             // większa karta w prawo
        j--;
    }
    v[j + 1] = x;                    // x w wolne miejsce
    for (auto y : v) cout << y << " ";
    cout << "\n";
}
▶ Wyjście
3 7 5 1 6 3 5 7 1 6 1 3 5 7 6 1 3 5 6 7
Ostatni krok: lewa część 1 3 5 7 jest ułożona (niebieska), wstawiamy 6. Siódemka przesuwa się w prawo, piątka już nie (5 nie jest większa od 6), więc 6 wskakuje do pudełka 3.

Warunek j >= 0 && v[j] > x — najpierw pilnujemy, żeby j nie wyszło przed vector, a dopiero potem czytamy v[j].

Ciekawostka: wstawianie jest bardzo szybkie, gdy dane są prawie posortowane — każda karta przesuwa się wtedy tylko o kilka miejsc. Gdy dane są ułożone odwrotnie, każda nowa karta wędruje aż na początek i porównań jest znowu około n·n / 2.

Sortowanie przez zliczanie

Tę metodę znasz z lekcji o tablicach, choć może nie wiedziałeś, że to sortowanie. Gdy wartości są małe — oceny 1–6, wiek 0–120, cyfry 0–9 — w ogóle nie trzeba ich porównywać. Robimy licznik dla każdej możliwej wartości, przechodzimy po danych i zwiększamy liczniki. Potem idziemy po licznikach od najmniejszej wartości i każdą wartość wypisujemy tyle razy, ile mówi jej licznik.

Sortowanie przez zliczanie — animacja
Animacja działa po włączeniu JavaScriptu.
zliczanie.cpp
vector<int> oceny = {4, 6, 3, 4, 5, 2, 4, 6};
vector<int> licznik(7, 0);           // pudełka 0..6, używamy 1..6
for (auto x : oceny) licznik[x]++;
for (int w = 1; w <= 6; w++) {
    for (int k = 0; k < licznik[w]; k++) cout << w << " ";
}
cout << "\n";
for (int w = 1; w <= 6; w++) cout << w << ": " << licznik[w] << "  ";
cout << "\n";
▶ Wyjście
2 3 4 4 4 5 6 6 1: 0 2: 1 3: 1 4: 3 5: 1 6: 2

To najszybsza metoda z tej części: jedno przejście po danych i jedno po licznikach. Ma jednak wadę — działa tylko wtedy, gdy wartości są małe i nieujemne (albo da się je łatwo przesunąć, np. dodając stałą). Dla liczb do miliarda potrzebowalibyśmy miliarda liczników.

Przy okazji dostajemy za darmo liczbę wystąpień każdej oceny — to drugi wiersz wyniku.

Ile to trwa? Dwie pętle kontra sort

Wybieranie, bąbelki i wstawianie mają pętlę w pętli, więc dla n elementów wykonują rzędu n·n operacji. Gotowe sort używa sprytniejszych metod, które dzielą dane na połówki — robi rzędu n·log2n operacji (log2n to mniej więcej „ile razy da się podzielić n na pół”, dla miliona to około 20). Komputer wykonuje około 100–300 milionów prostych operacji na sekundę. Porównaj:

ndwie pętle: około n·nsort: około n·log₂n
10100około 35
1 0001 000 000 — błyskawicznieokoło 10 000
10 000100 000 000 — ok. pół sekundyokoło 140 000
100 00010 000 000 000 — kilkadziesiąt sekund, za wolno!około 1 700 000 — błyskawicznie
1 000 0001012 — godzinyokoło 20 000 000 — ułamek sekundy
Którą metodę wybrać na zawodach? Zawsze sort — chyba że zadanie pyta o przebieg konkretnego algorytmu (np. ile zamian zrobią bąbelki) albo wartości są tak małe, że wygodniej zliczać. Metody z dwiema pętlami pisz po to, żeby zrozumieć sortowanie i przećwiczyć pętle — przy n do kilku tysięcy też zdążą.

Dla ciekawych: jak robi to sort?

Szybkie metody dzielą problem na mniejsze kawałki. Sortowanie przez scalanie dzieli dane na dwie połówki, sortuje każdą osobno (tak samo — dzieląc dalej), a potem scala dwie ułożone połówki w jedną: porównuje ich początki i bierze mniejszy. Sortowanie szybkie wybiera jedną liczbę — piwot — i ustawia mniejsze od niej na lewo, a większe na prawo; potem robi to samo z każdą stroną. Obie metody wymagają rekurencji — funkcji, która woła samą siebie — więc ich kod napiszesz w lekcji Rekurencja. Na razie po prostu popatrz:

Sortowanie przez scalanie — animacja
Animacja działa po włączeniu JavaScriptu.
Sortowanie szybkie — animacja
Animacja działa po włączeniu JavaScriptu.
Sprawdź się w głowie

Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment — jedna runda sortowania przez wybieranie?
vector<int> v = {4, 3, 1, 2};
int m = 0;
for (int j = 1; j < 4; j++) if (v[j] < v[m]) m = j;
swap(v[0], v[m]);
for (auto x : v) cout << x;
Pokaż odpowiedź
1342Najmniejsza jest jedynka (m = 2). Zamienia się z czwórką z pudełka 0.
Co wypisze ten fragment — jedna runda bąbelków?
vector<int> v = {4, 3, 1, 2};
for (int j = 0; j + 1 < 4; j++)
    if (v[j] > v[j + 1]) swap(v[j], v[j + 1]);
for (auto x : v) cout << x;
Pokaż odpowiedź
31244 i 3 — zamiana (3 4 1 2); 4 i 1 — zamiana (3 1 4 2); 4 i 2 — zamiana (3 1 2 4). Czwórka wypłynęła na koniec.
Co wypisze ten fragment — dwa kroki wstawiania?
vector<int> v = {4, 3, 1, 2};
for (int i = 1; i < 3; i++) {
    int x = v[i], j = i - 1;
    while (j >= 0 && v[j] > x) { v[j + 1] = v[j]; j--; }
    v[j + 1] = x;
}
for (auto x : v) cout << x;
Pokaż odpowiedź
1342Wstawiamy 3 (3 4 1 2), potem 1 (1 3 4 2). Dwójka jeszcze czeka.
Ile zamian zrobią bąbelki?
vector<int> v = {3, 2, 1};
int z = 0;
for (int r = 0; r < 2; r++)
    for (int j = 0; j + 1 < 3 - r; j++)
        if (v[j] > v[j + 1]) { swap(v[j], v[j + 1]); z++; }
cout << z;
Pokaż odpowiedź
3Ciąg 3 2 1 ma trzy inwersje: (3, 2), (3, 1), (2, 1). Każda zamiana naprawia jedną.
Ile porównań wykona sortowanie przez wybieranie dla n = 5?
int n = 5, p = 0;
for (int i = 0; i < n - 1; i++)
    for (int j = i + 1; j < n; j++) p++;
cout << p;
Pokaż odpowiedź
104 + 3 + 2 + 1 = 10, czyli n·(n − 1) / 2.
Co wypisze sortowanie przez zliczanie?
vector<int> v = {3, 1, 3, 0};
vector<int> c(4, 0);
for (auto x : v) c[x]++;
for (int w = 0; w < 4; w++)
    for (int k = 0; k < c[w]; k++) cout << w;
Pokaż odpowiedź
0133Liczniki: c[0] = 1, c[1] = 1, c[2] = 0, c[3] = 2.
Ile rund wykonają bąbelki z flagą?
vector<int> v = {1, 2, 3, 4};
int rund = 0;
for (int r = 0; r < 3; r++) {
    rund++;
    bool z = false;
    for (int j = 0; j + 1 < 4 - r; j++)
        if (v[j] > v[j + 1]) { swap(v[j], v[j + 1]); z = true; }
    if (!z) break;
}
cout << rund;
Pokaż odpowiedź
1Ciąg jest już posortowany: w pierwszej rundzie nie ma zamian i flaga przerywa pętlę.
Ile przesunięć zrobi wstawianie?
vector<int> v = {2, 1, 3};
int p = 0;
for (int i = 1; i < 3; i++) {
    int x = v[i], j = i - 1;
    while (j >= 0 && v[j] > x) { v[j + 1] = v[j]; j--; p++; }
    v[j + 1] = x;
}
cout << p;
Pokaż odpowiedź
1Tylko dwójka przesuwa się w prawo, żeby zrobić miejsce jedynce. Trójka od razu jest na miejscu.
Ćwiczenia · teraz Ty

7 ćwiczeń do tej części

0 / 7 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Sortowanie po swojemu: własna reguła porównania

Do tej pory sortowaliśmy „normalnie”: liczby od najmniejszej, słowa alfabetycznie. A co, jeśli zadanie każe ustawić liczby według ostatniej cyfry? Albo słowa od najkrótszego? Albo najpierw parzyste, potem nieparzyste? Wtedy dajesz sort własną regułę. To najważniejsza nowa umiejętność tej lekcji, więc pójdziemy bardzo powoli.

Reguła odpowiada na jedno pytanie

Wyobraź sobie, że sort to sędzia, który ustawia zawodników w szeregu. Sam nie wie, kto powinien stać wcześniej — za każdym razem pyta Twoją regułę o dwa elementy, a i b:

„Czy a ma stać PRZED b?”

Reguła odpowiada true (tak) albo false (nie). Sędzia zadaje to pytanie wiele razy, o różne pary, i na podstawie odpowiedzi ustawia wszystkich. Domyślna reguła sort to po prostu a < b: „a stoi przed b, gdy a jest mniejsze”. Dlatego bez reguły dostajesz kolejność rosnącą.

Jak zapisać regułę: lambda

Regułę piszemy jako trzeci argument sort, w specjalnym zapisie zwanym lambdą. Lambda to mały kawałek programu bez nazwy, napisany dokładnie w miejscu, w którym jest potrzebny. Oto reguła „większy przed mniejszym”:

lambda_wzor.cpp
sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
[]

Nawiasy kwadratowe mówią: „tu zaczyna się reguła”. Na razie zostawiamy je puste.

(int a, int b)

Dwa porównywane elementy. Ich typ to typ elementów vectora: dla vector<int> piszesz int, dla napisów string.

{ return a > b; }

Odpowiedź na pytanie „czy a przed b?”. return oddaje ją sędziemu — znasz to słowo z return 0; w main.

);

Na końcu zamykamy nawias okrągły od sort( i stawiamy średnik. Łatwo o tym zapomnieć!

regula_malejaco.cpp
vector<int> v = {5, 2, 8, 1, 9};
sort(v.begin(), v.end(), [](int a, int b) {
    return a > b;            // a przed b, gdy a jest większe
});
for (auto x : v) cout << x << " ";
cout << "\n";
sort(v.begin(), v.end(), [](int a, int b) {
    return a < b;            // to samo co zwykłe sort
});
for (auto x : v) cout << x << " ";
cout << "\n";
▶ Wyjście
9 8 5 2 1 1 2 5 8 9

Regułę można rozpisać na kilka linijek — tak jest czytelniej, gdy robi się dłuższa.

Przeczytaj pierwszą regułę na głos: „a ma stać przed b wtedy, gdy a jest większe od b”. Czyli większe liczby idą na przód — malejąco. Druga reguła to zwykła kolejność rosnąca, zapisana wprost.

Sztuczka do sprawdzania reguły: weź dwie konkretne liczby, np. a = 8 i b = 2, i zapytaj, co zwróci reguła. 8 > 2 to true, więc 8 stanie przed 2. Zgadza się z tym, co chcesz?

Według ostatniej cyfry — i co z remisami?

Ostatnia cyfra liczby to x % 10 (dla liczb nieujemnych). Reguła „mniejsza ostatnia cyfra wcześniej” wygląda tak: return a % 10 < b % 10;. Ale co, jeśli dwie liczby mają tę samą ostatnią cyfrę, jak 21 i 11? Reguła odpowiada wtedy „nie” w obie strony: ani 21 nie jest przed 11, ani 11 przed 21. Dla sędziego to remis — i sort może ustawić takie liczby w dowolnej kolejności. Nie ma żadnej gwarancji, że zostaną tak, jak były na wejściu.

Dlatego dobra reguła prawie zawsze ma drugie kryterium, które rozstrzyga remisy: „gdy ostatnie cyfry są takie same, mniejsza liczba wcześniej”.

ostatnia_cyfra.cpp
vector<int> v = {23, 15, 42, 11, 30, 21, 5};
sort(v.begin(), v.end(), [](int a, int b) {
    if (a % 10 != b % 10) {
        return a % 10 < b % 10;   // różne cyfry — decyduje cyfra
    }
    return a < b;                 // remis — decyduje cała liczba
});
for (auto x : v) cout << x << " ";
cout << "\n";
▶ Wyjście
30 11 21 42 23 5 15
ostatnia cyfraliczbyw środku grupy
030—
111, 2111 < 21
242—
323—
55, 155 < 15
Wzór na kilka kryteriów if (pierwsze kryterium jest różne) return porównanie według pierwszego; potem if (drugie jest różne) return porównanie według drugiego; … a na końcu return porównanie według ostatniego;. Jak w słowniku: najpierw pierwsza litera, a dopiero przy remisie — następna. Tego wzoru będziesz używać cały czas.

Reguła może liczyć

W środku lambdy możesz pisać zwykły kod: zmienne, pętle, ify. Na przykład sortowanie według sumy cyfr: najpierw liczymy sumę cyfr a i sumę cyfr b (pętlą while, jak w lekcji o pętli while), a potem je porównujemy. Remis rozstrzyga sama liczba.

suma_cyfr.cpp
vector<int> v = {91, 8, 125, 44, 70, 17};
sort(v.begin(), v.end(), [](int a, int b) {
    int sa = 0, sb = 0;
    int x = a;
    while (x > 0) { sa += x % 10; x /= 10; }
    x = b;
    while (x > 0) { sb += x % 10; x /= 10; }
    if (sa != sb) return sa < sb;
    return a < b;
});
for (auto x : v) cout << x << " ";
cout << "\n";
▶ Wyjście
70 8 17 44 125 91
liczbasuma cyfr
707
88
178
448
1258
9110

Aż cztery liczby mają sumę cyfr 8 — o ich kolejności decyduje drugie kryterium: 8 < 17 < 44 < 125.

a i b w regule to kopie elementów — mógłbyś je zmieniać i vector by tego nie zauważył. Ale dla czytelności lepiej liczyć na osobnej zmiennej (tu x), tak jak w przykładzie.

Najbliżej zera

Odległość liczby od zera to jej wartość bezwzględna: abs(x). Reguła „bliżej zera wcześniej, a przy remisie (−3 i 3) ujemna wcześniej”:

abs.cpp
vector<int> v = {3, -2, 2, -5, 0, -3};
sort(v.begin(), v.end(), [](int a, int b) {
    if (abs(a) != abs(b)) return abs(a) < abs(b);
    return a < b;              // -3 przed 3
});
for (auto x : v) cout << x << " ";
cout << "\n";
▶ Wyjście
0 -2 2 -3 3 -5

Przy remisie −2 i 2 mają tę samą odległość od zera (2), więc rozstrzyga a < b: −2 jest mniejsze, staje pierwsze.

[&] — reguła, która widzi zmienne z main

Teraz chcemy sortować według odległości od liczby k, którą wczytaliśmy w main: abs(a - k). Problem: lambda z pustymi nawiasami [] nie widzi zmiennych z main — kompilator zgłosi błąd, że nie zna k. Rozwiązanie: wpisz w nawiasy kwadratowe znak &. Zapis [&] znaczy „reguła może zaglądać do zmiennych z miejsca, w którym ją napisano”. To ten sam znak co w for (auto &x : v) — tam też oznaczał „pracuj na oryginale, nie na kopii”.

odleglosc_od_k.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    for (auto &x : v) cin >> x;
    sort(v.begin(), v.end(), [&](int a, int b) {
        if (abs(a - k) != abs(b - k)) return abs(a - k) < abs(b - k);
        return a < b;
    });
    for (auto x : v) cout << x << " ";
    cout << "\n";
    return 0;
}
▶ Wejście
6 10 1 12 8 20 10 15
▶ Wyjście
10 8 12 15 1 20
bez_ampersanda.cpp
int k = 10;
vector<int> v = {1, 12, 8};
sort(v.begin(), v.end(), [](int a, int b) {
    return abs(a - k) < abs(b - k);   // BŁĄD: [] nie widzi k
});
▶ Kompilator
error: 'k' is not captured

Odległości od 10: 10 → 0, 8 → 2, 12 → 2, 15 → 5, 1 → 9, 20 → 10. Remis 8 i 12 rozstrzyga mniejsza liczba.

Słowa po swojemu

Dla vectora napisów reguła dostaje dwa napisy. Najczęstsze życzenie: od najkrótszego słowa, a słowa tej samej długości — alfabetycznie.

dlugosc.cpp
vector<string> s = {"pies", "kot", "zebra", "mysz", "lew", "ara"};
sort(s.begin(), s.end(), [](string a, string b) {
    if (a.size() != b.size()) return a.size() < b.size();
    return a < b;
});
for (auto x : s) cout << x << " ";
cout << "\n";
▶ Wyjście
ara kot lew mysz pies zebra

Trzyliterowe słowa (ara, kot, lew) idą pierwsze i między sobą alfabetycznie. Potem czteroliterowe, na końcu „zebra”.

Pamiętasz, że wielkie litery są przed małymi? Gdy chcesz porównywać słowa bez względu na wielkość liter, w regule zrób kopie a i b, zamień w nich wszystkie litery na małe (tolower w pętli) i porównaj kopie.

Najpierw parzyste, potem nieparzyste

Chcemy dwie grupy: najpierw wszystkie parzyste rosnąco, potem wszystkie nieparzyste rosnąco. Zapisujemy w zmiennych bool, czy a i b są parzyste. Jeśli jedna jest parzysta, a druga nie — wcześniej stoi ta parzysta. Jeśli obie są tego samego rodzaju — mniejsza wcześniej.

parzyste.cpp
vector<int> v = {7, 4, -3, 10, 1, -6, 8};
sort(v.begin(), v.end(), [](int a, int b) {
    bool pa = (a % 2 == 0);
    bool pb = (b % 2 == 0);
    if (pa != pb) return pa;    // parzysta przed nieparzystą
    return a < b;
});
for (auto x : v) cout << x << " ";
cout << "\n";
▶ Wyjście
-6 4 8 10 -3 1 7

Linijka return pa; wymaga chwili namysłu. Wykonuje się tylko wtedy, gdy a i b są różnego rodzaju. Jeśli a jest parzyste (pa = true), to b nie jest — odpowiadamy „tak, a przed b”. Jeśli a jest nieparzyste (pa = false), to b jest parzyste — odpowiadamy „nie”.

Warunek a % 2 == 0 działa też dla liczb ujemnych. Gdybyś napisał a % 2 == 1, liczba −3 nie zostałaby uznana za nieparzystą, bo −3 % 2 to −1.

Żelazna zasada: dla równych — false

Reguła musi spełniać jeden warunek, którego kompilator nie sprawdzi za Ciebie: gdy pytasz o dwa elementy „równe” dla tej reguły, odpowiedź musi brzmieć false. W szczególności element nigdy nie może stać „przed samym sobą”. Dlatego w regule piszesz < albo >, a nigdy <= ani >=.

regula_zla.cpp
sort(v.begin(), v.end(), [](int a, int b) {
    return a <= b;     // ŹLE! Dla a == b odpowiada true
});
Zła reguła potrafi wysypać program Reguła z <= czasem działa na małych testach, a na dużych program nagle się wysypuje albo czyta pamięć spoza vectora — bez żadnego ostrzeżenia. Takie błędy są bardzo trudne do znalezienia. Druga podobna pułapka: reguła, która raz mówi „a przed b”, a za chwilę dla tej samej pary „b przed a” (np. losowa). Trzymaj się wzoru z ifami i ostrymi nierównościami, a wszystko będzie dobrze.

Reguła z nazwą

Długą regułę możesz zapisać w zmiennej i potem podawać jej nazwę. Typ takiej zmiennej jest bardzo skomplikowany, więc piszesz auto. Przydaje się, gdy tej samej reguły używasz kilka razy — albo po prostu dla czytelności.

regula_nazwa.cpp
auto wedlugDlugosci = [](string a, string b) {
    if (a.size() != b.size()) return a.size() < b.size();
    return a < b;
};
vector<string> owoce = {"kiwi", "banan", "figa", "jablko"};
vector<string> zwierzeta = {"wilk", "lis", "sowa", "bobr"};
sort(owoce.begin(), owoce.end(), wedlugDlugosci);
sort(zwierzeta.begin(), zwierzeta.end(), wedlugDlugosci);
for (auto x : owoce) cout << x << " ";
cout << "\n";
for (auto x : zwierzeta) cout << x << " ";
cout << "\n";
▶ Wyjście
figa kiwi banan jablko lis bobr sowa wilk

Tę samą regułę podajemy dwa razy — raz napisana, dwa razy użyta.

Uwaga na polskie litery: w napisie string litery takie jak „ś” czy „ó” zajmują po dwa znaki, więc size() słowa „ryś” to 4, a nie 3, i sortowanie według długości dałoby dziwne wyniki. Dlatego w zadaniach olimpijskich słowa składają się zwykle tylko z liter a–z.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
vector<int> v = {3, 1, 2};
sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
for (auto x : v) cout << x;
Pokaż odpowiedź
321Reguła „a przed b, gdy a większe” — malejąco.
Co wypisze ten fragment?
vector<int> v = {12, 5, 31, 24};
sort(v.begin(), v.end(), [](int a, int b) {
    return a % 10 < b % 10;
});
for (auto x : v) cout << x << " ";
Pokaż odpowiedź
31 12 24 5Ostatnie cyfry: 2, 5, 1, 4 — wszystkie różne, więc remisów nie ma. Kolejność: 1, 2, 4, 5.
Co wypisze ten fragment?
vector<int> v = {-3, 2, -1};
sort(v.begin(), v.end(), [](int a, int b) {
    if (abs(a) != abs(b)) return abs(a) < abs(b);
    return a < b;
});
for (auto x : v) cout << x << " ";
Pokaż odpowiedź
-1 2 -3Odległości od zera: 3, 2, 1.
Co wypisze ten fragment?
vector<string> s = {"ccc", "a", "bb"};
sort(s.begin(), s.end(), [](string a, string b) {
    return a.size() > b.size();
});
for (auto x : s) cout << x << " ";
Pokaż odpowiedź
ccc bb aZnak > — najdłuższe pierwsze.
Co wypisze ten fragment?
vector<int> v = {5, 2, 3, 4};
sort(v.begin(), v.end(), [](int a, int b) {
    bool pa = (a % 2 == 0), pb = (b % 2 == 0);
    if (pa != pb) return pa;
    return a < b;
});
for (auto x : v) cout << x;
Pokaż odpowiedź
2435Parzyste 2, 4 rosnąco, potem nieparzyste 3, 5 rosnąco.
Co wypisze ten fragment?
vector<int> v = {4, 9, 5};
sort(v.begin(), v.end(), [](int a, int b) {
    return a % 3 < b % 3;
});
for (auto x : v) cout << x;
Pokaż odpowiedź
945Reszty z dzielenia przez 3: 4 → 1, 9 → 0, 5 → 2.
Co wypisze ten fragment?
string s = "abc";
sort(s.begin(), s.end(), [](char a, char b) { return a > b; });
cout << s;
Pokaż odpowiedź
cbaReguła działa też dla liter napisu — typ to char.
Co wypisze ten fragment?
int k = 6;
vector<int> v = {1, 5, 9};
sort(v.begin(), v.end(), [&](int a, int b) {
    return abs(a - k) < abs(b - k);
});
for (auto x : v) cout << x << " ";
Pokaż odpowiedź
5 9 1Odległości od 6: 1 → 5, 5 → 1, 9 → 3. Bez & w nawiasach program by się nie skompilował.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Kilka kryteriów naraz: pary, sztuczka z minusem i stable_sort

Prawdziwe rankingi rzadko mają jedno kryterium. W konkursie wygrywa ten, kto ma więcej punktów, a przy remisie — ten, kto był szybszy. W dzienniku uczniowie stoją według nazwisk, a przy tych samych nazwiskach — według imion. W tej części ułożysz dane według dwóch i trzech kryteriów naraz.

Pary sortują się same

Przypomnienie z lekcji o parach: sort na vectorze par ustawia je najpierw według first, a przy remisie według second. To już są dwa kryteria — i nie trzeba pisać żadnej reguły. Wystarczy, że to, co ważniejsze, włożysz do first.

Pary (wiek, imię): najpierw według wieku, a osoby w tym samym wieku — alfabetycznie. Ani jednej linijki reguły.
pary_same.cpp
vector<pair<int, string>> p = {{12, "Ola"}, {11, "Jan"}, {12, "Ala"}, {10, "Ewa"}, {11, "Adam"}};
sort(p.begin(), p.end());
for (auto [wiek, imie] : p) cout << wiek << " " << imie << "\n";
▶ Wyjście
10 Ewa 11 Adam 11 Jan 12 Ala 12 Ola

Gdybyś chciał najpierw alfabetycznie, a przy tych samych imionach według wieku — zamieniłbyś kolejność w parze: pair<string, int>.

Zasada: główne kryterium na pierwsze miejsce. Wypisując, możesz pola ustawić w dowolnej kolejności.

Sztuczka z minusem

Ranking zawodów: więcej punktów wyżej (malejąco), a przy remisie krótszy czas wyżej (rosnąco). Pary porównują oba pola rosnąco, więc jak zrobić jedno malejąco? Sztuczka z lekcji o parach: zamiast punktów zapisz minus punkty. Rosnąco po −punktach to to samo co malejąco po punktach: −90 < −75 < −60. Przy wypisywaniu znowu zmieniasz znak.

minus.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> w(n);        // (-punkty, czas)
    for (auto &[mp, czas] : w) {
        int punkty;
        cin >> punkty >> czas;
        mp = -punkty;
    }
    sort(w.begin(), w.end());
    for (auto [mp, czas] : w) cout << -mp << " " << czas << "\n";
    return 0;
}
▶ Wejście
5 75 300 90 410 75 250 60 120 90 380
▶ Wyjście
90 380 90 410 75 250 75 300 60 120
Po sortowaniu: najpierw −90 (czyli 90 punktów), a dwie osoby z 90 — według czasu, krótszy wyżej.

Rozpakowanie z & w pętli wczytującej (auto &[mp, czas]) zapisuje wartości prosto do pary — znasz to z lekcji o parach.

Reguła dla par

Minus działa tylko dla liczb. A co, jeśli chcesz napisy w kolejności odwrotnej, albo para ma kryteria w „złej” kolejności, a nie chcesz jej przebudowywać? Wtedy piszesz regułę — dokładnie według wzoru z części 5. Para ma typ pair<string, int>, więc tak deklarujemy a i b. Żeby nie pisać długiego typu, można też użyć auto: [](auto a, auto b).

regula_par.cpp
vector<pair<string, int>> r = {{"Ola", 75}, {"Jan", 90}, {"Ala", 75}, {"Ewa", 60}, {"Adam", 90}};
sort(r.begin(), r.end(), [](pair<string, int> a, pair<string, int> b) {
    if (a.second != b.second) return a.second > b.second;  // więcej punktów wyżej
    return a.first < b.first;                              // remis: alfabetycznie
});
for (auto [imie, pkt] : r) cout << imie << " " << pkt << "\n";
▶ Wyjście
Adam 90 Jan 90 Ala 75 Ola 75 Ewa 60
regula_auto.cpp
vector<pair<string, int>> r = {{"Ola", 75}, {"Jan", 90}, {"Ala", 75}};
sort(r.begin(), r.end(), [](auto a, auto b) {
    if (a.second != b.second) return a.second > b.second;
    return a.first < b.first;
});
for (auto [imie, pkt] : r) cout << imie << " ";
cout << "\n";
▶ Wyjście
Jan Ala Ola

Ta sama reguła, krócej zapisana. auto w nawiasach lambdy znaczy „typ taki, jak elementy vectora”.

Trzy kryteria

Ranking olimpiady: więcej punktów wyżej; przy remisie mniej prób wyżej; przy remisie i w tym — alfabetycznie. Trzy pola trzymamy w parze par: pair<string, pair<int, int>>, czyli (imię, (punkty, próby)). Reguła ma teraz dwa ify i ostatni return — schodki, jak w słowniku.

trzy_kryteria.cpp
vector<pair<string, pair<int, int>>> z = {
    {"Ola", {300, 5}}, {"Jan", {300, 3}}, {"Ewa", {250, 1}},
    {"Ala", {300, 3}}, {"Igor", {250, 1}}
};
sort(z.begin(), z.end(), [](auto a, auto b) {
    if (a.second.first != b.second.first)
        return a.second.first > b.second.first;     // 1. punkty malejąco
    if (a.second.second != b.second.second)
        return a.second.second < b.second.second;   // 2. próby rosnąco
    return a.first < b.first;                       // 3. imię alfabetycznie
});
for (auto x : z)
    cout << x.first << " " << x.second.first << " " << x.second.second << "\n";
▶ Wyjście
Ala 300 3 Jan 300 3 Ola 300 5 Ewa 250 1 Igor 250 1

Ala i Jan remisują na punktach i na próbach — rozstrzyga alfabet. Ola ma tyle samo punktów, ale więcej prób, więc jest za nimi.

Zapis a.second.first szybko robi się nieczytelny. W części 7 poznasz wygodniejszy sposób: dane w kilku osobnych vectorach i sortowanie numerów.

stable_sort — remisy zostają w kolejności z wejścia

Pamiętasz z części 5: gdy reguła mówi „remis”, sort może ustawić takie elementy w dowolnej kolejności. Czasem jednak zadanie wymaga: „przy remisie zachowaj kolejność z wejścia”. Wtedy zamiast sort piszesz stable_sort — z tymi samymi argumentami. Stabilne sortowanie gwarantuje, że elementy równe dla reguły zostaną w takiej kolejności względem siebie, w jakiej były.

Przykład: lista uczniów w kolejności zapisów, każdy z numerem klasy. Chcemy pogrupować ich według klas, ale w każdej klasie zostawić kolejność zapisów. Reguła porównuje tylko klasy — a resztę załatwia stabilność.

stable_sort.cpp
vector<pair<string, int>> u = {{"Zosia", 2}, {"Adam", 1}, {"Ola", 2}, {"Bartek", 1}, {"Ala", 2}};
stable_sort(u.begin(), u.end(), [](auto a, auto b) {
    return a.second < b.second;      // tylko klasa!
});
for (auto [imie, klasa] : u) cout << klasa << " " << imie << "\n";
▶ Wyjście
1 Adam 1 Bartek 2 Zosia 2 Ola 2 Ala
W klasie 1 Adam przed Bartkiem, w klasie 2 Zosia, Ola, Ala — dokładnie w kolejności zapisów, choć alfabetycznie byłoby inaczej.
Dwa sposoby na „w kolejności z wejścia” Sposób 1: stable_sort z regułą, która porównuje tylko główne kryterium. Sposób 2: dopisz do danych numer z wejścia i użyj go jako ostatniego kryterium w regule — wtedy remisów w ogóle nie ma i wystarczy zwykłe sort. Oba dają ten sam wynik. Drugi sposób zobaczysz w części 7.

Punkty na płaszczyźnie

Punkty (x, y) to pary, więc sort bez reguły ustawi je „od lewej”: według x, a przy tym samym x — według y. Inne częste życzenie to sortowanie według odległości od początku układu (0, 0). Odległość to pierwiastek z x² + y², ale do porównywania pierwiastek nie jest potrzebny: większa odległość to większe x² + y². Liczymy więc same kwadraty — na liczbach całkowitych, bez błędów zaokrągleń.

punkty.cpp
vector<pair<int, int>> p = {{3, 4}, {-1, 1}, {0, 2}, {-5, 0}, {1, -1}};
sort(p.begin(), p.end(), [](auto a, auto b) {
    long long da = 1LL * a.first * a.first + 1LL * a.second * a.second;
    long long db = 1LL * b.first * b.first + 1LL * b.second * b.second;
    if (da != db) return da < db;
    return a < b;                 // remis: zwykłe porównanie par
});
for (auto [x, y] : p) cout << "(" << x << "," << y << ") ";
cout << "\n";
▶ Wyjście
(-1,1) (1,-1) (0,2) (-5,0) (3,4)

Kwadraty odległości: (3, 4) → 25, (−1, 1) → 2, (0, 2) → 4, (−5, 0) → 25, (1, −1) → 2.

Remisy rozstrzyga a < b — porównanie całych par, które już znasz: (−1, 1) przed (1, −1), bo −1 < 1; a (−5, 0) przed (3, 4).

1LL * zamienia mnożenie na long long: dla współrzędnych do miliarda sam kwadrat ma 18 cyfr i nie mieści się w int.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
vector<pair<int, int>> p = {{2, 1}, {1, 5}, {2, 0}};
sort(p.begin(), p.end());
for (auto [a, b] : p) cout << a << b << " ";
Pokaż odpowiedź
15 20 21Najpierw według first (1 przed 2), a pary (2, 1) i (2, 0) według second.
Co wypisze ten fragment?
vector<pair<int, int>> p = {{-5, 30}, {-7, 40}, {-5, 20}};
sort(p.begin(), p.end());
for (auto [a, b] : p) cout << -a << ":" << b << " ";
Pokaż odpowiedź
7:40 5:20 5:30Sztuczka z minusem: −7 jest najmniejsze, więc 7 punktów na górze. Przy 5 punktach — krótszy czas wyżej.
Co wypisze ten fragment?
vector<pair<string, int>> r = {{"a", 1}, {"b", 3}, {"c", 2}};
sort(r.begin(), r.end(), [](auto x, auto y) {
    return x.second > y.second;
});
for (auto [s, k] : r) cout << s;
Pokaż odpowiedź
bcaWedług second malejąco: 3, 2, 1.
Co wypisze ten fragment?
vector<pair<int, char>> p = {{2, 'x'}, {1, 'y'}, {2, 'z'}, {1, 'w'}};
stable_sort(p.begin(), p.end(), [](auto a, auto b) {
    return a.first < b.first;
});
for (auto [k, c] : p) cout << c;
Pokaż odpowiedź
ywxzReguła patrzy tylko na first; wśród jedynek zostaje kolejność z wejścia (y przed w), wśród dwójek też (x przed z).
Co wypisze ten fragment?
vector<pair<int, char>> p = {{2, 'x'}, {1, 'y'}, {2, 'z'}, {1, 'w'}};
sort(p.begin(), p.end());
for (auto [k, c] : p) cout << c;
Pokaż odpowiedź
wyxzBez reguły porównujemy całe pary: przy first = 1 decyduje znak, a 'w' < 'y'.
Co wypisze ten fragment?
vector<pair<int, int>> p = {{3, 4}, {1, 1}, {0, 2}};
sort(p.begin(), p.end(), [](auto a, auto b) {
    return a.first * a.first + a.second * a.second
         < b.first * b.first + b.second * b.second;
});
for (auto [x, y] : p) cout << x << y << " ";
Pokaż odpowiedź
11 02 34Kwadraty odległości: 25, 2, 4.
Co wypisze ten fragment?
vector<pair<string, int>> v = {{"Ola", 5}, {"Ala", 9}, {"Ola", 3}};
sort(v.begin(), v.end());
for (auto [s, k] : v) cout << s << k << " ";
Pokaż odpowiedź
Ala9 Ola3 Ola5Najpierw według imienia, a dwie Ole — według liczby.
Co wypisze ten fragment?
vector<pair<int, int>> p = {{1, 2}, {1, 5}, {0, 9}};
sort(p.begin(), p.end(), [](auto a, auto b) {
    if (a.first != b.first) return a.first > b.first;
    return a.second > b.second;
});
for (auto [x, y] : p) cout << x << y << " ";
Pokaż odpowiedź
15 12 09Oba kryteria malejąco: najpierw first (1 przed 0), przy remisie second (5 przed 2).
Ćwiczenia · teraz Ty

7 ćwiczeń do tej części

0 / 7 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Sortujemy numery zamiast wartości: rekordy i miejsca w rankingu

Sortowanie ma jedną wadę: po nim nie wiadomo, kto był kim. Gdy posortujesz wzrost uczniów, dostaniesz ładny rząd liczb — ale czyj jest wzrost 152? W tej części poznasz sposób, który rozwiązuje ten problem raz na zawsze: zamiast wartości sortujemy numery. Przy okazji nauczysz się układać dane z wieloma polami i liczyć miejsca w rankingu z remisami.

Problem: kto jest kim?

Uczniowie stoją w kolejce, każdy ma swój numer 0, 1, 2, 3, a w vectorze w zapisaliśmy ich wzrost. Chcemy wiedzieć, kto jest najniższy, kto drugi… — czyli numery uczniów w kolejności od najniższego. Sposób z lekcji o parach: pary (wzrost, numer) i sort. Działa, ale przy wielu polach robi się nieczytelnie. Jest lepszy sposób.

Sortujemy numery, porównujemy wartości

Robimy vector numerów nr = {0, 1, 2, …, n − 1} i sortujemy ten vector — ale z regułą, która porównuje numery według wzrostu: „numer a stoi przed numerem b, gdy uczeń a jest niższy od ucznia b”, czyli w[a] < w[b]. Reguła musi widzieć vector w, więc ma [&]. Sam vector w się nie zmienia — przestawiają się tylko numery.

sortuj_numery.cpp
vector<int> w = {150, 142, 160, 138};
int n = w.size();
vector<int> nr(n);
for (int i = 0; i < n; i++) nr[i] = i;     // 0 1 2 3
sort(nr.begin(), nr.end(), [&](int a, int b) {
    return w[a] < w[b];
});
for (auto i : nr) cout << i << " ";
cout << "\n";
for (auto i : nr) cout << w[i] << " ";
cout << "\n";
▶ Wyjście
3 1 0 2 138 142 150 160
Najniższy jest uczeń 3 (138 cm), potem uczeń 1 (142), uczeń 0 (150) i uczeń 2 (160). Vector w wygląda tak samo jak przed sortowaniem.

Jak czytać wynik? nr[0] to numer najniższego ucznia, nr[1] — drugiego, i tak dalej. Wzrost k-tego w kolejności to w[nr[k]] — dwa nawiasy, jak w lekcji o vectorze przy permutacjach. W drugim wierszu wyniku wypisaliśmy wzrosty w kolejności numerów — wyszły posortowane, a w nadal jest nietknięty.

Schemat: sortowanie numerów vector<int> nr(n); for (int i = 0; i < n; i++) nr[i] = i; a potem sort(nr.begin(), nr.end(), [&](int a, int b) { return w[a] < w[b]; });. a i b to numery, a porównujemy wartości pod tymi numerami.

Remis rozstrzyga numer

Gdy dwóch uczniów ma ten sam wzrost, reguła w[a] < w[b] mówi „remis” i sort może ich ustawić dowolnie. Najczęściej zadanie chce wtedy kolejności z wejścia — czyli mniejszy numer wcześniej. Dopisujemy więc drugie kryterium: return a < b;. To jest ten „sposób 2” z części 6 — zamiast stable_sort.

remis_numer.cpp
vector<int> w = {150, 142, 150, 138, 142};
int n = w.size();
vector<int> nr(n);
for (int i = 0; i < n; i++) nr[i] = i;
sort(nr.begin(), nr.end(), [&](int a, int b) {
    if (w[a] != w[b]) return w[a] < w[b];
    return a < b;                    // ten sam wzrost — kolejność z kolejki
});
for (auto i : nr) cout << i << "(" << w[i] << ") ";
cout << "\n";
▶ Wyjście
3(138) 1(142) 4(142) 0(150) 2(150)

Uczniowie 1 i 4 mają po 142 cm — pierwszy jest 1, bo stał wcześniej. Tak samo 0 przed 2 przy 150 cm.

Rekordy w kilku vectorach

Teraz prawdziwy pożytek. Zawodnik ma imię, punkty i czas. Zamiast pakować to w pary par, trzymamy trzy osobne vectory: imie[i], pkt[i], czas[i] — wszystkie trzy pod numerem i opisują tego samego zawodnika. Taki zestaw nazywa się rekordem. Sortujemy numery z regułą o trzech kryteriach, a wypisujemy przez imie[nr[k]].

rekordy.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<string> imie(n);
    vector<int> pkt(n), czas(n);
    for (int i = 0; i < n; i++) cin >> imie[i] >> pkt[i] >> czas[i];

    vector<int> nr(n);
    for (int i = 0; i < n; i++) nr[i] = i;
    sort(nr.begin(), nr.end(), [&](int a, int b) {
        if (pkt[a] != pkt[b]) return pkt[a] > pkt[b];      // więcej punktów
        if (czas[a] != czas[b]) return czas[a] < czas[b];  // krótszy czas
        return imie[a] < imie[b];                          // alfabet
    });
    for (int k = 0; k < n; k++) {
        int i = nr[k];
        cout << k + 1 << ". " << imie[i] << " " << pkt[i] << " " << czas[i] << "\n";
    }
    return 0;
}
▶ Wejście
5 Ola 300 95 Jan 300 80 Ewa 250 60 Ala 300 80 Igor 280 70
▶ Wyjście
1. Ala 300 80 2. Jan 300 80 3. Ola 300 95 4. Igor 280 70 5. Ewa 250 60

Porównaj z przykładem z części 6: reguła jest ta sama, ale zamiast a.second.first piszesz pkt[a]. Od razu widać, co porównujemy.

W pętli wypisującej najpierw zapisujemy int i = nr[k]; — numer zawodnika, który zajął miejsce k + 1. Dalej używamy już tylko i.

Ten sposób działa dla dowolnie wielu pól: dopisujesz kolejny vector i kolejny if w regule.

Miejsce każdego zawodnika — z remisami

Odwrotne pytanie: nie „kto jest k-ty”, tylko „które miejsce zajął zawodnik i”. W sporcie przy remisie zawodnicy dzielą miejsce (ex aequo), a następne miejsce jest pomijane: wyniki 90, 85, 85, 70 dają miejsca 1, 2, 2, 4. Algorytm: sortujemy numery malejąco według punktów i idziemy po kolei. Zawodnik na pozycji k dostaje miejsce k + 1 — chyba że ma tyle samo punktów co poprzedni; wtedy dostaje to samo miejsce co poprzedni. Miejsca zapisujemy w vectorze miejsce[i] pod numerem zawodnika, więc na koniec możemy je wypisać w kolejności z wejścia.

miejsca.cpp
vector<int> pkt = {70, 85, 90, 85, 60, 90};
int n = pkt.size();
vector<int> nr(n);
for (int i = 0; i < n; i++) nr[i] = i;
sort(nr.begin(), nr.end(), [&](int a, int b) {
    if (pkt[a] != pkt[b]) return pkt[a] > pkt[b];
    return a < b;
});
vector<int> miejsce(n);
for (int k = 0; k < n; k++) {
    int i = nr[k];
    if (k > 0 && pkt[i] == pkt[nr[k - 1]]) miejsce[i] = miejsce[nr[k - 1]];
    else miejsce[i] = k + 1;
}
for (int i = 0; i < n; i++) cout << miejsce[i] << " ";
cout << "\n";
▶ Wyjście
5 3 1 3 6 1
knr[k]punktyjak poprzedni?miejsce
0290—1
1590tak1
2185nie3
3385tak3
4070nie5
5460nie6

Po dwóch zwycięzcach ex aequo następne miejsce to 3, a nie 2 — miejsce 2 „zużyli” obaj zwycięzcy razem.

Kompresja: numery zamiast wielkich liczb

Ostatnia sztuczka tej części jest bardzo olimpijska. Masz liczby 1000, 5, 1 000 000, 5, 70. Chciałbyś użyć tablicy liczników, ale liczby są ogromne. Ważna jest jednak tylko ich kolejność, nie wielkość. Zamieniamy więc każdą liczbę na jej numer wśród różnych wartości: najmniejsza dostaje 1, następna 2… Wynik: 3, 1, 4, 1, 2. Teraz wszystkie liczby są małe (najwyżej n) i tablica liczników znowu działa. Ta sztuczka nazywa się kompresją (albo przenumerowaniem).

kompresja.cpp
vector<int> v = {1000, 5, 1000000, 5, 70};
int n = v.size();
vector<int> nr(n);
for (int i = 0; i < n; i++) nr[i] = i;
sort(nr.begin(), nr.end(), [&](int a, int b) { return v[a] < v[b]; });
vector<int> kod(n);
int numer = 0;
for (int k = 0; k < n; k++) {
    if (k == 0 || v[nr[k]] != v[nr[k - 1]]) numer++;   // nowa wartość
    kod[nr[k]] = numer;
}
for (auto x : kod) cout << x << " ";
cout << "\n";
▶ Wyjście
3 1 4 1 2
Różne wartości po kolei: 5 → 1, 70 → 2, 1000 → 3, 1 000 000 → 4. Obie piątki dostały ten sam numer. Kolejność się zgadza: jeśli v[i] < v[j], to kod[i] < kod[j].

Zauważ, że to ten sam schemat co liczenie różnych wartości w części 3: numer rośnie, gdy wartość różni się od poprzedniej. Tyle że teraz idziemy po numerach, więc wiemy, komu ten numer przypisać.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
vector<int> w = {5, 9, 1};
vector<int> nr = {0, 1, 2};
sort(nr.begin(), nr.end(), [&](int a, int b) { return w[a] < w[b]; });
for (auto i : nr) cout << i;
Pokaż odpowiedź
201Najmniejsza wartość (1) stoi pod numerem 2, potem 5 (numer 0), potem 9 (numer 1).
Co wypisze ten fragment?
vector<int> w = {5, 9, 1};
vector<int> nr = {0, 1, 2};
sort(nr.begin(), nr.end(), [&](int a, int b) { return w[a] > w[b]; });
for (auto i : nr) cout << i;
Pokaż odpowiedź
102Malejąco według wartości: 9 (numer 1), 5 (numer 0), 1 (numer 2).
Co wypisze ten fragment?
vector<int> w = {4, 4, 1};
vector<int> nr = {0, 1, 2};
sort(nr.begin(), nr.end(), [&](int a, int b) {
    if (w[a] != w[b]) return w[a] < w[b];
    return a < b;
});
for (auto i : nr) cout << i;
Pokaż odpowiedź
201Remis czwórek rozstrzyga numer: 0 przed 1.
Co wypisze ten fragment?
vector<int> w = {7, 3, 8};
vector<int> nr = {2, 0, 1};
cout << w[nr[0]] << " " << w[nr[2]];
Pokaż odpowiedź
8 3nr[0] = 2, więc w[2] = 8; nr[2] = 1, więc w[1] = 3.
Jakie miejsca wypisze ten fragment?
vector<int> p = {10, 30, 20, 30};
vector<int> nr = {1, 3, 2, 0};       // już posortowane malejąco
vector<int> m(4);
for (int k = 0; k < 4; k++) {
    int i = nr[k];
    if (k > 0 && p[i] == p[nr[k - 1]]) m[i] = m[nr[k - 1]];
    else m[i] = k + 1;
}
for (auto x : m) cout << x << " ";
Pokaż odpowiedź
4 1 3 1Dwie trzydziestki dzielą miejsce 1, potem 20 jest trzecia, a 10 czwarta. Wypisujemy w kolejności z wejścia.
Co wypisze ten fragment?
vector<int> v = {7, 3, 7, 10};
vector<int> nr = {1, 0, 2, 3};       // numery posortowane według v
vector<int> kod(4);
int c = 0;
for (int k = 0; k < 4; k++) {
    if (k == 0 || v[nr[k]] != v[nr[k - 1]]) c++;
    kod[nr[k]] = c;
}
for (auto x : kod) cout << x;
Pokaż odpowiedź
21233 → 1, 7 → 2 (obie siódemki), 10 → 3.
Co wypisze ten fragment?
vector<string> s = {"kot", "a", "mysz"};
vector<int> nr = {0, 1, 2};
sort(nr.begin(), nr.end(), [&](int a, int b) {
    return s[a].size() < s[b].size();
});
for (auto i : nr) cout << i;
Pokaż odpowiedź
102Długości: 3, 1, 4. Najkrótsze jest słowo numer 1.
Co wypisze ten fragment?
vector<int> w = {170, 165, 180};
vector<int> nr = {0, 1, 2};
sort(nr.begin(), nr.end(), [&](int a, int b) { return w[a] > w[b]; });
cout << nr[1] << " " << w[nr[1]];
Pokaż odpowiedź
0 170Malejąco: numer 2 (180), numer 0 (170), numer 1 (165). Drugi w kolejności to uczeń 0.
Ćwiczenia · teraz Ty

7 ćwiczeń do tej części

0 / 7 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Szukanie przez połowienie: lower_bound i upper_bound

W nieposortowanym vectorze, żeby sprawdzić, czy jest w nim liczba x, trzeba obejrzeć wszystkie elementy — tak działa find. W posortowanym da się to zrobić niesamowicie szybciej: w milionie liczb wystarczy zajrzeć do około 20 pudełek. W tej części poznasz pomysł połowienia i gotowe polecenia, które z niego korzystają.

Zabawa: zgadnij liczbę od 1 do 100

Ktoś pomyślał liczbę od 1 do 100. Możesz pytać „czy to x?”, a on odpowiada „tak”, „więcej” albo „mniej”. Jak zgadnąć jak najszybciej? Pytaj zawsze o środek przedziału, w którym może być liczba. Każda odpowiedź „więcej” albo „mniej” wyrzuca połowę możliwości: 100 → 50 → 25 → 12 → 6 → 3 → 1. Najwyżej 7 pytań! Strzelając po kolei 1, 2, 3, … mógłbyś potrzebować aż 100.

pytanieprzedziałśrodekodpowiedź (myślimy 71)
11 … 10050więcej
251 … 10075mniej
351 … 7462więcej
463 … 7468więcej
569 … 7471tak!

Wyszukiwanie binarne w vectorze

Ten sam pomysł działa w posortowanym vectorze. Pilnujemy przedziału numerów od l do r, w którym może stać x. Patrzymy na środek s = (l + r) / 2. Jeśli v[s] == x — znaleźliśmy. Jeśli v[s] < x — x może stać tylko na prawo od s (bo na lewo są jeszcze mniejsze liczby), więc l = s + 1. W przeciwnym razie r = s − 1. Gdy przedział zrobi się pusty (l > r), x nie ma. Nazwa: wyszukiwanie binarne (binarne — bo za każdym razem dzielimy na dwie części).

binarne.cpp
vector<int> v = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int x = 23;
int l = 0, r = v.size() - 1;
bool jest = false;
while (l <= r) {
    int s = (l + r) / 2;
    cout << "l=" << l << " r=" << r << " s=" << s << " v[s]=" << v[s] << "\n";
    if (v[s] == x) { jest = true; break; }
    if (v[s] < x) l = s + 1;       // x może być tylko na prawo
    else r = s - 1;                // x może być tylko na lewo
}
cout << (jest ? "jest" : "nie ma") << "\n";
▶ Wyjście
l=0 r=9 s=4 v[s]=16 l=5 r=9 s=7 v[s]=56 l=5 r=6 s=5 v[s]=23 jest
Krok 1: 16 < 23, więc lewa połowa (szara) odpada. Krok 2: 56 > 23, odpada prawa część. Krok 3: trafiony. Trzy zajrzenia zamiast sześciu.

Ile kroków najwyżej? Tyle, ile razy da się podzielić n na pół, zanim zostanie jedno pudełko. Dla tysiąca liczb — 10, dla miliona — 20, dla miliarda — 30. To jest właśnie log2n z części 4.

Tylko na posortowanym! Cały pomysł opiera się na tym, że na lewo od środka są mniejsze liczby, a na prawo — większe. Na nieposortowanych danych wyszukiwanie binarne (i wszystkie polecenia z tej części) dadzą bzdurną odpowiedź — bez żadnego błędu ani ostrzeżenia. Najpierw sort!

binary_search — jest czy nie ma?

Nie musisz pisać tej pętli za każdym razem. binary_search(v.begin(), v.end(), x) robi dokładnie to samo i zwraca true albo false. Przydaje się, gdy pytań jest dużo: sortujesz raz, a potem odpowiadasz na każde pytanie w kilkunastu krokach.

binary_search.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> v(n);
    for (auto &x : v) cin >> x;
    sort(v.begin(), v.end());              // raz
    while (q--) {
        int x;
        cin >> x;
        if (binary_search(v.begin(), v.end(), x)) cout << "TAK\n";
        else cout << "NIE\n";
    }
    return 0;
}
▶ Wejście
6 4 40 7 22 31 12 60 22 23 60 1
▶ Wyjście
TAK NIE TAK NIE

while (q--) to skrót: pętla wykona się q razy (q zmniejsza się po każdym sprawdzeniu, aż dojdzie do zera).

Dlaczego to takie ważne? Przy n = 100 000 liczb i q = 100 000 pytań, przeglądanie całego vectora przy każdym pytaniu to 10 miliardów kroków. Sortowanie i połowienie to kilka milionów.

lower_bound — pierwsze miejsce, gdzie x by pasował

binary_search mówi tylko „jest” albo „nie ma”. Często chcemy wiedzieć więcej: gdzie stoi x i ile jest liczb mniejszych od niego. Do tego służy lower_bound(v.begin(), v.end(), x). Zwraca strzałkę na pierwszy element, który jest ≥ x — czyli na pierwsze miejsce, w które dałoby się wstawić x, nie psując porządku. Jeśli wszystkie elementy są mniejsze od x, zwraca end().

Jak z każdej strzałki, numer dostajesz, odejmując v.begin(). I tu jest piękna rzecz: ten numer to jednocześnie liczba elementów mniejszych od x — bo wszystkie stoją na lewo od tego miejsca.

lower_bound(4) pokazuje pierwszą czwórkę (numer 1) — mniejszych od 4 jest 1. lower_bound(5) pokazuje siódemkę (numer 4) — tam stanęłaby piątka; mniejszych od 5 jest 4. lower_bound(10) to end() (numer 6) — wszystkie są mniejsze.

upper_bound — pierwsze miejsce ZA wszystkimi x

Brat bliźniak: upper_bound(v.begin(), v.end(), x) zwraca strzałkę na pierwszy element, który jest > x (ściśle większy). Czyli przeskakuje wszystkie elementy równe x. Numer tego miejsca to liczba elementów ≤ x.

Wszystkie czwórki leżą między lower_bound(4) (numer 1, wliczamy) a upper_bound(4) (numer 4, nie wliczamy). Czwórek jest 4 − 1 = 3.
bounds.cpp
vector<int> v = {2, 4, 4, 4, 7, 9};
for (int x : {4, 5, 1, 10}) {
    int lo = lower_bound(v.begin(), v.end(), x) - v.begin();
    int up = upper_bound(v.begin(), v.end(), x) - v.begin();
    cout << "x=" << x << ": mniejszych " << lo
         << ", co najwyzej x " << up
         << ", rownych " << up - lo << "\n";
}
▶ Wyjście
x=4: mniejszych 1, co najwyzej x 4, rownych 3 x=5: mniejszych 4, co najwyzej x 4, rownych 0 x=1: mniejszych 0, co najwyzej x 0, rownych 0 x=10: mniejszych 6, co najwyzej x 6, rownych 0

Pętla for (int x : {4, 5, 1, 10}) to wygodny sposób, żeby sprawdzić kilka wartości po kolei — pętla „dla każdego” po liście w klamrach.

Gdy x nie ma w vectorze (5, 1, 10), obie strzałki pokazują to samo miejsce — i różnica wynosi 0.

Ściąga: liczenie jednym odejmowaniem

Wszystkie te wzory zakładają, że v jest posortowany rosnąco. Dla wygody oznaczmy L(x) = lower_bound(v.begin(), v.end(), x) - v.begin() i U(x) = upper_bound(v.begin(), v.end(), x) - v.begin():

pytanieodpowiedźdla v = 2 4 4 4 7 9
ile elementów < xL(x)x = 7: 4
ile elementów ≤ xU(x)x = 7: 5
ile elementów == xU(x) - L(x)x = 4: 3
ile elementów > xn - U(x)x = 4: 2
ile elementów ≥ xn - L(x)x = 4: 5
ile elementów w przedziale [a, b]U(b) - L(a)[3, 8]: 4
przedzial.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> v(n);
    for (auto &x : v) cin >> x;
    sort(v.begin(), v.end());
    while (q--) {
        int a, b;
        cin >> a >> b;
        int ile = upper_bound(v.begin(), v.end(), b) - lower_bound(v.begin(), v.end(), a);
        cout << ile << "\n";
    }
    return 0;
}
▶ Wejście
7 3 15 3 9 27 9 20 1 5 15 10 14 0 100
▶ Wyjście
3 0 7

Po sortowaniu: 1 3 9 9 15 20 27. W przedziale [5, 15] leżą 9, 9 i 15 — trzy liczby (końce przedziału się liczą). W [10, 14] nie ma żadnej. W [0, 100] — wszystkie.

Różnica dwóch strzałek to od razu liczba — nie trzeba odejmować v.begin() osobno od każdej.

Najbliższa wartość

Masz cennik (posortowany) i chcesz znaleźć cenę najbliższą x. lower_bound(x) pokazuje najmniejszą cenę ≥ x — to jeden kandydat. Drugi kandydat stoi tuż przed nim: największa cena < x. Trzeba porównać obu (uważając, żeby nie wyjść poza vector).

najblizsza.cpp
vector<int> c = {10, 25, 40, 60, 95};
for (int x : {30, 34, 5, 120}) {
    int i = lower_bound(c.begin(), c.end(), x) - c.begin();
    int najlepsza;
    if (i == (int)c.size()) najlepsza = c[i - 1];      // wszystkie mniejsze
    else if (i == 0) najlepsza = c[0];                 // wszystkie większe
    else if (x - c[i - 1] <= c[i] - x) najlepsza = c[i - 1];
    else najlepsza = c[i];
    cout << x << " -> " << najlepsza << "\n";
}
▶ Wyjście
30 -> 25 34 -> 40 5 -> 10 120 -> 95

Dla x = 30: lower_bound pokazuje 40 (numer 2), a przed nim stoi 25. Odległości: 5 i 10 — wygrywa 25.

Znak <= w porównaniu odległości sprawia, że przy remisie (np. x = 50: 40 i 60) wybieramy tańszą cenę.

Dwa brzegi trzeba obsłużyć osobno: gdy i = 0, przed nim nikogo nie ma; gdy i = n, c[i] nie istnieje.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
vector<int> v = {1, 3, 5, 7};
cout << lower_bound(v.begin(), v.end(), 4) - v.begin();
Pokaż odpowiedź
2Pierwszy element ≥ 4 to 5 (numer 2). Mniejsze od 4 są dwa: 1 i 3.
Co wypisze ten fragment?
vector<int> v = {1, 3, 5, 7};
cout << upper_bound(v.begin(), v.end(), 5) - v.begin();
Pokaż odpowiedź
3Pierwszy element > 5 to 7 (numer 3). Elementów ≤ 5 jest trzy.
Co wypisze ten fragment?
vector<int> v = {2, 4, 4, 4, 7};
cout << upper_bound(v.begin(), v.end(), 4) - lower_bound(v.begin(), v.end(), 4);
Pokaż odpowiedź
3Liczba czwórek: 4 − 1.
Co wypisze ten fragment?
vector<int> v = {1, 3, 5, 7};
cout << binary_search(v.begin(), v.end(), 6);
Pokaż odpowiedź
0Szóstki nie ma — false wypisuje się jako 0.
Co wypisze ten fragment?
vector<int> v = {1, 3, 5, 7};
cout << lower_bound(v.begin(), v.end(), 10) - v.begin();
Pokaż odpowiedź
4Wszystkie elementy są mniejsze od 10, więc dostajemy end() — numer 4, czyli rozmiar vectora.
Co wypisze ten fragment?
vector<int> v = {1, 3, 5, 7};
cout << upper_bound(v.begin(), v.end(), 6) - lower_bound(v.begin(), v.end(), 3);
Pokaż odpowiedź
2Liczby z przedziału [3, 6]: 3 i 5.
Co wypisze ten fragment?
vector<int> v = {1, 3, 5, 7};
cout << *lower_bound(v.begin(), v.end(), 4);
Pokaż odpowiedź
5Gwiazdka daje wartość pod strzałką: najmniejszy element ≥ 4.
Ile razy wykona się pętla?
vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8};
int x = 1, l = 0, r = 7, kroki = 0;
while (l <= r) {
    kroki++;
    int s = (l + r) / 2;
    if (v[s] == x) break;
    if (v[s] < x) l = s + 1;
    else r = s - 1;
}
cout << kroki;
Pokaż odpowiedź
3Środki: s = 3 (4 > 1), s = 1 (2 > 1), s = 0 — trafione.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Najpierw posortuj, potem bierz po kolei: pomysły zachłanne

Wiele zadań olimpijskich rozwiązuje się według tego samego przepisu: posortuj dane w odpowiedniej kolejności, a potem bierz po kolei to, co w danej chwili wygląda najlepiej. Taki sposób myślenia nazywa się zachłannym — jak ktoś zachłanny, bierzemy od razu najlepszy kąsek i nigdy nie wracamy do wcześniejszych decyzji. Znasz już jeden przykład z lekcji o parach: wybór jak największej liczby wykładów. W tej części poznasz kolejne.

Jak najwięcej rzeczy za budżet

Masz B złotych i listę cen prezentów. Chcesz kupić jak najwięcej prezentów (każdy co najwyżej raz). Pomysł: kupuj od najtańszych, dopóki starcza pieniędzy. Dlaczego to najlepsze? Załóżmy, że ktoś kupił jakiś drogi prezent, a pominął tańszy. Gdyby zamienił drogi na tańszy, miałby tyle samo prezentów i więcej pieniędzy. Zatem zawsze opłaca się brać najtańsze.

budzet.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long budzet;
    cin >> n >> budzet;
    vector<int> c(n);
    for (auto &x : c) cin >> x;
    sort(c.begin(), c.end());               // od najtańszego
    int ile = 0;
    long long wydane = 0;
    for (auto x : c) {
        if (wydane + x > budzet) break;     // na ten już nie stać
        wydane += x;
        ile++;
    }
    cout << ile << " " << wydane << "\n";
    return 0;
}
▶ Wejście
6 50 20 7 35 12 9 15
▶ Wyjście
4 43

Po sortowaniu: 7 9 12 15 20 35. Kupujemy 7, 9, 12 i 15 (razem 43). Na 20 już nie starcza (43 + 20 = 63 > 50), a skoro nie stać nas na 20, to na droższe 35 tym bardziej — dlatego break.

Argument zamiany Tak sprawdzasz, czy pomysł zachłanny jest dobry: weź dowolne inne rozwiązanie i pokaż, że jeśli różni się od zachłannego, to zamiana jednego elementu na „zachłanny” niczego nie psuje. Jeśli tak — zachłanność jest optymalna. Jeśli nie umiesz tego pokazać, sprawdź pomysł na małych przykładach, rozwiązując je ręcznie.

Kolejka do kasy: kto pierwszy?

Do jednej kasy przyszło jednocześnie n klientów. Obsługa klienta trwa ti minut. Każdy klient czeka, aż skończy się jego obsługa. W jakiej kolejności obsługiwać, żeby suma czasów czekania wszystkich klientów była najmniejsza? Odpowiedź: od najkrótszego. Krótka obsługa na początku opóźnia wszystkich za nią tylko trochę, a długa — bardzo.

kolejnośćklienci kończą posuma czekania
5, 1, 35, 6, 920
3, 5, 13, 8, 920
1, 3, 5 (od najkrótszego)1, 4, 914 ← najmniej
5, 3, 1 (od najdłuższego)5, 8, 922 ← najwięcej
kolejka.cpp
vector<int> t = {5, 1, 3, 2, 8};
sort(t.begin(), t.end());          // 1 2 3 5 8
long long zegar = 0, suma = 0;
for (auto x : t) {
    zegar += x;                    // ten klient kończy w chwili zegar
    suma += zegar;
}
cout << suma << "\n";
▶ Wyjście
40

Klienci kończą po 1, 3, 6, 11 i 19 minutach: 1 + 3 + 6 + 11 + 19 = 40.

Zmienna zegar to suma prefiksowa z lekcji o vectorze — czas, który upłynął do końca obsługi bieżącego klienta.

Łódki: najcięższy z najlżejszym

Ludzie przepływają rzekę łódkami. Łódka mieści najwyżej dwie osoby o łącznej wadze najwyżej L. Ile najmniej łódek potrzeba? Pomysł: posortuj wagi i ustaw dwa wskaźniki — i na najlżejszej osobie, j na najcięższej. Najcięższy i tak musi czymś popłynąć. Jeśli zmieści się z najlżejszym — płyną razem (i++, j--). Jeśli nie — najcięższy nie zmieści się z nikim, więc płynie sam (j--). W obu przypadkach zużyliśmy jedną łódkę.

lodki.cpp
vector<int> w = {70, 50, 80, 30, 60, 90};
int L = 120;
sort(w.begin(), w.end());           // 30 50 60 70 80 90
int i = 0, j = w.size() - 1, lodek = 0;
while (i <= j) {
    if (i < j && w[i] + w[j] <= L) {
        cout << w[i] << "+" << w[j] << " ";
        i++;
    } else {
        cout << w[j] << " ";
    }
    j--;
    lodek++;
}
cout << "\n" << lodek << "\n";
▶ Wyjście
30+90 80 50+70 60 4
Pierwsza łódka: najlżejszy (30) z najcięższym (90) — razem 120, mieszczą się.
łódkaw[i]w[j]razem ≤ 120?płynie
13090120 tak30 i 90
25080130 nie80 sam
35070120 tak50 i 70
46060i == j60 sam

W łódce 2 najcięższy z pozostałych (80) nie mieści się nawet z najlżejszym (50) — więc z nikim się nie zmieści i płynie sam. W łódce 4 wskaźniki spotkały się na jednej osobie (i == j) — ona też płynie sama. Warunek i < j w ifie pilnuje, żeby nie posadzić osoby „samej ze sobą”.

Mnożenie w parach: największy z największym

Masz dwie listy po n liczb (nieujemnych): a — ile sztuk każdego produktu możesz sprzedać, b — ceny, jakie dają różni kupcy. Każdy produkt sprzedajesz innemu kupcowi. Jak połączyć je w pary, żeby zarobić jak najwięcej (suma iloczynów)? Intuicja: najwięcej sztuk sprzedaj najlepiej płacącemu. Po sortowaniu obu list rosnąco łączymy a[i] z b[i] — największy z największym. A żeby wyszło najmniej, jedną listę sortujemy rosnąco, a drugą malejąco.

iloczyny.cpp
vector<long long> a = {3, 1, 2};
vector<long long> b = {10, 30, 20};
sort(a.begin(), a.end());          // 1 2 3
sort(b.begin(), b.end());          // 10 20 30
long long maks = 0, mini = 0;
int n = a.size();
for (int i = 0; i < n; i++) {
    maks += a[i] * b[i];           // największy z największym
    mini += a[i] * b[n - 1 - i];   // największy z najmniejszym
}
cout << maks << " " << mini << "\n";
▶ Wyjście
140 100

Najwięcej: 1·10 + 2·20 + 3·30 = 140. Najmniej: 1·30 + 2·20 + 3·10 = 100.

Argument zamiany: jeśli gdzieś mniejsze a stoi z większym b, a większe a z mniejszym b, to zamiana tych dwóch b nie zmniejsza sumy. Sprawdź na liczbach: 1·30 + 3·10 = 60, a po zamianie 1·10 + 3·30 = 100.

Dwie posortowane listy: ciastka dla dzieci

Każde dziecko ma apetyt — minimalny rozmiar ciastka, które je zadowoli. Masz ciastka różnej wielkości; każde dziecko dostaje najwyżej jedno ciastko. Ile najwięcej dzieci zadowolisz? Sortujemy obie listy. Idziemy po ciastkach od najmniejszego: jeśli bieżące ciastko zadowala dziecko z najmniejszym apetytem spośród niezadowolonych — dajemy je; jeśli nie — to ciastko jest za małe dla wszystkich pozostałych dzieci, więc je pomijamy.

ciastka.cpp
vector<int> apetyt = {5, 2, 8, 3};
vector<int> ciastko = {4, 1, 3, 9, 2};
sort(apetyt.begin(), apetyt.end());     // 2 3 5 8
sort(ciastko.begin(), ciastko.end());   // 1 2 3 4 9
int d = 0;                              // pierwsze niezadowolone dziecko
for (auto c : ciastko) {
    if (d < (int)apetyt.size() && c >= apetyt[d]) {
        cout << "ciastko " << c << " -> dziecko z apetytem " << apetyt[d] << "\n";
        d++;
    }
}
cout << d << "\n";
▶ Wyjście
ciastko 2 -> dziecko z apetytem 2 ciastko 3 -> dziecko z apetytem 3 ciastko 9 -> dziecko z apetytem 5 3

Ciastko 1 jest za małe nawet dla najmniej wymagającego dziecka (2) — pomijamy. 2 → dziecko 2, 3 → dziecko 3. Ciastko 4 nie wystarczy dziecku z apetytem 5 — pomijamy. 9 → dziecko 5. Dla dziecka z apetytem 8 zabrakło ciastek.

Dlaczego dajemy ciastko najmniej wymagającemu? Bo większe ciastka warto zostawić dla bardziej wymagających dzieci.

Kiedy zachłanność zawodzi

Uwaga: nie każdy „oczywisty” pomysł zachłanny jest dobry. Wydajesz resztę monetami o nominałach 1, 3 i 4 i chcesz użyć jak najmniej monet. Zachłannie: zawsze największa moneta, która się mieści. Dla 6 zł: 4 + 1 + 1 — trzy monety. A wystarczą dwie: 3 + 3! Zachłanność zawiodła, bo nie da się tu przeprowadzić argumentu zamiany. Dlatego zanim zaufasz pomysłowi zachłannemu, sprawdź go na kilku małych przykładach — najlepiej porównując z rozwiązaniem, które sprawdza wszystkie możliwości.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Ile prezentów kupisz za 10 zł?
vector<int> c = {7, 2, 5, 3};
sort(c.begin(), c.end());
int b = 10, ile = 0;
for (auto x : c) {
    if (x > b) break;
    b -= x;
    ile++;
}
cout << ile;
Pokaż odpowiedź
3Po sortowaniu: 2, 3, 5, 7. 2 + 3 + 5 = 10 — trzy prezenty, na 7 już nie starcza.
Jaka jest suma czekania?
vector<int> t = {3, 1, 2};
sort(t.begin(), t.end());
int z = 0, s = 0;
for (auto x : t) { z += x; s += z; }
cout << s;
Pokaż odpowiedź
10Kończą po 1, 3 i 6 minutach: 1 + 3 + 6 = 10.
Ile łódek (L = 100)?
vector<int> w = {60, 40, 70, 30};
sort(w.begin(), w.end());
int i = 0, j = 3, ile = 0;
while (i <= j) {
    if (i < j && w[i] + w[j] <= 100) i++;
    j--;
    ile++;
}
cout << ile;
Pokaż odpowiedź
2Po sortowaniu: 30 40 60 70. Pary 30 + 70 i 40 + 60 — po 100.
Co wypisze ten fragment?
vector<int> a = {1, 2}, b = {3, 4};
cout << a[0] * b[0] + a[1] * b[1] << " " << a[0] * b[1] + a[1] * b[0];
Pokaż odpowiedź
11 10Największy z największym daje więcej (11), największy z najmniejszym — mniej (10).
Ile dzieci będzie zadowolonych?
vector<int> ap = {1, 2, 3}, c = {1, 1};
int d = 0;
for (auto x : c)
    if (d < 3 && x >= ap[d]) d++;
cout << d;
Pokaż odpowiedź
1Pierwsze ciastko (1) zadowala dziecko z apetytem 1. Drugie (1) nie wystarczy dziecku z apetytem 2.
Ile monet wyda zachłanna kasa (nominały 4, 3, 1)?
int reszta = 6, monet = 0;
int nom[3] = {4, 3, 1};
for (int k = 0; k < 3; k++) {
    while (reszta >= nom[k]) { reszta -= nom[k]; monet++; }
}
cout << monet;
Pokaż odpowiedź
34 + 1 + 1. A najlepiej byłoby 3 + 3 — dwie monety. Zachłanność tu zawodzi.
Jaka jest największa suma par po połączeniu „najmniejszy z największym”?
vector<int> v = {1, 9, 3, 7};
sort(v.begin(), v.end());
int najw = 0;
for (int i = 0; i < 2; i++) najw = max(najw, v[i] + v[3 - i]);
cout << najw;
Pokaż odpowiedź
10Pary (1, 9) i (3, 7) — obie po 10. Każde inne łączenie dałoby parę o sumie większej niż 10.
Co wypisze ten fragment?
vector<int> t = {4, 4, 1};
sort(t.begin(), t.end());
int z = 0, s = 0;
for (auto x : t) { z += x; s += z; }
cout << z << " " << s;
Pokaż odpowiedź
9 15Kończą po 1, 5 i 9 minutach. Ostatni zawsze kończy po sumie wszystkich czasów (9), ale suma czekania zależy od kolejności: 1 + 5 + 9 = 15.
Ćwiczenia · teraz Ty

7 ćwiczeń do tej części

0 / 7 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Baza zadań: sortowanie w praktyce

Znasz już wszystko, co potrzebne: sort rosnąco i malejąco na vectorze, tablicy i napisie, k-ty element i medianę, grupy równych wartości, unique i najbliższych sąsiadów, cztery metody sortowania ręcznego, własne reguły z lambdą, kilka kryteriów naraz i stable_sort, sortowanie numerów, miejsca w rankingu i kompresję, lower_bound i upper_bound, a na koniec pomysły zachłanne. Czas na zadania, które łączą kilka z tych rzeczy naraz. Są ułożone od najłatwiejszego do najtrudniejszego: najpierw rozgrzewka z jednym pomysłem, potem zadania średnie, w których łączysz dwa, trzy pomysły, a na końcu trudne — z wielkim finałem.

Przy każdym zadaniu widać, jakich zagadnień używa — także tych z poprzednich lekcji, jak napisy, pary czy vector. Jeśli coś brzmi obco, wróć do odpowiedniej części — mapa lekcji jest na górze strony. A tu masz najważniejsze schematy z lekcji w jednym miejscu:

Ściąga: gotowe schematy sortowania

Rosnąco i malejąco

sort(v.begin(), v.end());
sort(t, t + n);          // tablica
sort(v.rbegin(), v.rend());
sort(v.begin(), v.end(), greater<int>());

Napisy — alfabetycznie, ale wielkie litery przed małymi, a „10” przed „9”.

Adresy w posortowanym

v[0]   v[n - 1]          // min, max
v[k - 1]   v[n - k]      // k-ty od dołu, od góry
v[n / 2]                 // mediana (n nieparzyste)
(v[n/2 - 1] + v[n/2]) / 2.0

Remis na granicy: wszyscy z wynikiem ≥ v[n - k].

Grupy i unique

i = 0;
while (i < n) { j = i;
  while (j < n && v[j] == v[i]) j++;
  // grupa v[i..j-1]
  i = j; }
v.erase(unique(v.begin(), v.end()), v.end());

Najpierw sort! Najbliżsi to zawsze sąsiedzi: v[i + 1] - v[i].

Sortowanie ręczne

wybieranie: min z [i..n-1] na miejsce i
bąbelki: swap sąsiadów, runda po rundzie
wstawianie: x wsuwa się w lewą część
zliczanie: licznik[x]++, potem wypisz

Dwie pętle ≈ n·n — dobre do kilku tysięcy. sort ≈ n·log n.

Własna reguła

sort(v.begin(), v.end(), [](int a, int b) {
    if (kl(a) != kl(b)) return kl(a) < kl(b);
    return a < b;
});

„Czy a przed b?” Dla równych — false, więc nigdy <=. Zmienne z main: [&].

Kilka kryteriów

pair: najpierw first, potem second
(-punkty, czas)        // minus = malejąco
[](auto a, auto b) { ... }
stable_sort(...)       // remisy jak na wejściu

Główne kryterium na pierwsze miejsce pary albo do pierwszego ifa reguły.

Numery i rankingi

vector<int> nr(n);  nr[i] = i;
sort(nr..., [&](int a, int b) {
    return w[a] < w[b]; });
miejsce: jak poprzedni → to samo
kompresja: nowa wartość → numer++

k-ty w kolejności to nr[k], jego wartość — w[nr[k]].

Szukanie i zachłanność

binary_search(b, e, x)    // jest?
lower_bound(...) - v.begin()  // ile < x
upper_bound(...) - v.begin()  // ile ≤ x
[a, b]: U(b) - L(a)

Zachłannie: posortuj i bierz po kolei; sprawdź argumentem zamiany.

Jak rozwiązywać zadania z sortowaniem 1) Zadaj sobie pytanie: czy gdyby dane były posortowane, zadanie stałoby się proste? Prawie zawsze tak — wtedy pierwszy krok to sort. 2) Zdecyduj, według czego sortować: wartości, kilku kryteriów, a może numerów? Gdy po sortowaniu trzeba wiedzieć, kto był kim — sortuj numery albo pary (wartość, numer). 3) Ustal, co robić z remisami — zadanie zwykle to mówi. 4) Sprawdź ograniczenia: n do kilku tysięcy pozwala na dwie pętle, n do 100 000 — tylko na sort i połowienie. 5) Przetestuj skrajności: jeden element, wszystkie równe, liczby ujemne, ogromne wartości (long long!).
łatwe

Rozgrzewka · zadania 1–10

Jeden pomysł naraz: szereg na WF-ie, mały słownik, skarpetki do pary, ciąg arytmetyczny, najmniejszy wolny numer, brązowy medal, najcieplejsze dni, patyczki na trójkąt, liczba Kaprekara i pary butów.

1 Szereg na WF-iełatwe✓ zaliczone Ustaw dzieci od najwyższego. Ile z nich musi zmienić miejsce? sort malejącokopia vectoraporównanie pozycji Rozwiąż 2 Mały słownikłatwe✓ zaliczone Z tekstu zrób słownik: każde słowo raz, alfabetycznie, z liczbą wystąpień. vector<string>grupy napisówporządek słownikowy Rozwiąż 3 Skarpetki do paryłatwe✓ zaliczone Ile par skarpetek tego samego koloru da się złożyć i ile zostanie samotnych? sortgrupyliczba / 2 i liczba % 2 Rozwiąż 4 Ciąg arytmetyczny?łatwe✓ zaliczone Czy liczby da się ustawić tak, by każda następna była większa o tę samą wartość? sortróżnice sąsiadówTAK / NIE Rozwiąż 5 Najmniejszy wolny numerłatwe✓ zaliczone Jaka jest najmniejsza dodatnia liczba, której nie ma na liście? sortszukany numer rośniepowtórzenia i liczby ujemne Rozwiąż 6 Brązowy medalłatwe✓ zaliczone Medale dostają trzy najlepsze różne wyniki. Ile osób stanie na najniższym stopniu podium? sort malejącouniquetrzecia różna wartość Rozwiąż 7 Najcieplejsze dniłatwe✓ zaliczone Wybierz k najcieplejszych dni i wypisz ich numery po kolei w kalendarzu. sortowanie numerówdwa sortowaniaremis po numerze Rozwiąż 8 Patyczki na trójkątłatwe✓ zaliczone Czy z trzech spośród n patyczków da się złożyć trójkąt? Po sortowaniu wystarczą sąsiedzi. sorttrzech sąsiadówa + b > clong long Rozwiąż 9 Liczba Kaprekarałatwe✓ zaliczone Cyfry malejąco minus cyfry rosnąco — i tak w kółko, aż wyjdzie 6174. sortowanie cyfrstring i stoizera na początkupętla while Rozwiąż 10 Pary butówłatwe✓ zaliczone Lewe i prawe buty w różnych rozmiarach. Ile pełnych par da się złożyć? dwie posortowane listydwa wskaźnikijak scalanie Rozwiąż
średnie

Średnie · zadania 11–20

Kilka sztuczek naraz: dwa rankingi, sortowanie według częstości, indeks h, wyrównywanie wież, największy obwód, mediana na bieżąco, pary o różnicy k, zgrana drużyna, wieże z klocków i śpiewne słowa.

11 Dwa rankingiśrednie✓ zaliczone Ranking sportowy (1, 2, 2, 4) i ranking gęsty (1, 2, 2, 3) — dla każdego zawodnika. sortowanie numerówmiejsca ex aequodwa liczniki Rozwiąż 12 Według częstościśrednie✓ zaliczone Najczęstsze liczby na przód: sortuj według liczby wystąpień, a przy remisie według wartości. grupypary (liczba wystąpień, wartość)reguła Rozwiąż 13 Indeks naukowcaśrednie✓ zaliczone Największe h takie, że h prac ma co najmniej po h cytowań. sort malejącov[h] >= h + 1myślenie po sortowaniu Rozwiąż 14 Wyrównaj wieżeśrednie✓ zaliczone Ruch to dołożenie albo zdjęcie jednego klocka. Do jakiej wysokości wyrównać wieże najtaniej? medianasuma |h - t|long long Rozwiąż 15 Największy obwódśrednie✓ zaliczone Ułóż z trzech patyczków trójkąt o największym obwodzie. sort malejącopierwsza dobra trójkalong long Rozwiąż 16 Mediana na bieżącośrednie✓ zaliczone Liczby przychodzą po kolei. Po każdej nowej podaj medianę wszystkich dotychczasowych. vector posortowany cały czaslower_bound + insertmediana dolna Rozwiąż 17 Pary o różnicy kśrednie✓ zaliczone Ile par liczb (na różnych pozycjach) różni się dokładnie o k? sortupper_bound - lower_boundk = 0long long Rozwiąż 18 Zgrana drużynaśrednie✓ zaliczone Jak liczną drużynę da się zebrać, by rankingi graczy różniły się najwyżej o d? sortokno o zmiennej długościdwa wskaźniki albo upper_bound Rozwiąż 19 Wieże z klockówśrednie✓ zaliczone W wieży klocki muszą być coraz węższe. Ile najmniej wież zbudujesz ze wszystkich klocków? grupynajliczniejsza grupapomysł zamiast symulacji Rozwiąż 20 Śpiewne słowaśrednie✓ zaliczone Najpierw słowa z największą liczbą samogłosek, potem krótsze, potem alfabetycznie. reguła, która liczytrzy kryteriasamogłoski Rozwiąż
trudne

Trudne · zadania 21–28

Największa liczba ze sklejenia, kwota nie do zapłacenia, suma odległości, kary za czekanie, trójki o sumie zero, wyrównana grupa, książki na półce — a na koniec wielki finał: ranking olimpiady.

21 Największa liczba ze sklejeniatrudne✓ zaliczone Sklej liczby w jedną, jak największą. Reguła porównuje a + b z b + a. reguła na napisacha + b > b + asame zera Rozwiąż 22 Czego nie da się zapłacić?trudne✓ zaliczone Masz monety o różnych nominałach. Jaka najmniejsza kwota jest nie do zapłacenia bez reszty? sort rosnącozasięg 1..szachłanność z dowodemlong long Rozwiąż 23 Suma odległościtrudne✓ zaliczone Domy przy drodze: zsumuj odległości między wszystkimi parami domów — bez pętli w pętli. sortsumy prefiksowewkład każdego elementulong long Rozwiąż 24 Kary za czekanietrudne✓ zaliczone Zlecenia mają czas wykonania i karę za każdą minutę czekania. W jakiej kolejności je zrobić? reguła z mnożeniem na krzyżargument zamianylong long Rozwiąż 25 Trójki o sumie zerotrudne✓ zaliczone Ile trójek różnych liczb sumuje się do zera? Sortowanie i dwa wskaźniki. sortdwa wskaźniki dla każdego in · n zamiast n · n · n Rozwiąż 26 Wyrównana grupatrudne✓ zaliczone Usuń jak najmniej liczb, żeby największa była co najwyżej dwa razy większa od najmniejszej. sortdwa wskaźnikimax ≤ 2 · minlong long Rozwiąż 27 Książki na półcetrudne✓ zaliczone Jedyny ruch: weź książkę i odłóż ją na koniec półki. Ile ruchów, by tomy stały po kolei? pozycja każdej wartościnajdłuższy dobry początekmyślenie zamiast symulacji Rozwiąż 28 Wielki finał: ranking olimpiadytrudne✓ zaliczone Ułóż ranking z remisami ex aequo i odpowiadaj na pytania o miejsca, progi i liczbę osób z wynikiem. reguła z kilkoma kryteriamimiejsca ex aequolower_boundsortowanie numerów Rozwiąż

Częste błędy i dobre praktyki

📏
t + n, nie t + n - 1
Druga strzałka pokazuje miejsce, którego nie bierzemy. sort(t, t + n - 1) zostawia ostatni element nieposortowany. Dla pudełek 1..n: sort(t + 1, t + n + 1).
🔤
Napisy to nie liczby
Wielkie litery są przed małymi („Zosia” przed „ala”), a liczby zapisane jako napisy sortują się znak po znaku („100” przed „20”). Liczby wczytuj do int albo long long.
🧾
Sort zjada kolejność
Po sort nie wiadomo, gdzie co stało. Potrzebujesz oryginału — zrób kopię. Potrzebujesz numerów — sortuj pary (wartość, numer) albo vector numerów.
➗
Mediana przez 2.0
Przy parzystym n mediana to średnia dwóch środkowych: (a + b) / 2.0. Samo / 2 obetnie połówkę. Przy dużych liczbach sumuj w long long.
🧹
unique bez sort i bez erase
unique zbija tylko sąsiednie powtórzenia i nie skraca vectora. Zawsze: sort, a potem v.erase(unique(v.begin(), v.end()), v.end());.
⚖️
<= w regule
Reguła dla równych elementów musi zwracać false. return a <= b; potrafi wysypać program na dużym teście. Pisz < albo >.
🎲
Remisy bez rozstrzygnięcia
Gdy reguła mówi „remis”, sort ustawia takie elementy w dowolnej kolejności — nie w kolejności z wejścia. Dopisz kolejne kryterium (np. numer) albo użyj stable_sort.
👀
[] czy [&]?
Reguła z pustymi nawiasami nie widzi zmiennych z main — „is not captured”. Gdy w regule używasz k albo innego vectora, pisz [&].
🔎
Połowienie na nieposortowanym
binary_search, lower_bound i upper_bound na nieposortowanych danych dają bzdury bez ostrzeżenia. Najpierw sort — i to raz, a nie przy każdym pytaniu.
🚧
end() z lower_bound
Gdy wszystkie elementy są mniejsze od x, lower_bound zwraca end() — gwiazdka czyta wtedy spoza vectora. Najpierw sprawdź, czy numer jest mniejszy od n.
⏱️
Dwie pętle przy dużym n
Bąbelki, wybieranie i wstawianie robią około n·n kroków — dla n = 100 000 to 10 miliardów. Na zawodach sortuj przez sort, a pętle zostaw zadaniom o przebiegu algorytmu.
🍪
Zachłanność bez dowodu
„Bierz największe” nie zawsze działa (monety 1, 3, 4). Zanim zaufasz pomysłowi, sprawdź argument zamiany albo porównaj z rozwiązaniem sprawdzającym wszystko na małych testach.

Co dalej?

Sortowanie będzie Ci towarzyszyć już zawsze — w większości zadań olimpijskich pierwszą linijką rozwiązania po wczytaniu danych jest właśnie sort. W następnych lekcjach poznasz przydatne narzędzia matematyczne: max i min, zaokrąglanie, silnię i wartość bezwzględną. Kod sortowania przez scalanie i sortowania szybkiego napiszesz w lekcji o rekurencji, a lower_bound wróci przy zbiorach i mapach. A jeśli chcesz trenować z mentorami — dołącz do T-Olimpians.