• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Algorytm quicksort

0 głosów
160 wizyt
pytanie zadane 23 kwietnia 2020 w C i C++ przez Rrafał98 Nowicjusz (240 p.)

Mam pewne pytanie.

Znalazłem w internecie taki schemat sortowania przez scalanie. Otóż zastanawiam się czy quicksort wykorzystuje scalanie dwóch ciągów uporządkowanych. W quicksort występuje "dzielenie" problemu na mniejsze. Ale czy quicksort wykorzystuje scalanie posortowanych ciągów?

1 odpowiedź

+1 głos
odpowiedź 23 kwietnia 2020 przez Whistleroosh Nałogowiec (29,580 p.)
Quicksort podobnie jak merge sort rozbija tablicę na coraz mniejsze części, lecz nie wykonuje on potem scalania. Jak zapewne wiesz, quicksort działa tak, że znajdujesz sobie pivot i względem niego sortujesz pewną część tablicy i potem znowu powtarzasz to rekurencyjnie dla części na prawo od pivota i na lewo. Musisz zauważyć, że gdy skończymy rozważać jakiś pivot, to będzie się on już znajdował na swojej właściwej pozycji w posortowanym ciągu. Czyli jak rozważymy każdy element jako pivot to nie ma już potrzeby scalać tego wszystkiego.

Podobne pytania

0 głosów
1 odpowiedź 131 wizyt
0 głosów
1 odpowiedź 4,233 wizyt
+1 głos
1 odpowiedź 104 wizyt
pytanie zadane 27 czerwca 2020 w C i C++ przez Marcinuq Początkujący (480 p.)
Porady nie od parady
Zadając pytanie postaraj się o poprawną pisownię i czytelne formatowanie tekstu.Kompozycja

85,082 zapytań

133,883 odpowiedzi

296,819 komentarzy

56,216 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...