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

Algorytm quicksort

VPS Starter Arubacloud
0 głosów
477 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 Maniak (56,900 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ź 373 wizyt
pytanie zadane 6 stycznia 2021 w Python przez maciej12 Nowicjusz (120 p.)
0 głosów
1 odpowiedź 4,708 wizyt
+1 głos
1 odpowiedź 187 wizyt
pytanie zadane 27 czerwca 2020 w C i C++ przez Marcinuq Użytkownik (640 p.)

92,454 zapytań

141,262 odpowiedzi

319,089 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...