Który stabilny algorytm sortowania ma złożoność liniową O(n)?
Który stabilny algorytm sortowania ma złożoność liniową O(n)?
Wyjaśnienie i uzasadnienie dydaktyczne
Poprawna odpowiedź to D. Sortowanie przez zliczanie (Counting Sort) jest algorytmem o złożoności liniowej O(n+k) i jest stabilne. Nie opiera się ono na porównywaniu elementów, lecz na zliczaniu ich wystąpień.
Wyjaśnienie pozostałych opcji:
- Sortowanie przez wstawianie i bąbelkowe mają średnią złożoność O(n^2).
- Sortowanie szybkie (Quick Sort) ma średnią złożoność O(n \log n), ale w standardowej implementacji nie jest stabilne.
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ę.
- Sortowanie przez zliczanie (Counting Sort) i Kubełkowe (Bucket Sort)Nieporównaniowe algorytmy sortowania o liniowej złożoności czasowej O(n+k), opierające się na zliczaniu wystąpień kluczy lub podziale liczb na kubełki w znanym przedziale.
- 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: