R13XFHOJPLQJ3
Fotografia przedstawia spiralne elementy w fabryce. Są wysokie, identyczne. Stoją w jednym rzędzie.

I_R_W14_M27_C++ Metoda Quicksort

Źródło: Kelvyn Ornettte Sol Marte, domena publiczna.

Wśród uporządkowanych przedmiotów łatwiej jest znaleźć to, czego szukasz. W programach komputerowych porządek jest tak samo ważny, choć tutaj sprowadza się on przede wszystkim do posortowanych liczb. Jak uporządkować liczby? Oczywiście za pomocą algorytmów.

Sortowania używamy np. robiąc zakupy w sklepie internetowym, gdy układamy elementy zgodnie z rosnącą ceną. Chodzi jednak nie tylko o to, żeby dane zostały posortowane – równie ważne jest, by zadanie wykonać w możliwie najkrótszym czasie. Jak to zrobić? Możemy skorzystać z sortowania szybkiego.

Ćwiczenie na rozgrzewkę

Ćwiczenie 1
R1P1HF2CDXMAO
Algorytm "quick sort" wykorzystuje technikę: Możliwe odpowiedzi: 1. dziel i zwyciężaj, 2. porównań, 3. wyboru wartownika przed indeksem 0
Twoje cele
  • Przeanalizujesz pseudokod, który jest zapisem algorytmu sortowania szybkiego.

  • Omówisz czas działania algorytmu quick sort, w tym dla przypadku optymistycznego i pesymistycznego.

  • Zastosujesz algorytm sortowania przykładowej tablicy za pomocą algorytmu quick sort.

  • Wykonasz implementację algorytmu quick sort w języku ....