Programozási tételek III.

1. A kiválogatás tétele

A kiválogatás tételének segítségével egy adatsorozatból kiválasztjuk azokat az elemeket, amelyek megfelelnek egy adott feltételnek, és ezeket egy új adatsorozatba helyezzük.

A feladat lényege:

Fontos: A kiválogatás során az összes olyan elemet megkeressük, amely teljesíti a feltételt.

Mikor használjuk? Például:

Konkrét példa

Adott az alábbi számsorozat:

szamok = [12, 5, 18, 3, 9, 25, 7, 30, 14]

Válogassuk ki a páros számokat!

A feldolgozás lépései:

Először létrehozunk egy üres listát, amelybe a megfelelő elemeket fogjuk elhelyezni.

parosak = []

Ezután végigvizsgáljuk az eredeti lista elemeit.

A páros számok azok, amelyek 2-vel maradék nélkül oszthatók.

Ennek ellenőrzése Pythonban:

szam % 2 == 0

A % operátor az osztás maradékát adja vissza.

Például:

Szám Osztás 2-vel Maradék Páros?
12 12 / 2 0 Igen
5 5 / 2 1 Nem

Az új lista tehát:

parosak = [12, 18, 30, 14]

Az algoritmus általános felépítése

A kiválogatás során három fontos lépést kell megvalósítanunk:

  1. Létrehozunk egy üres listát.
  2. Végigmegyünk az eredeti lista minden elemén.
  3. Ha egy elem megfelel a feltételnek, hozzáadjuk az új listához.

Pszeudokód:

Kiválogatás: kivalogatott := üres lista CIKLUS i = 0-tól N-1-ig HA tömb[i] megfelel a feltételnek AKKOR kivalogatott végére hozzáadjuk tömb[i]-t ELÁGAZÁS VÉGE CIKLUS VÉGE KI: kivalogatott Kiválogatás vége

A pszeudokódban a kivalogatott egy új adatsorozat, ami kezdetben üres.

Megvalósítás Python nyelven

szamok = [12, 5, 18, 3, 9, 25, 7, 30, 14] parosak = [] for szam in szamok: if szam % 2 == 0: parosak.append(szam) print("Az eredeti lista:", szamok) print("A páros számok:", parosak)

Eredmény:

Az eredeti lista: [12, 5, 18, 3, 9, 25, 7, 30, 14] A páros számok: [12, 18, 30, 14]

A program működése

1. Az eredeti lista létrehozása

szamok = [12, 5, 18, 3, 9, 25, 7, 30, 14]

Ebben a listában tároljuk az adatokat.

2. Az új lista létrehozása

parosak = []

Egy üres listát hozunk létre. Ebbe kerülnek majd a kiválogatott páros számok.

3. A lista bejárása

for szam in szamok:

A ciklus végigmegy az eredeti lista minden elemén.

4. A feltétel ellenőrzése

if szam % 2 == 0:

Megvizsgáljuk, hogy az aktuális szám páros-e.

5. Az elem hozzáadása az új listához

parosak.append(szam)

Ha a szám páros, hozzáadjuk az új lista végéhez.

6. Az eredmény kiírása

print(parosak)

A ciklus befejezése után az új lista már tartalmazza az összes megfelelő elemet.

Kiválogatás indexek segítségével

A kiválogatás megvalósítható hagyományos, indexekkel dolgozó ciklussal is.

szamok = [12, 5, 18, 3, 9, 25, 7, 30, 14] parosak = [] for i in range(len(szamok)): if szamok[i] % 2 == 0: parosak.append(szamok[i]) print("A páros számok:", parosak)

Gyakorlófeladatok - kiválogatás

1. feladat – Megfelelő dolgozateredmények kiválogatása

Egy osztály dolgozatpontszámai:

pontok = [45, 78, 92, 34, 65, 88, 51, 100, 72, 39]

Válogasd ki azokat, akik legalább 70 pontot értek el!

2. feladat – Magánhangzóval kezdődő nevek kiválogatása

Adott egy névlista:

nevek = ["Anna", "Béla", "Emese", "Dávid", "István", "Katalin", "Orsolya"]

Válogasd ki azokat a neveket, amelyek magánhangzóval kezdődnek!

3. feladat – Több feltétel együttes alkalmazása

Adott egy számlista:

szamok = [12, 25, 30, 45, 50, 65, 70, 85, 90]

Válogasd ki azokat a számokat, amelyek:


Egyszerű cserés rendezés (Bubble Sort / Buborék rendezés)

A rendezés egy olyan algoritmikus feladat, amelynek során egy adatsorozat elemeit meghatározott sorrendbe állítjuk.

A rendezés történhet például:

A rendezés nagyon gyakori feladat a programozásban.

Például:

Mi az egyszerű cserés rendezés?

Az egyszerű cserés rendezés angol neve Bubble Sort, magyarul gyakran buborékrendezésnek is nevezzük.

Az algoritmus lényege:

  1. Megvizsgáljuk a szomszédos elemeket.
  2. Összehasonlítjuk őket.
  3. Ha nem megfelelő sorrendben vannak, felcseréljük őket.
  4. Ezt a folyamatot többször megismételjük.
  5. A végén az elemek rendezett sorrendbe kerülnek.

A rendezés során a nagyobb értékek növekvő rendezés esetén fokozatosan a lista vége felé haladnak, mintha buborékként emelkednének a felszínre.

Konkrét példa – Növekvő sorrendbe rendezés

Adott az alábbi lista:

szamok = [5, 3, 8, 2, 1]

Rendezzük növekvő sorrendbe!

A kívánt eredmény:

[1, 2, 3, 5, 8]

Első menet

Összehasonlítjuk az egymás mellett álló elemeket.

Kezdeti lista:

5, 3, 8, 2, 1

1. összehasonlítás:

5 és 3.

Mivel 5 nagyobb, mint 3, felcseréljük őket.

3, 5, 8, 2, 1

2. összehasonlítás:

5 és 8.

Mivel 5 kisebb, mint 8, nem cseréljük fel őket.

3, 5, 8, 2, 1

3. összehasonlítás:

8 és 2.

Mivel 8 nagyobb, mint 2, felcseréljük őket.

3, 5, 2, 8, 1

4. összehasonlítás:

8 és 1.

Mivel 8 nagyobb, mint 1, felcseréljük őket.

3, 5, 2, 1, 8

Az első menet végére a legnagyobb szám, a 8, a lista végére került.

Második menet

A következő menetben már nem szükséges az utolsó elemet vizsgálni, hiszen az már a helyére került.

Kezdő lista:

3, 5, 2, 1, 8

1. összehasonlítás:

3 és 5 – nem kell csere.

2. összehasonlítás:

5 és 2 – csere.

3, 2, 5, 1, 8

3. összehasonlítás:

5 és 1 – csere.

3, 2, 1, 5, 8

Harmadik menet

Kezdő lista:

3, 2, 1, 5, 8

1. összehasonlítás:

3 és 2 – csere.

2, 3, 1, 5, 8

2. összehasonlítás:

3 és 1 – csere.

2, 1, 3, 5, 8

Negyedik menet

Kezdő lista:

2, 1, 3, 5, 8

1. összehasonlítás:

2 és 1 – csere.

1, 2, 3, 5, 8

A lista rendezetté vált.

Az összes menet összefoglalása

Állapot Lista
Kezdeti állapot 5, 3, 8, 2, 1
1. menet után 3, 5, 2, 1, 8
2. menet után 3, 2, 1, 5, 8
3. menet után 2, 1, 3, 5, 8
4. menet után 1, 2, 3, 5, 8

Eredmény:

1, 2, 3, 5, 8


Az egyszerű cserés rendezés algoritmusa

Az algoritmus működéséhez két egymásba ágyazott ciklust használunk.

Ha az aktuális elem nagyobb, mint az utána következő, akkor felcseréljük őket.

Pszeudokód

Buborék rendezés: CIKLUS i = 0-tól N-2-ig CIKLUS j = 0-tól N-2-i-ig HA tömb[j] > tömb[j+1] AKKOR CSERE tömb[j] és tömb[j+1] között ELÁGAZÁS VÉGE CIKLUS VÉGE CIKLUS VÉGE KI: rendezett tömb Buborék rendezés vége

Változók jelentése:

Miért kell az N-2-i határ?

Minden egyes menet végére a legnagyobb, még rendezetlen elem a megfelelő helyére kerül.

Ezért a következő menetben már nem kell a korábban rendezett utolsó elemeket vizsgálni.

Így a belső ciklus egyre kevesebb összehasonlítást végez.


Egyszerű cserés rendezés Python nyelven

Alapmegoldás növekvő sorrendben

szamok = [5, 3, 8, 2, 1] n = len(szamok) for i in range(n - 1): for j in range(n - 1 - i): if szamok[j] > szamok[j + 1]: seged = szamok[j] szamok[j] = szamok[j + 1] szamok[j + 1] = seged print("Rendezett lista:", szamok)

📣 Egyszerűbb csere Pythonban

Pythonban lehetőség van arra is, hogy két változó értékét egyetlen utasítással felcseréljük.

python

a = 5 b = 3 a, b = b, a print(a) print(b)

Eredmény:

3 5

Így a rendezési algoritmus csere része egyszerűsíthető:

szamok[j], szamok[j + 1] = szamok[j + 1], szamok[j]

A teljes program ezzel a megoldással:

szamok = [5, 3, 8, 2, 1] n = len(szamok) for i in range(n - 1): for j in range(n - 1 - i): if szamok[j] > szamok[j + 1]: szamok[j], szamok[j + 1] = szamok[j + 1], szamok[j] print("Rendezett lista:", szamok)

Egyszerű cserés rendezés csökkenő sorrendben

A rendezési algoritmus nagyon könnyen módosítható úgy, hogy ne növekvő, hanem csökkenő sorrendbe rendezze a listát.

Eddig ezt a feltételt használtuk:

if szamok[j] > szamok[j + 1]:

Ez azt jelenti, hogy ha a bal oldali szám nagyobb, akkor cserélünk.

Csökkenő rendezés esetén a kisebb számokat szeretnénk a lista végére küldeni.

Ezért a feltételt megfordítjuk:

if szamok[j] < szamok[j + 1]:

Teljes program

szamok = [5, 3, 8, 2, 1] n = len(szamok) for i in range(n - 1): for j in range(n - 1 - i): if szamok[j] < szamok[j + 1]: szamok[j], szamok[j + 1] = szamok[j + 1], szamok[j] print("Csökkenő sorrend:", szamok)

Eredmény:

Csökkenő sorrend: [8, 5, 3, 2, 1]

Növekvő és csökkenő rendezés összehasonlítása

Rendezés típusa Feltétel
Növekvő szamok[j] > szamok[j+1]
Csökkenő szamok[j] < szamok[j+1]

A két algoritmus között tehát csak az összehasonlítás iránya változik.


Gyakorlófeladatok - Egyszerű cserés rendezés

4. feladat – Nevek rendezése

Rendezd ABC-sorrendbe az alábbi neveket!

nevek = ["Zoltán", "Anna", "Péter", "Béla", "Dávid"]

5. feladat – Legmagasabb pontszámoktól a legalacsonyabbakig

Egy osztály dolgozateredményei:

pontok = [56, 92, 45, 78, 100, 65, 88]

Rendezd csökkenő sorrendbe!


Összetett gyakorlófeladatok

Ezek a feladatok már több programozási tétel együttes alkalmazását igénylik.

6. feladat – Tanulók eredményeinek feldolgozása

Egy osztály dolgozateredményei:

pontok = [45, 78, 92, 34, 65, 88, 51, 100, 72, 39]

