Kwalifikacje w Zawodzie - Testy zawodowe online | Egzaminy Zawodowe

KWALIFIKACJA INF2 + INF3 - STYCZEŃ 2011



PYTANIE NR 25.
Przedstawiony algorytm w postaci listy kroków porządkuje ciąg n liczb od największej do najmniejszej metodą "przez wybór (Selection Sort). Ilu porównań wymaga, w najgorszym wypadku, porządkowanie tą metodą ciągu 4 liczb?
Ilustracja przedstawia fragment egzaminu zawodowego dla technika programisty, dotyczący algorytmu sortowania przez wybór
A.
B.
C.
D.
Wyjaśnienie poprawnej odpowiedzi:
W sortowaniu przez wybór w każdym przebiegu szuka się elementu skrajnego w nieposortowanej części.
Dla 4 liczb porównania to: 3 (dla i=1) + 2 (dla i=2) + 1 (dla i=3) = 6. Ogólnie algorytm wykonuje zawsze n(n-1)/2 porównań, niezależnie od danych i kierunku sortowania.

Pełne wyjaśnienie:

Selection Sort (sortowanie przez wybór) działa iteracyjnie: w każdej iteracji wybiera element skrajny (najmniejszy lub największy) z nieposortowanej części i umieszcza go na właściwej pozycji poprzez zamianę. Kluczowe jest to, że w danym przebiegu trzeba porównać kolejne elementy, aby znaleźć minimum/maksimum.

Dla ciągu 4 liczb algorytm wykona n-1 = 3 przebiegi:

  • W 1. przebiegu przeszukuje 4 elementy, więc aby znaleźć element skrajny, musi wykonać 3 porównania (porównujemy kandydatów na min/max wśród 4 wartości).
  • W 2. przebiegu pozostają 3 elementy nieposortowane, więc potrzeba 2 porównań.
  • W 3. przebiegu pozostają 2 elementy, więc potrzeba 1 porównania.

Suma porównań wynosi więc 3 + 2 + 1 = 6. To jest też wartość wynikająca z ogólnego wzoru: n(n-1)/2, czyli dla n=4: 4·3/2 = 6.

Dlaczego pozostałe propozycje są błędne?

  • "4 porównania" zaniża wynik, bo w pierwszym przebiegu już trzeba wykonać 3 porównania, a do tego dochodzą kolejne przebiegi.
  • "8 porównań" zawyża wynik; w Selection Sort liczba porównań dla n=4 jest stała i wynika z 3+2+1, nie ma tu dodatkowych porównań zależnych od ułożenia danych.
  • "10 porównań" odpowiadałoby innemu n (np. 5 elementów daje 5·4/2 = 10) albo błędnemu założeniu o większej liczbie przebiegów.

Wskazówka egzaminacyjna: jeśli pytanie dotyczy Selection Sort, najczęściej wystarczy policzyć sumę (n-1) + (n-2) + ... + 1. Kierunek sortowania (rosnąco/malejąco) zmienia znak porównania, ale nie zmienia liczby porównań.

Dodatkowe pytania

