Przykładem algorytmu typu dziel i zwyciężaj jest?
Przykładem algorytmu typu dziel i zwyciężaj jest?
Wyjaśnienie i uzasadnienie dydaktyczne
Poprawna odpowiedź: A
Uzasadnienie i szersze wyjaśnienie:
Quicksort (sortowanie szybkie) jest klasycznym przykładem algorytmu implementującego strategię „dziel i zwyciężaj” (divide and conquer). Jego działanie polega na:
- Dziel: Wyborze elementu rozdzielającego (tzw. piwota) i podziale tablicy na dwie części – elementy mniejsze od piwota i elementy większe od piwota.
- Zwyciężaj: Rekurencyjnym sortowaniu obu powstałych podtablic.
- Połącz: Ten krok jest trywialny, ponieważ po posortowaniu podtablic cała tablica jest już posortowana.
Dlaczego pozostałe odpowiedzi są nieprawidłowe?
- B. algorytm Kruskala i C. algorytm Dijkstry: Są to algorytmy zachłanne (greedy). W każdym kroku podejmują one decyzję, która wydaje się lokalnie najlepsza, w nadziei na znalezienie globalnego optimum (np. dodanie najkrótszej krawędzi w algorytmie Kruskala).
- D. insert-sort (sortowanie przez wstawianie): Jest to prosty algorytm, który działa przyrostowo. Buduje on posortowaną tablicę, wstawiając po kolei każdy element z nieposortowanej części w odpowiednie miejsce.
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
- Sortowanie przez wstawianie (Insertion Sort)Algorytm sortowania budujący posortowany ciąg element po elemencie poprzez wstawianie każdego nowego elementu na właściwą pozycję.
- 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 szybkie (Quicksort)Wydajny algorytm sortowania oparty na paradygmacie 'dziel i zwyciężaj', wykorzystujący element osiowy (pivot) do partycjonowania tablicy.
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: