Call for Paper - January 2021 Edition
IJCA solicits original research papers for the January 2021 Edition. Last date of manuscript submission is December 21, 2020. Read More

Probabilistic Analysis of Perfect Partitioning in Randomized Quicksort

Print
PDF
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2017
Authors:
Vivek Kumar, Mahesh Kumar Aghwariya
10.5120/ijca2017915421

Vivek Kumar and Mahesh Kumar Aghwariya. Probabilistic Analysis of Perfect Partitioning in Randomized Quicksort. International Journal of Computer Applications 174(9):1-2, September 2017. BibTeX

@article{10.5120/ijca2017915421,
	author = {Vivek Kumar and Mahesh Kumar Aghwariya},
	title = {Probabilistic Analysis of Perfect Partitioning in Randomized Quicksort},
	journal = {International Journal of Computer Applications},
	issue_date = {September 2017},
	volume = {174},
	number = {9},
	month = {Sep},
	year = {2017},
	issn = {0975-8887},
	pages = {1-2},
	numpages = {2},
	url = {http://www.ijcaonline.org/archives/volume174/number9/28432-2017915421},
	doi = {10.5120/ijca2017915421},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, 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

  1. Hoare, C.A., 1962. Quicksort. The Computer Journal, 5(1), pp.10-16.
  2. Coremen, L., Rivest, Stein Introduction to Algorithm. PHI publication.

Keywords

Quicksort, Randomized-Quicksort