Research Article
Probabilistic Analysis of Perfect Partitioning in Randomized Quicksort
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 174 - Issue 9 |
| Published: Sep 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
@article{ 10.5120/ijca2017915421,
author = { Vivek Kumar,Mahesh Kumar Aghwariya },
title = { Probabilistic Analysis of Perfect Partitioning in Randomized Quicksort },
journal = { International Journal of Computer Applications },
year = { 2017 },
volume = { 174 },
number = { 9 },
pages = { 1-2 },
doi = { 10.5120/ijca2017915421 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2017
%A Vivek Kumar
%A Mahesh Kumar Aghwariya
%T Probabilistic Analysis of Perfect Partitioning in Randomized Quicksort%T
%J International Journal of Computer Applications
%V 174
%N 9
%P 1-2
%R 10.5120/ijca2017915421
%I Foundation of Computer Science (FCS), NY, USA
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