Dynamic Behavior of Simple Insertion Sort Algorithm

Issue title: SPECIAL ISSUE ON CONCURRENCY SPECIFICATION AND PROGRAMMING (CS&P 2005) Ruciane-Nide, Poland, 28–30 September 2005

Article type: Research Article

Authors: Grabowski, Franciszek | Strzalka, Dominik

Affiliations: Rzeszow University of Technology, Department of Distributed Systems, ul. W.Pola 2, 35-959 Rzeszow, Poland. E-mails: [email protected], [email protected]

Abstract: This paper deals with new analytical and experimental aspects of influence of data structure and algorithm on sort dynamics. Traditional analysis of data structure-algorithm interface which based on computational complexity is incomplete because do not considers of dynamical effects in area between extremely best and worst cases of computing time. The main aim of this paper are investigations of the impact of long-term dependencies in data structure on sort efficiency. This approach treats interface data structure-algorithm as the complex system in opposition to the classical computational analysis which treats this interface as simple deterministic system. This new approach makes possibilities to determine power spectral density of sorting process and test the existence of 1/f noise in this process which in fact is not noise but reflects the intrinsic dynamic (data flow disturbances inside system) of selforganized computer system. The idea presented in this paper shows how complex system behavior provide a good perspective to analysis of whole computer system as well.

Keywords: insertion sort, dynamics, 1/f noise

Journal: Fundamenta Informaticae, vol. 72, no. 1-3, pp. 155-165, 2006