Dodatkowe pytania (FAQ):
Co to jest sortowanie przez wybór (Selection Sort)?
To prosty algorytm sortowania iteracyjnego. W każdym przebiegu wybiera element skrajny (najmniejszy lub największy) z nieposortowanej części i zamienia go z pierwszym elementem tej części. Wykonuje dokładnie n-1 przebiegów dla n elementów.
Jak policzyć liczbę porównań w Selection Sort dla n elementów?
W każdym przebiegu porównujesz elementy, aby znaleźć min/max w pozostałej części tablicy: (n-1) + (n-2) + ... + 1. To suma liczb od 1 do n-1, czyli n(n-1)/2. W Selection Sort liczba porównań nie zależy od ułożenia danych.
Dlaczego w Selection Sort liczba porównań nie zależy od danych wejściowych?
Bo algorytm zawsze wykonuje pełne przeszukanie nieposortowanego fragmentu, aby wybrać element skrajny. Niezależnie od tego, czy tablica jest już prawie posortowana, i tak porównuje kolejne elementy w tym fragmencie, zmienia się tylko wynik porównań, a nie ich liczba.
Czy sortowanie rosnące i malejące w Selection Sort ma inną liczbę porównań?
Nie. Zmienia się tylko warunek (szukanie minimum vs maksimum), ale w każdym przebiegu nadal trzeba porównać elementy nieposortowanej części. Dlatego liczba porównań pozostaje taka sama: n(n-1)/2 dla dowolnego kierunku sortowania.
Jakie są porównania krok po kroku dla 4 elementów w Selection Sort?
Dla 4 elementów są 3 przebiegi: w pierwszym trzeba wykonać 3 porównania, w drugim 2, w trzecim 1. Razem: 3+2+1=6. To najprostszy sposób liczenia bez używania wzoru ogólnego.
Co jest częstszą pułapką: porównania czy zamiany w Selection Sort?
Najczęściej myli się liczbę porównań z liczbą zamian. Selection Sort ma zwykle mało zamian (maksymalnie n-1), ale porównań zawsze jest dużo i jest ich stała liczba: n(n-1)/2. Na egzaminie trzeba czytać, o którą operację pytają.
Jak odróżnić Selection Sort od Insertion Sort w zadaniach egzaminacyjnych?
W Selection Sort w każdym przebiegu wybiera się min/max z pozostałej części i wykonuje jedną zamianę. W Insertion Sort element jest "wstawiany" w odpowiednie miejsce w już posortowanym fragmencie, a liczba porównań zależy mocno od danych. Jeśli pytanie mówi o szukaniu skrajnego elementu, to zwykle Selection Sort.
Kiedy Selection Sort ma sens w praktyce programistycznej?
Głównie dydaktycznie i dla bardzo małych zbiorów danych. Bywa też użyteczny, gdy koszt zamiany elementów jest istotny, bo wykonuje mało zamian (do n-1). W aplikacjach webowych zwykle stosuje się jednak wbudowane sortowania bibliotek, bo są szybsze dla większych danych.
Jaką złożoność czasową ma Selection Sort i co to oznacza?
Ma złożoność czasową rzędu n², bo wykonuje około n(n-1)/2 porównań. Oznacza to, że przy podwojeniu liczby elementów czas działania rośnie w przybliżeniu czterokrotnie. Dlatego algorytm nie nadaje się do dużych tablic w aplikacjach.
Jakie triki pomagają szybko policzyć 1+2+...+(n-1) na egzaminie?
Możesz użyć wzoru n(n-1)/2 albo skojarzenia z "trójkątem" liczb: dla n=4 to 1+2+3. Dla małych n często najszybciej jest wypisać składniki (3+2+1). Ważne, by nie pomylić n z (n-1) w podstawieniu.
info

Statystycznie 60% uczniów zna prawidłową odpowiedź. średnie

Specjaliści zwracają uwagę: "W sortowaniu przez wybór w każdym przebiegu szuka się elementu skrajnego w nieposortowanej części.Dla 4 liczb porównania to: 3 (dla i=1) + 2 (dla i=2) + 1 (dla i=3) = 6."

Źródła:

  • Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms" (CLRS), 3rd edition, Chapter 2 (analiza prostych sortowań, w tym liczby porównań)
  • Wikipedia: "Selection sort" https://en.wikipedia.org/wiki/Selection_sort - accessed 2026-03-05
  • GeeksforGeeks: "Selection Sort Algorithm" https://www.geeksforgeeks.org/selection-sort-algorithm-2/ - accessed 2026-03-05

Materiały:

  • Podręcznik/rozdział o algorytmach sortowania (Selection, Insertion, Bubble) z omówieniem liczby porównań i zamian
  • Ćwiczenia: ręczne prześledzenie Selection Sort dla n=3..6 i zapis liczby porównań w tabeli
  • Notatka/wzory: suma 1+2+...+(n-1) oraz n(n-1)/2 i kiedy je stosować
Zobacz też:

Aktualizacja pytania: 31.03.2026



Aktualizacja pytania: 31.03.2026
📡 Brak połączenia internetowego