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:
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]
A kiválogatás során három fontos lépést kell megvalósítanunk:
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.
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]
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.
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)
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!
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!
Adott egy számlista:
szamok = [12, 25, 30, 45, 50, 65, 70, 85, 90]
Válogasd ki azokat a számokat, amelyek:
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:
Az egyszerű cserés rendezés angol neve Bubble Sort, magyarul gyakran buborékrendezésnek is nevezzük.
Az algoritmus lényege:
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.
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]
Ö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.
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
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
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.
| Á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 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:
i: A külső ciklus számlálója, vagyis hányadik rendezési menetnél járunk.j: A belső ciklus számlálója, vagyis melyik szomszédos elempárt vizsgáljuk.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.
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)
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)
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]:
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]
| 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.
Rendezd ABC-sorrendbe az alábbi neveket!
nevek = ["Zoltán", "Anna", "Péter", "Béla", "Dávid"]
Egy osztály dolgozateredményei:
pontok = [56, 92, 45, 78, 100, 65, 88]
Rendezd csökkenő sorrendbe!
Ezek a feladatok már több programozási tétel együttes alkalmazását igénylik.
Egy osztály dolgozateredményei:
pontok = [45, 78, 92, 34, 65, 88, 51, 100, 72, 39]
Készíts programot, amely:
Egy webáruház termékeinek árai:
arak = [2500, 12000, 8500, 45000, 3200, 18000, 7500, 55000]
Készíts programot, amely:
Adott egy számlista:
szamok = [15, 8, 23, 4, 18, 7, 30, 12, 5, 20]
Készíts programot, amely:
| 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. |
| 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 |
python
kivalogatott = []
for elem in lista:
if feltetel:
kivalogatott.append(elem)
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.
append() metódust?% operátor?startswith() metódus?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.
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.
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.
| 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 |
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.”
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.