Python stazaCjelina 3 · Tekst i listeLekcija 19

Sortiranje

Poredati brojeve od najmanjeg prema najvećem Python zna sam. Važnije je ono što slijedi: na sortiranoj listi mnogi zadaci postaju puno lakši.

Pythonoko 45 minuta4 zadatka za evaluator

1Sortiranje liste

Sortirati znači poredati od najmanjeg prema najvećem. Python to radi sam: a.sort() sortira listu.

Program
a = [7, 2, 9, 4, 2]
a.sort()
print(a)
a.sort(reverse=True)
print(a)
Ispis
[2, 2, 4, 7, 9] [9, 7, 4, 2, 2]
Ključna ideja

reverse=True sortira obrnuto, od najvećeg prema najmanjem.

2sort ili sorted

Postoje dva načina. a.sort() mijenja samu listu. sorted(a) ostavlja listu kakva jest i daje novu, sortiranu listu.

Program
a = [7, 2, 9]
b = sorted(a)
print(a)
print(b)
Ispis
[7, 2, 9] [2, 7, 9]
Pazi

a = a.sort() je česta greška: sort ne vraća listu, pa bi u a ostala posebna vrijednost None. Piši samo a.sort().

sorted radi i sa stringom: daje listu njegovih slova poredanih po abecedi.

Program
print(sorted("mama"))
print(sorted(["Ivo", "Ana", "Marko"]))
Ispis
['a', 'a', 'm', 'm'] ['Ana', 'Ivo', 'Marko']

3Što je lako na sortiranoj listi

Mnogi zadaci postaju jednostavni kad je lista sortirana:

PitanjeNa sortiranoj listi a
najmanji i najvećia[0] i a[-1]
drugi najvećia[-2]
srednji element (medijan), za neparan Na[len(a) // 2]
jesu li neki brojevi jednakijednaki su sada jedan do drugoga, pa uspoređujemo susjede
dva najbliža brojanajbliži su sada susjedi

Primjer: koliko je različitih brojeva u listi? Nakon sortiranja jednaki brojevi stoje zajedno, pa brojimo koliko je puta element različit od prethodnog.

a = list(map(int, input().split()))
a.sort()
razlicitih = 1
for i in range(1, len(a)):
    if a[i] != a[i - 1]:
        razlicitih += 1
print(razlicitih)
Ulaz
5 3 5 1 3 5
Ispis
3

4Anagrami

Dvije riječi su anagrami ako imaju ista slova, samo drugačijim redom: „rak“ i „kar“, „lopta“ i „plato“. Ako slova obiju riječi sortiramo, anagrami daju istu listu.

a = input()
b = input()
if sorted(a) == sorted(b):
    print("anagrami")
else:
    print("nisu anagrami")
Ulaz
lopta plato
Ispis
anagrami
Ključna ideja

Sortiranje je često prvi korak: poredaj podatke, pa je ostatak zadatka puno lakši.

Na natjecanju

Sortiranje je vrlo brzo, i za milijun brojeva. Ako zadatak izgleda teško, pitaj se postaje li lakši kad su podaci sortirani.

5Provjeri se

Prije zadataka provjeri jesi li razumio gradivo. Klikni na odgovor za koji misliš da je točan.

Pitanje

Razlika između L.sort() i sorted(L)?

Pitanje

Kako sortirati od najvećeg prema najmanjem?

Pitanje

Kako provjeriti jesu li dvije riječi anagrami?

6Zadaci

Poredaj

★☆☆ lagano

Ispiši brojeve od najmanjeg prema najvećem.

Ulaz
U prvom retku N. U drugom retku N cijelih brojeva.
Izlaz
Sortirani brojevi u jednom retku, odvojeni razmakom.
Ograničenja
1 ≤ N ≤ 1000
Ulaz
5 4 -1 7 4 0
Izlaz
-1 0 4 4 7
Riješi u evaluatoru

Anagram

★★☆ srednje

Jesu li dvije riječi anagrami?

Ulaz
Dva retka, u svakom jedna riječ od malih slova.
Izlaz
DA ili NE.
Ograničenja
Riječi imaju od 1 do 100 slova.
Ulaz
rak kar
Izlaz
DA
Ulaz
mama mara
Izlaz
NE
Riješi u evaluatoru

Srednji rezultat

★★☆ srednje

Na natjecanju je N učenika, N je neparan. Koliko bodova ima učenik koji je točno u sredini poretka?

Ulaz
U prvom retku neparan N. U drugom retku N brojeva, bodovi učenika.
Izlaz
Bodovi učenika u sredini poretka.
Ograničenja
1 ≤ N ≤ 999, N je neparan
Ulaz
5 40 10 90 70 20
Izlaz
40
Riješi u evaluatoru

Najbliži par

★★★ teže

Kolika je najmanja razlika između dva broja iz liste?

Ulaz
U prvom retku N. U drugom retku N cijelih brojeva.
Izlaz
Najmanja razlika između dva različita elementa liste (po mjestu, ne nužno po vrijednosti).
Ograničenja
2 ≤ N ≤ 100 000, brojevi su od 0 do 1 000 000 000
Ulaz
5 30 4 18 25 9
Izlaz
5
Treba ti pomoć?

Uspoređivati svaki broj sa svakim je presporo za 100 000 brojeva. Nakon sortiranja najbliži brojevi su susjedi, pa je dovoljna jedna petlja.

Riješi u evaluatoru
Vježbaj dalje: zadaci s natjecanja

Ovi zadaci s Infokupa traže upravo ovo gradivo. Kreni od prvoga.

  1. Luka Infokup 2013 · školsko · 7. r. OŠ
  2. Strah Infokup 2019 · županijsko · 7. r. OŠ
  3. Kripto Infokup 2017 · županijsko · 8. r. OŠ

7Što smo naučili

  • a.sort() sortira listu; reverse=True obrnuto.
  • sorted(a) daje novu sortiranu listu, a a ostaje ista.
  • Na sortiranoj listi: najmanji je a[0], najveći a[−1], jednaki i najbliži su susjedi.
  • Sortirana slova riječi otkrivaju anagrame.
Najčešće greške

a = a.sort() · zaboravljeno sortiranje prije uspoređivanja susjeda · medijan krivog indeksa