Algorytm
Algorytm sortowania szybkiego opiera się na strategii "dziel i zwyciężaj" (ang. divide and conquer), którą możemy krótko scharakteryzować w trzech punktach:
- DZIEL - problem główny zostaje podzielony na podproblemy
- ZWYCIĘŻAJ - znajdujemy rozwiązanie podproblemów
- POŁĄCZ - rozwiązania podproblemów zostają połączone w rozwiązanie problemu głównego
Idea sortowania szybkiego jest następująca:
DZIEL : | najpierw sortowany zbiór dzielimy na dwie części w taki sposób, aby wszystkie elementy leżące w pierwszej części (zwanej lewą partycją) były mniejsze lub równe od wszystkich elementów drugiej części zbioru (zwanej prawą partycją). |
ZWYCIĘŻAJ : | każdą z partycji sortujemy rekurencyjnie tym samym algorytmem. |
POŁĄCZ : | połączenie tych dwóch partycji w jeden zbiór daje w wyniku zbiór posortowany. |
Brak komentarzy:
Prześlij komentarz