Wskaż niestabilny algorytm sortowania
Wskaż niestabilny algorytm sortowania
Wyjaśnienie i uzasadnienie dydaktyczne
Poprawna odpowiedź: C
Uzasadnienie i szersze wyjaśnienie:
Stabilność algorytmu sortowania to właściwość, która gwarantuje, że elementy o równych wartościach (kluczach) zachowają swoją względną kolejność po posortowaniu. Oznacza to, że jeśli dwa takie same elementy występowały w zbiorze wejściowym w pewnej kolejności, to w zbiorze wyjściowym pojawią się w tej samej kolejności.
- Sortowanie szybkie (Quick Sort) jest klasycznym przykładem algorytmu niestabilnego. W standardowej implementacji, operacja partycjonowania (dzielenia tablicy względem elementu osiowego) może zamienić miejscami elementy o równej wartości, naruszając ich pierwotną kolejność.
Dlaczego pozostałe odpowiedzi są nieprawidłowe?
- A. sortowanie bąbelkowe: Jest algorytmem stabilnym. Podczas porównywania i zamiany sąsiednich elementów, równe elementy nigdy nie są zamieniane miejscami, więc ich kolejność zostaje zachowana.
- B. sortowanie przez wstawianie: Jest algorytmem stabilnym. Nowy element jest wstawiany na odpowiednie miejsce w już posortowanej części tablicy, ale nie „przeskakuje” przez elementy o równej wartości.
- D. sortowanie przez zliczanie: W swojej typowej implementacji jest algorytmem stabilnym. Jego konstrukcja pozwala na zachowanie pierwotnej kolejności równych 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
- 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 bąbelkowe (Bubble Sort)Prosty algorytm sortowania o złożoności O(n^2), wielokrotnie porównujący sąsiednie elementy i zamieniający je miejscami, jeśli są w złej kolejności.
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: