Test on Gyorsrendezés (quicksort)

Question 1: A Gyorsrendezés algoritmusában a pivot elem kiválasztásának módja nem befolyásolja az algoritmus hatékonyságát.

A. Yes

B. No

Explanation: A tanulmányi anyag egyértelműen kimondja, hogy „Ennek az elemnek [a pivot] a megválasztása kulcsfontosságú az algoritmus hatékonysága szempontjából.” Ez azt jelenti, hogy a pivot kiválasztásának módja igenis befolyásolja a hatékonyságot, nem pedig nem.

Question 2: A mellékelt tananyag alapján mi jellemzi a Gyorsrendezés algoritmus „helyben rendezés” elvét?

A. Minimális extra memóriát használ, kivéve a rekurzív verem tárolására szolgáló részt.

B. Az elemek cseréje és mozgatása közvetlenül a bemeneti tömbben történik.

C. A rendezéshez mindig egy teljesen új tömböt hoz létre.

D. A felosztási lépés során ideiglenes listákat használ, amelyek mérete meghaladhatja az eredeti tömb méretét.

Explanation: A tanulmányi anyag szerint a „helyben rendezés” elve azt jelenti, hogy a Gyorsrendezés minimális extra memóriát használ (a rekurzív verem kivételével). Ezen felül az elemek cseréje és mozgatása közvetlenül a bemeneti tömbben történik, ami hatékony memóriahasználatot eredményez. A harmadik és negyedik opcióban leírtak ellentmondanak ennek a megállapításnak, mivel azok jelentős extra memóriaigényre utalnának.

Question 3: Ha rendezett adatokon alkalmazzuk a Gyorsrendezést, és mindig az első vagy utolsó elemet választjuk pivotnak, az a legrosszabb esethez vezethet.

A. Yes

B. No

Explanation: Az első vagy utolsó elem pivotként való választása a legrosszabb esethez vezethet, ha a bemeneti adatok már rendezettek vagy majdnem rendezettek. Ilyenkor az egyik al-lista üres lesz, a másik pedig majdnem az eredeti méretű.

Question 4: A Gyorsrendezés pivot elhelyezése során a végső lépésben az A[i] elemet cseréljük fel az A[jobb] elemmel, hogy a pivot a helyére kerüljön.

A. Yes

B. No

Explanation: A tanulmányi anyag szerint a pivot elhelyezésekor az iteráció végén az A[i + 1] és az A[jobb] elemeket cseréljük fel. Az `i` értéke 4, így `A[i + 1]` az `A[5]`-ös indexű elem.

Question 5: A mellékelt tananyag alapján miért előnyös véletlenszerűen kiválasztott elemet használni pivotként a Gyorsrendezés algoritmusban?

A. Mert garantálja, hogy a pivot mindig a lista mediánja lesz.

B. Mert csökkenti annak valószínűségét, hogy a legrosszabb eset előforduljon rendezett vagy majdnem rendezett adatok esetén.

C. Mert minden esetben O(n log n) időkomplexitást biztosít, kizárva az O(n²) lehetőséget.

D. Mert a legrosszabb eset gyakrabban fordul elő, de az algoritmus mégis gyorsabb.

Explanation: A tananyag szerint 'Egy véletlenszerűen kiválasztott elem pivotként való használata csökkenti annak valószínűségét, hogy a legrosszabb eset előforduljon rendezett vagy majdnem rendezett adatok esetén. Bár a legrosszabb eset még mindig lehetséges, annak valószínűsége rendkívül alacsony.' Ezért a második opció a helyes. A többi opció ellentmond a tananyagnak.