فرآیند مرتب سازی سریع میانه₋محور

نویسندگان
رامین ایمانی نبیی 1
مهری جوانیان 2
1 دانشگاه تبریز
2 دانشگاه زنجان
چکیده
الگوریتم مرتب‌سازی سریع، داده­های ذخیره شده در یک آرایه را مرتب می‌کند. الگوریتم مرتب‌سازی سریع جزئی، کوچکترین l عدد از n عدد ذخیره شده در یک آرایه را مرتب می‌کند. الگوریتم مرتب‌سازی سریع آنی، ابتدا کوچکترین داده، سپس دومین کوچکترین داده و به همین ترتیب تا آخرین دادۀ یک آرایه را به ترتیب زمانی مرتب می‌کند که اگر در₋l امین کوچکترین داده متوقف شویم، آنگاه همان نتیجۀ کار الگوریتم مرتب‌سازی سریع جزئی را ارائه می‌کند. در این مقاله به تحلیل Ynln یک نسخۀ استاندارد شدۀ تعداد مقایسه‌های مورد نیاز برای مرتب کردن کوچکترین l عدد از n عدد ذخیره شده در یک آرایه توسط الگوریتم مرتب‌سازی سریع آنی میانه₋ محور می‌پردازیم و نشان می‌دهیم که هرگاه l≔nt ، t∈0,1 و n→∞ ، آنگاه فرآیند Ynt≔Ynntn به Yt در فضای توابع کدلگ همگرا است.
کلیدواژه‌ها
الگوریتم مرتب‌سازی سریع میانه محور
فرآیند شاخه‌ای وزن‌دار
روش انقباض
فضای توابع کدلگ

عنوان مقاله English

Median Quicksort Process

نویسندگان English

Ramin Imany Nabiyyi 1
Mehri Javanian 2
1 University of Tabriz
2 University of Zanjan
چکیده English

The Quicksort algorithm sorts the data stored in an array. The Partial Quicksort algorithm sorts the l smallest numbers out of numbers stored in an array of length n. The Quicksort on the fly provides online first the smallest, then the second smallest and so on. If we stop at the l-th smallest, we obtain Partial Quicksort. In this paper, we analyze Ynln, a correctly normalized version of the number of comparisons needed to sort the l smallest numbers out of numbers stored in an array of length n, by the Median Quicksort algorithm. We show that whenever l≔nt، t∈0,1 and n→∞, then the process Ynt≔Ynntn converges to Yt in the space of cadlag functions.

کلیدواژه‌ها English

Median Quicksort algorithm
weighted branching process
contraction method
space of cadlag function
1. V. Bruhn, Eine Methode zur asymptotischen Behandlung einer Klasse von Rekursionsgleichungen mit einer Anwendung in der stochastischen Analyse des Quicksort-Algorithmus, Dissertation, Christian-Albrechts-Universitat, Kiel, 1996.

2. S. Hallmann, U. Roesler and M. Wnuk, All solutions of the stochastic fixed point equation of the Quicksort process, Advances in Applied Probability, 50 (2018), 131–140.

3. V. Iliopoulos, The Quicksort algorithm and related topics, Phd Thesis (2013),

4. M. Javanian and U. Roesler, Expectation of Partial Median Quicksort, Mediterranean Journal of Mathematics, submitted (2024).

5. M. Javanian and A. M. Mosammam, Some results on asymptotic behavior of the recalls of random median Quicksort, Mathematics Interdisciplinary Research, 7 (2022), 357-375.

6. D.E. Knuth, The art of computer programming, Vol.3: Sorting and Searching, 1973.

7. C. Martinez and U. Roesler, Partial Quicksort and Quickpartitionsort, Discrete Mathematics and Theoretical Computer Science, 21 (2010), 505– 512.

8. Martinez C., Partial Quicksort, Proceeding, 1st ACM-SIAM Workshop on Analytic Algorithmics and Combinatorics, 6 (2004), 224–228.

9. H. Okasha and U. Roesler, Asymptotic distribution for random median Quicksort, Journal of Discrete Algorithms, 5 (2007), 592–608.

10. M. Ragab and U. Roesler, The Quicksort process, Stochastic Processes and their Applications, 124 (2014), 1036–1054.

11. U. Roesler, On the analysis of stochastic divide and conqure algorithms, Algorithmica, 29 (2001), 238–261.

12. U. Roesler, The weighted branching process, Branching Processes and Their Applications, 219 (2016), 219–236.

13. U. Roesler, Almost sure convergence to the Quicksort process, Stochastic Processes and their Applications, 130 (2020), 5290–5309.

14. U. Roesler, A limit theorem for Quicksort, RAIRO - Theoretical Informatics and Applications, 25 (1991), 85–100.

15. S. Wild, M. E. Nebel and R. Neininger, Average case and distributional analysis of dual-pivot Quicksort, ACM Transactions on Algorithms, 11 (2015), 1–42.