ISSN:
1436-5057
Keywords:
68 E 05
;
Sorting
;
probabilistic analysis
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Bei dem distributiven Sortierverfahren von Dobosiewicz wird sowohl das Intervall zwischen Minimum und Median als auch das Intervall zwischen Median und Maximum inn/2 Teilintervalle gleicher Länge zerlegt; die Prozedur wird dann rekursiv in jedem, mindestens vier Zahlen enthaltenden Teilintervall angesetzt. In dieser Arbeit werden einige Aspekte des Verfahrens verfeinert und erweitert. Insbesondere wird das asymptotisch lineare Verhalten unter verschiedene Wahrscheinlichkeits-Annahmen untersucht.
Notes:
Abstract In the distributive sorting method of Dobosiewicz, both the interval between the minimum and the median of the numbers to be sorted and the interval between the median and the maximum are partitioned inton/2 subintervals of equal length; the procedure is then applied recursively on each subinterval containing more than three numbers. We refine and extend previous analyses of this method, e.g., by establishing its asymptotic linear behaviour under various probabilistic assumptions.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02251234
Permalink
