Different Cases of Quick Sort

Authors(2) :-Chahat Monga, Richa

Sorting algorithms have attracted a great deal of attention and study, as they have numerous applications to Mathematics, Computer Science and related fields. In this thesis, we first deal with the mathematical analysis of the Quick sort algorithm and its variants. Specifically, we study the time complexity of the algorithm and we provide a complete demonstration of the variance of the number of comparisons required, a known result but one whose detailed proof is not easy to read out of the literature. We also examine variants of Quick sort, where multiple pivots are chosen for the partitioning of the array. The rest of this work is dedicated to the analysis of finding the true order by further pair wise comparisons when a partial order compatible with the true order is given in advance. We discuss a number of cases where the partially ordered sets arise at random. To this end, we employ results from Graph and Information Theory. Finally, we obtain an alternative bound on the number of linear extensions when the partially ordered set arises from a random graph, and discuss the possible application of Shell sort in merging chains.

Authors and Affiliations

Chahat Monga
Guru Nanak College, Department of Computer Science and Applications, Ferozepur, Punjab, India
Punjabi University, Department of Computer Science, Patiala, Punjab, India

Sorting, Pivot, Keys, Pointer

  1. Abramowitz, M. and Stegun, I. A. (1972) "Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables." Dover Publications.
  2. Albacea, E. A. (2012) "Average-case analysis of Leapfrogging samplesort." Philipp. Sci. Lett. 5 (1): 14-16.
  3. Albert, M. and Frieze A. (1989) "Random graph orders." Order 6 (1): 19-30.
  4. Alon, N., Bollobás, B., Brightwell, G. and Janson, S. (1994) "Linear Extensions of a Random Partial Order." Ann. Appl. Probab. 4 (1): 108-123.
  5. Bell, D. A. (1958) "The Principles of Sorting." Comput. J. 1 (2): 71-77.
  6. Bentley, J. L. (2000) "Programming Pearls." Addison-Wesley Publishing, second edition.
  7. Bentley, J. L. and McIlroy, M. D. (1993) "Engineering a Sort Function." Software Pract. Exper. 23 (11): 1249-1265.
  8. Billingsley, P. (2012) "Probability and measure." John Wiley & So., third edition.
  9. Boyce, W. E., DiPrima, R. C. (2001) "Elementary Differential Equations and Boundary Value Problems." John Wiley & So., seventh edition.

Publication Details

Published in : Volume 3 | Issue 3 | May-June 2017
Date of Publication : 2017-06-30
License:  This work is licensed under a Creative Commons Attribution 4.0 International License.
Page(s) : 709-713
Manuscript Number : IJSRSET1841112
Publisher : Technoscience Academy

Print ISSN : 2395-1990, Online ISSN : 2394-4099

Cite This Article :

Chahat Monga, Richa, " Different Cases of Quick Sort, International Journal of Scientific Research in Science, Engineering and Technology(IJSRSET), Print ISSN : 2395-1990, Online ISSN : 2394-4099, Volume 3, Issue 3, pp.709-713, May-June-2017.
Journal URL : http://ijsrset.com/IJSRSET1841112

Article Preview

Follow Us

Contact Us