Mathematical Analysis of Sorting and Searching Algorithms

This project is devoted to the analysis of computer algorithms for the sorting and searching of data. In such a mathematically founded analysis one tries to describe the average running time of the examined algorithms. Thereby one studies the time-consuming operations, that describe the so called "costs" (time is money) of an algorithm. As examples for such time-consuming operations are mentioned here parameters like "number of comparisons", "number of rotations" and "number of recursive calls". On the one hand such an analysis gives the user a scientifically well founded aid, that is not based on pure empirical examinations, to make the right decision in selecting the optimal algorithm for his given problem. On the other hand such an analysis gives the researcher a deeper insight how an algorithm works and therefore such studies can help to improve the efficiency of existing algorithms. In this project a lot of concrete algorithms and data structures were analysed, whereby methods of different mathematical branches like combinatorics, algebra, probability theory and analysis were used. The results of these studies were written down in a number of papers, that were published in scientific journals of mathematical computer science and combinatorics. Within the project also two international cooperations with French resp. Spanish researchers were established, that lead to two collaborating papers. It follows now a short description of results of this project: In statistical inference it is often desired to construct order statistics for several elements for data arrays of arbitrary size. One algorithm that is suitable for such a problem is Multiple Quickselect and is based on the widespread sorting algorithm "Quicksort". Important parameters of this algorithm were analysed here in detail. Priority trees are a data structure for the administration of priority queues. There exist applications of priority queues e. g. in operating systems like job scheduling or resource management. Here we analysed several parameters of this structure. Variants of binary search trees are among the most important data structures in computer science. The performance of several important algorithms is closely related to the number of descendants resp. ascendants of a certain element in a search tree. These parameters were therefore studied here. One way to improve the speed of retrieval of data stored in the nodes of a binary search tree is a method called "fringe balancing". The construction costs of these trees are determined by the here required "rotations" of elements and this parameter were analysed. In many applications such as Geographical Information Systems, databases, computer graphics, and statistical data analysis, the need frequently arises to maintain multidimensional records. Here we analysed data structures (so called multidimensional search trees), that are suited for that.