Test z Sortowanie szybkie (quicksort)

Pytanie 1: Wybór pierwszego lub ostatniego elementu jako pivota w algorytmie Quicksort zawsze gwarantuje złożoność czasową O(n log n), nawet w przypadku posortowanych danych.

A. Tak

B. Nie

Wyjaśnienie: Wybór pierwszego lub ostatniego elementu jako pivota prowadzi do złożoności czasowej O(n²) dla już posortowanych lub odwrotnie posortowanych danych, a nie gwarantuje złożoności O(n log n).

Pytanie 2: Niewłaściwe zarządzanie indeksami `i` i `j` podczas implementacji partycjonowania w Quicksortcie może prowadzić do nieskończonych rekurencji lub nieprawidłowego sortowania.

A. Tak

B. Nie

Wyjaśnienie: Zgodnie z materiałami, 'Błędy w implementacji partycjonowania' obejmują niewłaściwe zarządzanie indeksami `i` i `j`, co 'może prowadzić do nieskończonych rekurencji lub nieprawidłowego sortowania'.

Pytanie 3: Zgodnie z podanym przykładem partycjonowania Lomuto dla listy `[7, 2, 1, 6, 8, 5, 3, 4]`, jaki jest stan listy po wykonaniu pętli iterującej przez indeks `j`, ale przed umieszczeniem pivota na właściwej pozycji?

A. [2, 1, 3, 4, 8, 5, 7, 6]

B. [2, 1, 7, 6, 8, 5, 3, 4]

C. [2, 1, 3, 6, 8, 5, 7, 4]

D. [2, 1, 3, 6, 8, 5, 7, 4]

Wyjaśnienie: W podanym przykładzie partycjonowania Lomuto, po zakończeniu pętli iterującej przez indeks 'j', wartość indeksu 'i' wynosi 2. Oznacza to, że elementy mniejsze lub równe pivotowi (`4`) zostały przesunięte na początek listy. Ostatnia zamiana w pętli dotyczyła `element[2]` (`7`) i `element[6]` (`3`), dając listę `[2, 1, 3, 6, 8, 5, 7, 4]` (pivot `4` nadal jest na ostatniej pozycji). Dopiero po tej pętli następuje zamiana `element[i + 1]` (czyli `element[3]`, wartość `6`) z pivotem (`element[7]`, wartość `4`), co daje finalną listę `[2, 1, 3, 4, 8, 5, 7, 6]`.

Pytanie 4: Które z poniższych stwierdzeń najlepiej opisują podstawową ideę algorytmu Quicksort?

A. Wybór elementu zwanego pivotem, który dzieli listę na dwie podlisty.

B. Przestawianie elementów tak, aby wszystkie mniejsze od pivota były po jego lewej stronie, a większe po prawej.

C. Łączenie dwóch już posortowanych podlist w jedną posortowaną listę.

D. Rekurencyjne wywoływanie algorytmu dla podlist po obu stronach pivota.

Wyjaśnienie: Podstawowa idea algorytmu Quicksort opiera się na trzech głównych krokach: wyborze pivota, partycjonowaniu oraz rekurencji. Wybiera się pivot, następnie elementy są przestawiane (partycjonowanie) tak, aby mniejsze od pivota były po jego lewej stronie, a większe po prawej. Po tej operacji pivot znajduje się na swojej ostatecznej pozycji. Na koniec, algorytm jest rekurencyjnie wywoływany dla podlist po lewej i prawej stronie pivota. Opcja trzecia opisuje mechanizm algorytmów takich jak Scalanie (Merge Sort), a nie Quicksort, który nie scala jawnie podlist, lecz opiera się na umieszczeniu pivota we właściwej pozycji i rekurencyjnym sortowaniu pozostałych części.

Pytanie 5: Tematem do nauki jest Złożoność Czasowa.

A. Tak

B. Nie

Wyjaśnienie: Zagadnienie 'Złożoność Czasowa' jest wymienione w materiałach do nauki.