Készíts programot, amely:

  1. Kiválogatja a legalább 60 pontos eredményeket.
  2. Meghatározza a legmagasabb pontszámot.
  3. Meghatározza a legalacsonyabb pontszámot.
  4. Növekvő sorrendbe rendezi a kiválogatott eredményeket.

7. feladat – Webáruház termékeinek feldolgozása

Egy webáruház termékeinek árai:

arak = [2500, 12000, 8500, 45000, 3200, 18000, 7500, 55000]

Készíts programot, amely:

  1. Kiválogatja a 10000 Ft alatti termékeket.
  2. Növekvő sorrendbe rendezi a kiválogatott árakat.
  3. Meghatározza a legolcsóbb terméket.
  4. Meghatározza a legdrágább terméket.

8. feladat – Páros számok kiválogatása és rendezése

Adott egy számlista:

szamok = [15, 8, 23, 4, 18, 7, 30, 12, 5, 20]

Készíts programot, amely:

  1. Kiválogatja a páros számokat.
  2. Csökkenő sorrendbe rendezi őket.
  3. Kiírja a rendezett listát.

12. Gyakori hibák, amelyekre érdemes figyelni

Hiba Miért probléma? Helyes megoldás
Nem hozunk létre üres listát. Nincs hová gyűjteni az elemeket. kivalogatott = []
Elmarad az append(). A megfelelő elemek nem kerülnek az új listába. kivalogatott.append(elem)
Rossz feltételt használunk. Nem a megfelelő elemeket válogatjuk ki. Pontosan meg kell határozni a feltételt.
A rendezésnél nem szomszédos elemeket hasonlítunk össze. Nem a Bubble Sort algoritmust valósítjuk meg. lista[j] és lista[j+1] összehasonlítása.
Felcseréljük az összehasonlítás irányát. Fordított sorrendet kapunk. Növekvő: >; csökkenő: <.
Hibás a belső ciklus határa. Indexelési hiba keletkezhet. range(n - 1 - i)
Csere közben elveszítjük az egyik értéket. Nem lesz helyes a csere. Segédváltozó vagy Python-féle értékcsere.

13. A két algoritmus összehasonlítása

Szempont Kiválogatás Egyszerű cserés rendezés
Cél Megfelelő elemek összegyűjtése Elemsorrend kialakítása
Bemenet Egy lista Egy lista
Eredmény Új lista Rendezett lista
Ciklusok Általában egy ciklus Két egymásba ágyazott ciklus
Feltétel A kiválogatás feltétele Szomszédos elemek összehasonlítása
Fő Python-művelet append() Értékcsere
Példa Páros számok kiválogatása Számok növekvő rendezése

13.1. A kiválogatás mintakódja

python

kivalogatott = [] for elem in lista: if feltetel: kivalogatott.append(elem)

13.2. Az egyszerű cserés rendezés mintakódja

python

n = len(lista) for i in range(n - 1): for j in range(n - 1 - i): if lista[j] > lista[j + 1]: lista[j], lista[j + 1] = lista[j + 1], lista[j]

Ezt a két kódrészletet érdemes a tanulóknak begyakorolniuk.


14. Ellenőrző kérdések

  1. Mi a kiválogatás tételének célja?
  2. Mi a különbség a kiválasztás és a kiválogatás között?
  3. Miért hozunk létre egy üres listát a kiválogatás elején?
  4. Mire használjuk az append() metódust?
  5. Mit jelent a % operátor?
  6. Hogyan ellenőrizzük, hogy egy szám páros-e?
  7. Mit jelent a startswith() metódus?
  8. Mi a rendezés célja?
  9. Mi az egyszerű cserés rendezés angol neve?
  10. Miért használunk két egymásba ágyazott ciklust?
  11. Mit hasonlítunk össze a belső ciklusban?
  12. Mikor cseréljük fel a két szomszédos elemet?
  13. Miért csökken a belső ciklus által vizsgált elemek száma?
  14. Hogyan módosítjuk a programot csökkenő rendezéshez?
  15. Mire használjuk a segédváltozót?
  16. Hogyan lehet Pythonban egyszerűbben felcserélni két változó értékét?

