W tym artykule przyjrzymy się zaawansowanej analizie złożoności obliczeniowej bardzo popularnego algorytmu sortującego o nazwie QuickSort. Zbadamy nie tylko złożoność pesymistyczną, ale również złożoność optymistyczną i oczekiwaną. Algorytm QuickSort jest ciekawym przypadkiem ze względu na to, że na pozór wydaje się być algorytmem wolnym, ale w praktyce jest to jedna z najszybszych metod sortowania...

Niektóre zagadnienia poruszane w tym artykule:

• Opis algorytmu;
• Złożoność pesymistyczna;
• Złożoność optymistyczna;
• Ciekawy przykład;
• Złożoność oczekiwana.

Artykuł pochodzi magazynu Programista nr 77 (10/2018). Jest to wydanie z przełomu grudnia 2018 r. i stycznia 2019 r. Szczegółowy spis treści: https://programistamag.pl/programista-10-2018-77/

Autorem artykułu jest Piotr Jastrzębski. Inżynier oprogramowania z dziesięcioletnim stażem. Aktualnie pracuje nad rozproszoną bazą danych NoSQL o nazwie Scylla. Wcześniej rozwijał real-time trading system w londyńskim City oraz pracował nad systemem Android w firmie Google. Absolwent informatyki na Uniwersytecie Warszawskim.