Sortowanie szybkie

Sortowanie szybkie
Rodzaj	Sortowanie
Struktura danych	Różne
	Złożoność
Czasowa	; pesymistycznie:
Pamięciowa	zależnie od implementacji

Sortowanie szybkie (ang. quicksort) – jeden z popularnych algorytmów sortowania działających na zasadzie „dziel i zwyciężaj”^[1].

Sortowanie szybkie (ang. QuickSort) zostało wynalezione w 1962 przez C.A.R. Hoare’a^[2].

Algorytm sortowania szybkiego jest wydajny: jego średnia złożoność obliczeniowa jest rzędu $O(n\log n)$ ^[1]. Ze względu na szybkość i prostotę implementacji jest powszechnie używany. Jego implementacje znajdują się w bibliotekach standardowych wielu środowisk programowania^[3]^[4].

↑ ^a ^b Thomas H. Cormen, Charles E. Leiserson, Ronald. R. Rivest: Wprowadzenie do algorytmów. Warszawa: Wydawnictwa Naukowo-Techniczne, 1997, 1998, s. 186–205. ISBN 83-204-2317-1.
↑ C.A.R. Hoare: Quicksort. Computer Journal, Vol. 5, 1, 10–15 (1962).
↑ Uwaga dot. implementacji algorytmu Quicksort w funkcji sort() języka PHP: PHP: sort - Manual. [dostęp 2014-03-28]. (ang.).
↑ Opis funkcji qsort z biblioteki standardowej języka C++: qsort - C++ Reference. [dostęp 2014-03-28]. (ang.).

[CLR-1] Thomas H. Cormen, Charles E. Leiserson, Ronald. R. Rivest: Wprowadzenie do algorytmów. Warszawa: Wydawnictwa Naukowo-Techniczne, 1997, 1998, s. 186–205. ISBN 83-204-2317-1.

[Hoare-2] C.A.R. Hoare: Quicksort. Computer Journal, Vol. 5, 1, 10–15 (1962).

[3] Uwaga dot. implementacji algorytmu Quicksort w funkcji sort() języka PHP: PHP: sort - Manual. [dostęp 2014-03-28]. (ang.).

[4] Opis funkcji qsort z biblioteki standardowej języka C++: qsort - C++ Reference. [dostęp 2014-03-28]. (ang.).

[1]

[2]

[3]

[4]

Sortowanie szybkie

From Wikipedia, the free encyclopedia · View on Wikipedia