The week's pick
Random Articles
Reseach Article
Probabilistic Analysis of Perfect Partitioning in Randomized Quicksort
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 174 - Number 9 |
| Year of Publication: 2017 |
| Authors: Vivek Kumar, Mahesh Kumar Aghwariya |
10.5120/ijca2017915421
|
Vivek Kumar, Mahesh Kumar Aghwariya . Probabilistic Analysis of Perfect Partitioning in Randomized Quicksort. International Journal of Computer Applications. 174, 9 ( Sep 2017), 1-2. DOI=10.5120/ijca2017915421
Abstract
The paper analyzes the probability of a scenario where Randomized-Quicksort performs a perfect partitioning of the input array. The RANDOMIZED PARTITION procedure, which is a subroutine of the Randomized-Quicksort, randomly picks an element of the given array as the pivot element, it then partitions the array around that element. A perfect partitioning occurs when every successive call to the RANDOMIZED-PARTITION procedure results in the picking of the median element as the pivot element, which partitions the array into two halves consisting of exact no. of elements. In this scenario, the algorithm yields an Θ (n lg n) runtime.
References
- Hoare, C.A., 1962. Quicksort. The Computer Journal, 5(1), pp.10-16.
- Coremen, L., Rivest, Stein Introduction to Algorithm. PHI publication.
Index Terms
Keywords