Almost sure convergence to the Quicksort process

Uwe Roesler

Stochastic Processes and their Applications, 2020, vol. 130, issue 9, 5290-5309

Abstract: The algorithm Partial Quicksort, introduced by Conrado Martínez, sorts the l smallest real numbers for a set of n different ones. It uses a splitting like Quicksort, continuing always with the leftmost list. The normalized running time Yn(t) converges with ln→t in distribution to a non degenerate limit. The finite dimensional distributions of the process Yn converge to a limit (Ragab and Roesler (2014)), called the Quicksort process. In this paper we will present the algorithm Quicksort on the fly, a version of Partial Quicksort, showing the almost sure convergence of Yn to the Quicksort process in Skorokhod metric.

Keywords: Analysis of algorithms; Quicksort process; Stochastic fixed point equation; Weighted branching process; Skorokhod convergence; Stochastic processes (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0304414920301629
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:spapps:v:130:y:2020:i:9:p:5290-5309

Ordering information: This journal article can be ordered from
http://http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.spa.2020.03.008

Access Statistics for this article

Stochastic Processes and their Applications is currently edited by T. Mikosch

More articles in Stochastic Processes and their Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().