15. Fontos kiegészítés: A rendezés hatékonysága

A szoftverfejlesztő tanulóknak érdemes megismerniük, hogy nem minden rendezési algoritmus ugyanolyan gyors.

Az egyszerű cserés rendezés könnyen megtanulható, de nagy adatmennyiségnél nem túl hatékony.

Mennyi összehasonlítást végez?

Ha a listában 5 elem van, akkor a rendezés legfeljebb 10 szomszédos összehasonlítást végez.

Általánosságban az összehasonlítások száma nagyjából az elemek számának négyzetével arányos.

Ezt így jelöljük:

O(n²)

Ez azt jelenti, hogy ha az adatok száma jelentősen megnő, a rendezés ideje még gyorsabban növekedhet.

Például:

Lista elemszáma Összehasonlítások maximális száma
5 10
10 45
20 190
100 4950
1000 499 500

Ezért az egyszerű cserés rendezést elsősorban kisebb adatsorozatok rendezésére, illetve algoritmikus alapok tanítására használjuk.

Python beépített rendezési lehetőségei

Pythonban természetesen nem szükséges minden esetben saját rendezőalgoritmust írnunk.

Két fontos lehetőség:

1. sorted() függvény

Új, rendezett listát készít, az eredeti lista változatlan marad.

python

szamok = [5, 3, 8, 2, 1] rendezett = sorted(szamok) print(rendezett) print(szamok)

Eredmény:

text

[1, 2, 3, 5, 8] [5, 3, 8, 2, 1]

2. sort() metódus

Az eredeti listát rendezi át.

python

szamok = [5, 3, 8, 2, 1] szamok.sort() print(szamok)

Eredmény:

text

[1, 2, 3, 5, 8]

Csökkenő rendezés:

python

szamok = [5, 3, 8, 2, 1] szamok.sort(reverse=True) print(szamok)

Eredmény:

text

[8, 5, 3, 2, 1]

A Python beépített rendezési módszerei a Timsort algoritmust használják, amely általában sokkal hatékonyabb az egyszerű cserés rendezésnél.

Oktatási szempontból fontos: A tanulóknak először saját ciklusokkal kell megvalósítaniuk a rendezést. A sort() és sorted() csak az algoritmus működésének megértése után következzen.


16. Összefoglalás – Mit kell tudni a két tételről?

Tétel Legfontosabb gondolat Python-megoldás
Kiválogatás Minden megfelelő elemet összegyűjtünk append()
Egyszerű cserés rendezés Szomszédos elemeket hasonlítunk össze és szükség esetén cserélünk Két egymásba ágyazott ciklus

Hogyan jegyezzék meg a diákok?

Kiválogatás:

„Végignézem az összes elemet, és amelyik megfelel a feltételnek, azt beteszem egy új listába.”

Egyszerű cserés rendezés:

„Megnézem az egymás mellett álló elemeket. Ha rossz sorrendben vannak, felcserélem őket. Ezt addig ismétlem, amíg kialakul a rendezett lista.”

Javasolt oktatási sorrend

  1. Kiválogatás páros és páratlan számokkal.
  2. Kiválogatás összetettebb feltételekkel.
  3. Kiválogatás karakterláncokkal, nevekkel.
  4. Egyszerű cserés rendezés növekvő sorrendben.
  5. A rendezés lépéseinek táblázatos követése.
  6. Egyszerű cserés rendezés csökkenő sorrendben.
  7. Kiválogatás és rendezés együttes alkalmazása.

A két téma elsajátításának ellenőrzésére különösen jó feladat: egy számlistából válogassák ki a páros számokat, majd a kiválogatott számokat rendezzék növekvő sorrendbe. Ez egyszerre ellenőrzi a kiválogatás és a rendezés megértését, valamint a ciklusok és az elágazások helyes használatát.