Fiszki do Sortowanie przez scalanie (merge sort)
Sortowanie przez Scalanie (Merge Sort): Opracowanie i Przykład
Dotknij, aby odwrócić · Przesuń, aby nawigować
Sortowanie przez scalanie
24 fiszek
Fiszka 1
Pytanie: Czym jest sortowanie przez scalanie (Merge Sort) i do jakiej kategorii algorytmów należy?
Odpowiedź: Sortowanie przez scalanie to jeden z najbardziej efektywnych algorytmów sortowania, należący do algorytmów porównawczych.
Fiszka 2
Pytanie: Jaka jest główna zaleta sortowania przez scalanie pod względem złożoności czasowej?
Odpowiedź: Jego główną zaletą jest gwarantowana złożoność czasowa O(n log n) w każdym przypadku (najgorszym, średnim i najlepszym).
Fiszka 3
Pytanie: Na jakim paradygmacie opiera się sortowanie przez scalanie?
Odpowiedź: Algorytm ten opiera się na paradygmacie „dziel i zwyciężaj” (ang. Divide and Conquer).
Fiszka 4
Pytanie: Na czym polega paradygmat „dziel i zwyciężaj”?
Odpowiedź: Polega na rozwiązywaniu problemu poprzez rozbicie go na mniejsze, łatwiejsze do rozwiązania podproblemy tego samego typu, a następnie łączenie rozwiąz
Fiszka 5
Pytanie: Jakie są trzy główne kroki paradygmatu „dziel i zwyciężaj” w kontekście sortowania przez scalanie?
Odpowiedź: Dzielenie (Divide), Zwyciężanie (Conquer), Scalanie (Combine).
Fiszka 6
Pytanie: Opisz krok 'Dzielenie' w algorytmie sortowania przez scalanie.
Odpowiedź: Problem sortowania listy n elementów jest dzielony na dwa podproblemy sortowania list o około n/2 elementach. Proces ten jest kontynuowany rekurencyjn
Fiszka 7
Pytanie: Kiedy lista w procesie 'Dzielenia' jest uznawana za posortowaną?
Odpowiedź: Lista składająca się z jednego elementu jest z definicji posortowana.
Fiszka 8
Pytanie: Opisz krok 'Zwyciężanie' w algorytmie sortowania przez scalanie.
Odpowiedź: Podproblemy są rozwiązywane rekurencyjnie. 'Rozwiązaniem' najmniejszego podproblemu (listy jednoelementowej) jest po prostu ta sama lista, ponieważ je
Fiszka 9
Pytanie: Opisz krok 'Scalanie' w algorytmie sortowania przez scalanie.
Odpowiedź: Posortowane podlisty są łączone (scalane) w taki sposób, aby utworzyć jedną, większą, posortowaną listę.
Fiszka 10
Pytanie: Co jest warunkiem bazowym rekurencji w procesie dzielenia w Merge Sort?
Odpowiedź: Warunkiem bazowym rekurencji jest moment, gdy uzyskamy podtablice zawierające tylko jeden element, które są uznawane za posortowane.