Test on Beszúrásos rendezés (insertion sort)

Question 1: A beszúrásos rendezés pszeudokódjában az 'i' változóval jelölt ciklus a tömb első elemétől (index 0) kezdve iterál.

A. Yes

B. No

Explanation: A pszeudokód szerint a CIKLUS az 'i = 1-től n-1-ig' tart, ami azt jelenti, hogy a tömb második elemétől (index 1) kezdve iterál, mivel az első elem (index 0) eleve rendezettnek tekintendő.

Question 2: A beszúrásos rendezés a legalkalmasabb algoritmus nagy méretű, véletlenszerűen rendezett adathalmazok rendezésére.

A. Yes

B. No

Explanation: A beszúrásos rendezés egyik hátránya, hogy lassú nagy adathalmazokon, mert O(n²) időkomplexitású, ami jelentősen lassabb, mint a fejlettebb rendezési algoritmusok nagy adathalmazok esetén.

Question 3: A mellékelt tananyag alapján mi jellemzi a beszúrásos rendezés átlagos esetbeli (average case) időkomplexitását, és mit jelent ez az adathalmaz méretének változásakor?

A. O(n) időkomplexitású, ami azt jelenti, hogy az adathalmaz méretének duplázódásával a futási idő is duplázódik.

B. O(n²) időkomplexitású, ami azt jelenti, hogy ha az adathalmaz mérete megduplázódik, az algoritmus futási ideje körülbelül megnégyszereződik.

C. O(n log n) időkomplexitású, ami gyorsabb növekedést eredményez, mint az O(n²).

D. O(1) időkomplexitású, mivel helyben rendező algoritmusról van szó.

Explanation: Az időkomplexitás fejezet szerint a beszúrásos rendezés átlagos esete O(n²). A szöveg említi, hogy 'Az O(n²) azt jelenti, hogy ha az adathalmaz mérete megduplázódik, az algoritmus futási ideje körülbelül megnégyszereződik.' Az O(n) a legjobb esetre vonatkozik, az O(n log n) nem szerepel az időkomplexitások között a beszúrásos rendezésre, és az O(1) a térkomplexitásra jellemző, nem az időkomplexitásra.

Question 4: Melyik állítás írja le HELYESEN, hogy mit figyelhetünk meg vagy próbálhatunk ki egy interaktív szimulációban a beszúrásos rendezés működésével kapcsolatban a megadott tananyag szerint?

A. Megfigyelhető, hogyan tolódnak az elemek jobbra, hogy helyet csináljanak a „kulcsnak”, majd hogyan kerül a kulcs a megfelelő pozícióba.

B. Kísérletezhetünk különböző kezdeti adathalmazokkal (pl. rendezett, fordított sorrendű), és vizuálisan megérthetjük az O(n) és O(n²) időkomplexitás közötti különbséget.

C. Látható, ahogy a szimuláció vizuálisan elkülöníti a tömb már rendezett és még rendezetlen részét.

D. A szimulációban megfigyelhető, hogy a beszúrásos rendezés mindig a legkevesebb cserét igénylő algoritmus, függetlenül az adatok kezdeti elrendezésétől.

Explanation: Az első három állítás közvetlenül szerepel a 'Szimulációban Megfigyelhető és Kipróbálható Dolgok' szakaszban: 'Látható, ahogy az elemek jobbra tolódnak, hogy helyet csináljanak a kulcsnak, majd a kulcs bekerül a megfelelő pozícióba.', 'Kísérletezhetünk különböző kezdeti állapotokkal... Megfigyelhető, hogy a rendezett tömb esetén alig történik eltolás, míg a fordított sorrendű tömbnél minden elem beszúrása sok eltolással jár. Ez segít vizuálisan megérteni az O(n) és O(n²) időkomplexitás közötti különbséget.' és 'A szimuláció gyakran vizuálisan is elkülöníti a tömb már rendezett és még rendezetlen részét'. A negyedik állítás hibás, mivel a beszúrásos rendezés nem mindig igényli a legkevesebb cserét, különösen nagy és rosszul rendezett adathalmazok esetén, és ez az állítás nem is található meg a tananyagban.

Question 5: A stabilitás kritikus lehet, ha az elemek nem csak egy kulcsértékkel rendelkeznek, hanem más adatokkal is?

A. Yes

B. No

Explanation: A tanulmányi anyag szerint a stabilitás kritikus lehet, ha az elemek nem csak egy kulcsértékkel rendelkeznek, hanem más adatokkal is, és az eredeti sorrend megőrzése fontos az azonos kulcsértékű elemek között.