If you're seeing this message, it means we're having trouble loading external resources on our website.

Ha webszűrőt használsz, győződj meg róla, hogy a *.kastatic.org és a *.kasandbox.org nincsenek blokkolva.

Fő tartalom

Minimumkiválasztásos rendezés pszeudokódja

Kártyákat többféleképpen lehet sorba rendezni. Íme egy egyszerű minimumkiválasztásos rendezés (selection sort) nevű eljárás, ami valószínűleg hasonló ahhoz, ahogy te rendezted a kártyákat:
  1. Keresd meg a legkisebb kártyát! Cseréld ki az első kártyával!
  2. Keresd meg a második legkisebb kártyát! Cseréld ki a második kártyával!
  3. Keresd meg a harmadik legkisebb kártyát! Cseréld ki a harmadik kártyával!
  4. Ismételd meg a következő legkisebb kártya keresését, és cseréld ki a megfelelő helyen levő kártyával!
Ezt az algoritmust minimumkiválasztásos keresésnek hívják, mert folyamatosan kiválasztja a következő legkisebb elemet, és kicseréli a megfelelő helyen lévő elemmel.
Itt láthatod az algoritmust. A „Step" gomb megnyomásával lépésenként tudod nyomon követni az algoritmust, a „Play" gombbal az egészet lefuttathatod, ha már megértetted a működést. (A feliratok: „It seem to have gotten my cards all mixed up...” jelentése: „Úgy tűnik, összekeveredtek a kártyáim...”, „Finding next smallest...” jelentése: „A következő legkisebb megkeresése...”, „Sorted!” jelentése „Sorba rendezve!”, a swapping jelentése cserélés. A gombok felirata: Lépés, Lejátszás, Keverés)
Miután megnézted működés közben, mit gondolsz erről az algoritmusról? Mik azok a részek, amik sokáig tartanak? Mit gondolsz, nagy tömbön mennyire lenne hatékony? Tartsd észben ezeket a megfontolásokat, mialatt ezt az algoritmust megvalósítod!

A legkisebb elem megkeresése egy résztömbben

A minimumkiválasztásos rendezés egyik lépése az, hogy a megkeressük a következő legkisebb kártyát, hogy a helyére tegyük. Például, ha az eredeti tömbünk [13, 19, 18, 4, 10], akkor először meg kell keresni a legkisebb szám indexét. Mivel 4 a legkisebb szám, a legkisebb szám indexe 3.
A minimumkiválasztásos rendezés kicseréli a 3-as és 0-s indexű elemet, így [4, 19, 18, 13, 10]-t kapunk. Most a második legkisebb szám indexét kell megkeresni és kicserélni az 1-es indexű számmal.
Nem könnyű megírni azt a programot, ami a második legkisebb elem indexét keresi meg a tömbben, de biztos vagyok benne, hogy meg tudnád oldani. Viszont van egy egyszerűbb lehetőség is. Figyeld meg, hogy mivel a legkisebb értéket már elhelyeztük a 0-s indexen, mi igazándiból a tömbnek az 1-es indexszel kezdődő részében szeretnénk megtalálni a legkisebbet. Egy tömb részét résztömbnek hívunk, úgyhogy ebben az esetben az 1-es indexszel kezdődő résztömb legkisebb elemére van szükségünk. A mi példánk esetében, ha a teljes tömb [4, 19, 18, 13, 10], akkor az 1-es indexszel kezdődő résztömb legkisebb eleme a 10, aminek az indexe 4 az eredeti tömbben. Így a 4-es indexen található a teljes tömb második legkisebb eleme.
Próbáld ki ezt a stratégiát a következő feladatban, és akkor már majdnem minden meglesz ahhoz, hogy elkészítsd a teljes minimumkiválasztásos rendezés algoritmusát.

Ez a fejezet a Dartmouth Computer Science két professzora, Thomas Cormen és Devin Balkcom, valamint a Khan Academy informatika tanmenetfejlesztő csapatának együttműködésében készült. A tartalom a CC-BY-NC-SA licenc alatt engedélyezett.

Szeretnél részt venni a beszélgetésben?

Még nincs hozzászólás.
Tudsz angolul? Kattints ide, ha meg szeretnéd nézni, milyen beszélgetések folynak a Khan Academy angol nyelvű oldalán.