Sir Charles Antony Richard Hoare (Tony Hoare, ur. 11 stycznia 1934 w Kolombo, Sri Lanka)
Wiadomości podstawowe
Podstawowa wersja algorytmu Quicksort została wynaleziona w latach 60-tych przez angielskiego informatyka, profesora Tony`ego Hoare`a. Algorytm jest popularny, ponieważ nietrudno go zaimplementować, działa sprawnie na danych różnego typu i często zużywa mniej zasobów pamięciowych niż jakikolwiek inny algorytm.
Algorytm sortowania szybkiego działa na zasadzie „dziel i zwyciężaj” (ang. divide and conquer). Zasadę tą możemy opisać w następujący sposób:
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
Działanie algorytmu opiera się na dzieleniu tablicy na dwie części, które następnie sortowane są niezależnie. Warto zaznaczyć, iż początkowy porządek elementów w wejściowym zbiorze danych ma wpływ na to, jak będzie przebiegał podział. Należy wiedzieć, że to właśnie proces podziału jest sednem metody.