Long-range dependencies in quick-sort algorithm

• Autorzy: Dymora P. , Mazurek M. , Strzałka D.

Identyfikatory

DOI

10.12915/pe.2014.01.35

Warianty tytułu

PL

Zależności długoterminowe w algorytmie quick-sort

• Języki publikacji: EN

Abstrakty

EN

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.

PL

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.

Słowa kluczowe

EN

long-range dependence; quick-sort algorithm; Hurst factor; self-similarity

PL

zależności długoterminowe; algorytm szybkiego sortowania; współczynnik Hursta; samopodobieństwo

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2014
• Tom: R. 90, nr 1
• Strony: 149--152
• Opis fizyczny: Bibliogr. 13 poz., rys.

Twórcy

autor

Dymora P.

• Politechnika Rzeszowska, Zakład Systemów Rozproszonych, ul. W. Pola 2, 35-959 Rzeszów

autor

Mazurek M.

• Mirosław Mazurek, Politechnika Rzeszowska, Zakład Systemów Rozproszonych, ul. W. Pola 2, 35-959 Rzeszów

autor

Strzałka D.

• Politechnika Rzeszowska, Zakład Systemów Rozproszonych, ul. W. Pola 2, 35-959 Rzeszów

Bibliografia

• 1. Turing, A. M.: On computable numbers, with an application to the Entscheidungsproblem, Proc. of the London Mathematical Society, Series 2, 42 (1936), pp. 230–265. Errata appeared in Series 2, 43, pp. 544–546, 1937.
• 2. Eberbach E., Wegner P. Beyond Turing machines, Bulletin of the European Association for Theoretical Computer Science 81, pp. 279–304, 2003.
• 3. Bennett, Ch. H.: The Thermodynamics of Computation – a Review, Int. J. of Theor. Phys., vol. 21, No. 12, pp. 905–939, 1982.
• 4. Ch. Roth, Fundamental of logic design, Cengage Learning, (2009)
• 5. B. Strzałka, M. Mazurek, D. Strzałka: Queue Performance in Presence of Long-Range Dependencies – an Empirical Study, International Journal of Information Science, 2(4), pp. 47-53, (2012)
• 6. Grabowski F., Strzałka D. Computer engineering by non-extensive statistics approach. in: New technologies in computer networks. WKiŁ, Warsaw, 2006
• 7. Grabowski F., Strzałka D.: Limitations of asynchronous systems scalability, , Measurement, Automatics, Control, 53, pp. 6-9 (2007)
• 8. Grabowski F. Logistic equation of arbitrary order, Physica A: Statistical Mechanics and its Applications, Vol. 389, Issue 16, pp. 3081–3093, 2010
• 9. Hartmanis, J. and Stearns, R.E., On the Computational Complexity of Algorithms,. Trans. Am. Math. Soc., vol. 117 (5), 285-306, 1965
• 10. T. H. Cormen, Ch. E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms , MIT. Press, mcgraw- Hill Book Company, 1990
• 11. D. Knuth, The art of computer programming, Addison-Wesley, 1968
• 12. D. Strzałka, F. Grabowski: Towards possible non-extensive thermodynamics of algorithmic processing - statistical mechanics of insertion sort algorithm, International Journal of Modern Physics C, vol. 19 n. 9, pp. 1443–1458, (2008)
• 13. Strzałka, D. Processes in the computer system at the interface between data and simple insertion sort algorithm in terms of nonextensive statistics, PHD. Thesis, Gliwice, 2009.