Przedstawiona na obrazie idea sortowania odnosi się do sortowania
Przedstawiona na obrazie idea sortowania odnosi się do sortowania
Wyjaśnienie i uzasadnienie dydaktyczne
Poprawna odpowiedź: A
Uzasadnienie i szersze wyjaśnienie:
Przedstawiony schemat graficzny jest klasyczną wizualizacją algorytmu sortowania przez scalanie (Merge Sort). Algorytm ten działa w oparciu o strategię „dziel i zwyciężaj” i składa się z dwóch głównych faz, które są widoczne na obrazku:
- Faza podziału (niebieskie strzałki): Nieposortowana tablica jest rekurencyjnie dzielona na dwie połowy tak długo, aż powstaną jednoelementowe (czyli z definicji posortowane) podtablice.
- Faza scalania (pomarańczowe strzałki): Posortowane podtablice są rekurencyjnie łączone (scalane) w większe, również posortowane tablice, aż do uzyskania jednej, w pełni posortowanej tablicy wynikowej.
Dlaczego pozostałe odpowiedzi są nieprawidłowe?
- B. kubełkowego: Działa poprzez podział elementów na określoną liczbę „kubełków”, sortowanie każdego kubełka z osobna i połączenie wyników.
- C. przez wybieranie: W każdym kroku znajduje najmniejszy element w nieposortowanej części i zamienia go z pierwszym elementem tej części.
- D. bąbelkowego: Polega na wielokrotnym porównywaniu i zamienianiu sąsiednich elementów.
Chcesz poćwiczyć całą kwalifikację INF.04?
Egzamin próbny na czas, nauka działami, losowe pytanie albo przegląd całej bazy — wszystko w przeglądarce i bez zakładania konta.
Pojęcia z tego pytania
- Paradygmat Dziel i Zwyciężaj (Divide and Conquer)Wiodąca technika projektowania algorytmów polegająca na rekurencyjnym podziale problemu na mniejsze podproblemy tego samego typu, ich rozwiązaniu i scaleniu wyników.
- Sortowanie przez scalanie (Merge Sort)Stabilny algorytm sortowania dzielący tablicę na połowy, sortujący je rekurencyjnie i scalający dwa posortowane ciągi w czasie O(n log n).
- Pojęcie i Cechy AlgorytmuUporządkowany, skończony i jednoznaczny ciąg instrukcji i kroków postępowania prowadzący do rozwiązania określonego problemu obliczeniowego dla poprawnych danych wejściowych.
Podobne pytania z działu „Algorytmy sortowania i wyszukiwania”
Ten sam obszar materiału z kwalifikacji INF.04. W całej bazie znajdziesz 23 pytań z tego działu.
- #93
Aby zaprojektować zestaw danych do zainicjowania algorytmu sortowania bąbelkowego tablicy, należy zastosować przynajmniej typy:
- #103
Metoda poszukiwań w tablicach posortowanych, która polega na podzieleniu tablicy na kilka bloków i wyszukaniu liniowym tylko w tym bloku, w którym docelowy element może się znajdować, w języku angielskim nosi nazwę
- #129
Który z wymienionych algorytmów działających na tablicy jednowymiarowej ma złożoność obliczeniową O(n2)?
- #143
Strategia budowania algorytmu poprzez podział na dwa lub więcej mniejszych podproblemów tak długo, aż fragmentu staną się proste do bezpośredniego rozwiązania jest metodą:
- #144
Z tabeli przedstawiającej złożoność obliczeniową algorytmów sortowania na dowolnym, dużym, zbiorze wejściowym (ponad 100 elementów) wynika, że najszybszą metodą jest algorytm sortowania: