Long-range dependencies in quick-sort algorithm

Sorting is one of the most frequently used types of processing in computer systems. In presented approach sorting will be considered as an introduction of order into processed input task and algorithm as a physical system (responsible for computations). This analysis shows how the dependencies in processed tasks can influence the behavior of algorithm (or equivalently Turing machine). Normally, analysis of any algorithm behavior is done in terms of classical computational complexity. In this paper the rate of existence of long-term correlations in processing dynamics is calculated basing on Hurst coefficient.

---

Sortowanie jest jednym z najczęstszych wykorzystywanych typów przetwarzania w systemach komputerowych. W prezentowanym podejściu sortowanie będzie rozważane jako wprowadzenie porządku w przetwarzanym zadaniu wejściowym oraz algorytm jako fizyczny system (odpowiedzialny za obliczenia). Zazwyczaj analiza zachowania dowolnego algorytmu jest realizowana w kontekście klasycznej złożoności obliczeniowej. W niniejszej pracy istnienie zależności długoterminowych w dynamice przetwarzania jest wyznaczane w oparciu o współczynnik Hurst’a.