Test z Sortowanie przez wstawianie (insertion sort)

Pytanie 1: Symulacja sortowania przez wstawianie jest przydatna głównie do zrozumienia ogólnej zasady działania algorytmów sortowania, ale nie dostarcza szczegółowych informacji o zmianie złożoności czasowej w zależności od charakterystyki danych wejściowych.

A. Tak

B. Nie

Wyjaśnienie: Symulacja sortowania przez wstawianie jest niezwykle pomocna w zrozumieniu mechaniki algorytmu krok po kroku oraz pozwala utrwalić zrozumienie, kiedy sortowanie przez wstawianie jest efektywne, a kiedy nie, oraz jak jego złożoność czasowa zmienia się w zależności od charakterystyki danych wejściowych. Obserwacja liczby porównań i przesunięć dla różnych układów początkowych danych (posortowane, odwrócone, losowe, prawie posortowane) jest kluczowym aspektem korzystania z symulacji.

Pytanie 2: Sortowanie przez wstawianie jest często szybsze niż quicksort dla małych zbiorów danych.

A. Tak

B. Nie

Wyjaśnienie: Zaletą sortowania przez wstawianie jest jego efektywność dla małych zbiorów danych. Dla n rzędu kilkudziesięciu elementów, sortowanie przez wstawianie jest często szybsze niż bardziej złożone algorytmy, takie jak quicksort, ze względu na mniejsze stałe współczynniki i brak narzutu rekurencji.

Pytanie 3: Co sprawia, że algorytm sortowania przez wstawianie jest stabilny?

A. W pętli wewnętrznej elementy są przesuwane tylko wtedy, gdy są ściśle większe od klucza, a klucz jest wstawiany po elementach o równej wartości.

B. W pętli wewnętrznej elementy są przesuwane, jeśli są większe lub równe kluczowi, co zapewnia odpowiednią pozycję dla klucza.

C. Algorytm jest stabilny, ponieważ sortuje elementy w miejscu, nie wymagając dodatkowej pamięci.

D. Sortowanie przez wstawianie zawsze działa w czasie liniowym, gdy dane są posortowane, co czyni go stabilnym.

Wyjaśnienie: Algorytm sortowania przez wstawianie jest stabilny, ponieważ w pętli wewnętrznej elementy są przesuwane tylko wtedy, gdy są ściśle większe od klucza. Jeśli element A[j] jest równy kluczowi, pętla wewnętrzna zatrzymuje się, a klucz jest wstawiany po tym elemencie. Dzięki temu zachowywana jest pierwotna względna kolejność elementów o równych wartościach.

Pytanie 4: Które z poniższych stwierdzeń dotyczących złożoności czasowej algorytmu sortowania przez wstawianie są zgodne z dostarczonym materiałem do nauki?

A. W najlepszym przypadku, gdy tablica jest już posortowana, złożoność czasowa wynosi O(n).

B. W najgorszym przypadku, na przykład dla tablicy posortowanej w odwrotnej kolejności, złożoność czasowa wynosi O(n²).

C. Złożoność czasowa dla średniego przypadku dla losowo uporządkowanych danych jest również proporcjonalna do O(n²).

D. Dla dużych zbiorów danych o złożoności O(n²) algorytm jest bardzo efektywny, ponieważ ma małe stałe współczynniki.

Wyjaśnienie: Materiał do nauki jasno wskazuje, że w najlepszym przypadku (tablica już posortowana lub prawie posortowana) złożoność czasowa wynosi O(n), co potwierdza opcja 0. Opcja 1 jest poprawna, ponieważ materiał stwierdza, że najgorszy przypadek (np. tablica posortowana w odwrotnej kolejności) ma złożoność O(n²). Opcja 2 jest również poprawna, ponieważ materiał podaje, że dla losowo uporządkowanych danych, średnia liczba porównań i przesunięć jest proporcjonalna do n², czyli O(n²). Opcja 3 jest nieprawidłowa. Materiał wskazuje, że ze względu na złożoność O(n²) algorytm jest 'niepraktyczny dla dużych tablic', a jego efektywność dla małych zbiorów danych wynika z małych stałych współczynników, nie zaś dla dużych zbiorów z O(n²).

Pytanie 5: W najgorszym przypadku sortowania, liczba porównań jest proporcjonalna do logarytmu z liczby elementów n.

A. Tak

B. Nie

Wyjaśnienie: W najgorszym przypadku sortowania (gdy tablica jest posortowana w odwrotnej kolejności), element klucz musi być porównany ze wszystkimi elementami w posortowanej części. Liczba porównań sumuje się do 1 + 2 + ... + (n-1), co jest równe n(n-1)/2. Jest to złożoność kwadratowa, oznaczana jako O(n²), a nie logarytmiczna.