ID: 2734
Algorytmy
Łatwe
Źródło: Arkusze CKE
Który algorytm sortowania opiera się na metodzie "dziel i zwyciężaj"?
Warianty odpowiedzi
-
A
Sortowanie przez wybór
-
B
Sortowanie szybkie (QuickSort)
-
C
Sortowanie przez wstawianie
-
D
Sortowanie bąbelkowe
Wyjaśnienie
Strategia dziel i zwyciężaj polega na rozbijaniu jednego dużego i trudnego problemu na mniejsze, łatwiejsze do rozwiązania części.
W przypadku QuickSorta wygląda to tak, że wybieramy z tablicy jeden element nazywany pivotem, który służy jako punkt odniesienia.
Następnie dzielimy całą tablicę na dwie mniejsze części. W jednej umieszczamy elementy mniejsze od pivota, a w drugiej większe.
Ten proces powtarzamy rekurencyjnie dla powstałych podtablic, aż wszystkie elementy znajdą się na swoich miejscach. Dokładnie na tym polega ta metoda.