The Quicksort process

被引：7

作者：

Ragab, Mahmoud ^{[1
]}

Roesler, Uwe ^{[2
]}

机构：

[1] Al Azhar Univ, Fac Sci, Dept Math, Cairo 11884, Egypt

[2] Christian Albrechts Univ Kiel, Math Seminar, D-24098 Kiel, Germany

来源：

STOCHASTIC PROCESSES AND THEIR APPLICATIONS | 2014年 / 124卷 / 02期

关键词：

Sorting; Quicksort; Divide and conquer algorithm; Random algorithm; Running time analysis; Stochastic process; Cadlag functions; Asymptotics; Skorodhod metric;

D O I：

10.1016/j.spa.2013.09.014

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

Quicksort on the fly returns the input of n reals in increasing natural order during the sorting process. Correctly normalized the running time up to returning the l-th smallest out of n seen as a process in 1 converges weakly to a limiting process with path in the space of cadlag functions. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：1036 / 1054

页数：19

共 18 条

[1]

[Anonymous], 1998, SORTING SEARCHING

[2]

Billingsley P., 1968, CONVERGE PROBAB MEAS

[3] Asymptotic distribution theory for Hoare's selection algorithm [J].

Grubel, R ;

Rosler, U .

ADVANCES IN APPLIED PROBABILITY, 1996, 28 (01) :252-269

[4]

Hoare C. A., 1961, Communications of the ACM, V4, P321, DOI DOI 10.1145/366622.366644

[5] QUICKSORT [J].

HOARE, CAR .

COMPUTER JOURNAL, 1962, 5 (01) :10-&

[6]

Knof D, 2012, DISCRETE MATH THEOR, V14, P129

[7]

Martinez C., 2001, SIAM Journal on Computing, V31, P683, DOI 10.1137/S0097539700382108

[8]

Martinez C., 2004, PROC 6 ACMSIAM WORKS, P224

[9] A LIMITING DISTRIBUTION FOR QUICKSORT [J].

REGNIER, M .

RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS, 1989, 23 (03) :335-343

[10]

[No title captured]

← 1 2 →