4646

0(n log n). Zaletą tego sposobu jest to, iż wiele współczesnych języków programowania posiada w swoich bibliotekach funkcję sortującą qsort(), która wykorzystuje ten właśnie algorytm.

Wadą z kolei jest to, iż do otrzymania wartości jednego elementu musimy sortować cały zbiór danych.

W podanym poniżej algorytmie sortowania szybkiego wykorzystujemy funkcję Dziel_na_partycję(Z,tp, z*).

Funkcja ta dzieli partycję zbioru Z określoną dwoma indeksami z_p oraz z* na dwie mniejsze partycje. Zwraca indeks podziałowy i_v. Pierwsza partycja zawiera elementy od i_p do i_v - 1, a druga od z_v do z*. Elementy w partycji pierwszej są niewiększe od elementów w partycji drugiej.

ALGORYTM SZYBKIEGO SORTOWANIA I ZNAJDOWANIA MEDIANY:

Wejście:

n - liczba elementów w zbiorze Z

Z[] - tablica (n+1) elementowa odwzorowująca zbiór Z, w który sortujemy. Na pozycji Z[n] należy umieścić wartownika o wartości większej od każdego elementu zbioru.

Wyjście:

Mediana zbioru Z.

Zmienne pomocnicze:

iv    - zawiera pozycję elementu zwrotnego, Iv należy do C

v    - wartość elementu zwrotnego

i, j - indeksy w tablicy Z[J; i, j należy do C