Test on Buborékrendezés (bubble sort)

Question 1: Arányos a buborékrendezés összehasonlításainak és cseréinek száma a bemeneti lista méretének négyzetével?

A. Yes

B. No

Explanation: A buborékrendezés hatékonyságát az időbonyolultságával jellemezzük, ami azt mutatja meg, hogyan növekszik az algoritmus futási ideje a bemeneti adatok méretének (n) függvényében. A buborékrendezés esetében az összehasonlítások és cserék száma a bemeneti lista méretének négyzetével arányos.

Question 2: Mely állítások jellemzik a buborékrendezés alapvető működési elvét a megadott tanulmányi anyag alapján?

A. Ismételten végigmegy a listán, összehasonlítja a szomszédos elemeket, és ha rossz sorrendben vannak, felcseréli őket.

B. A rendezési folyamat akkor áll le, ha egy teljes menet során nem történik egyetlen csere sem.

C. Minden egyes menetben egyre több elemet kell vizsgálni, ahogy a nagyobb elemek a lista elejére kerülnek.

D. Az első menet végére a legkisebb elem kerül garantáltan a lista első pozíciójára.

Explanation: Az első opció (0) pontosan leírja a buborékrendezés alapelvét: 'ismételten végigmegy egy listán, összehasonlítja a szomszédos elemeket, és felcseréli őket, ha rossz sorrendben vannak'. A második opció (1) a leállítási feltételre vonatkozik, mely szerint 'az algoritmus akkor áll le, ha egy teljes menet során nem történt egyetlen csere sem'. A harmadik opció (2) téves, mivel a szöveg szerint 'minden egyes menetben eggyel kevesebb elemet kell vizsgálni'. A negyedik opció (3) is téves, mert az anyag szerint 'az első menet végére a legnagyobb elem garantáltan a lista utolsó pozíciójára kerül'.

Question 3: A buborékrendezés átlagos időbonyolultsága O(n), mert csak az elemek fele szorul cserére.

A. Yes

B. No

Explanation: Az átlagos eset időbonyolultsága O(n²), nem pedig O(n), mert az elemek nagyjából fele cserére szorul, ami szintén négyzetes komplexitást eredményez.

Question 4: Az optimalizált buborékrendezés Python kódjában a `csere_tortent` logikai változó az egész rendezési folyamat alatt csak egyszer, a függvény elején inicializálódik `False` értékre.

A. Yes

B. No

Explanation: Az optimalizált buborékrendezés Python kódjában a `csere_tortent` logikai változó minden külső ciklus elején inicializálódik `False` értékre (`for i in range(n - 1):` ciklusban), nem pedig csak egyszer, a függvény elején.

Question 5: Melyik állítás írja le pontosan a buborékrendezés algoritmusának legrosszabb esetre vonatkozó időbonyolultságát az adott tananyag alapján?

A. Az időbonyolultság O(n), mert a lista már rendezett.

B. Az időbonyolultság O(n²), mert a lista fordított sorrendben van, és minden összehasonlítás cserét igényel.

C. Az időbonyolultság O(log n), mivel az algoritmus felezéssel dolgozik.

D. Az időbonyolultság O(n²), de csak ha a lista optimalizálatlan.

Explanation: A tananyag szerint a buborékrendezés legrosszabb esete akkor fordul elő, ha a lista fordított sorrendben van, és ekkor minden összehasonlítás cserét eredményez. Az összehasonlítások és cserék száma ekkor közel n·(n-1)/2, ami O(n²) nagyságrendű. Ez pontosan leírja a buborékrendezés legrosszabb esetének időbonyolultságát.