Quick Sort Optimized for Non-decreasing Data set
Abstract
The Sorting Algorithm proposed by C.A.R Hoare in 1961 by name Quick sort, which is popularly known for being the fastest sorting algorithm. Quick sort is still being practiced in the field of computers systems and its applications. The Algorithm whose efficiency to sort random data set is represented in asymptotic notation as O(n log2 n) and when quick sort algorithm has a input data set which is already Ordered then it takes a quadratic execution time which is considered as a worst case performance and this behavior is represented in asymptotic notation as O(n2). The worst case performance is due the scan over heads which occur over the pre-sorted data set, in other words the partitioning gets skewed due to recursive calls and hence results in a quadratic complexity. This research paper presents an algorithm which minimizes a worst case execution time making it linear when the input list is in non-decreasing order. The paper describes how the improvements are accommodated in the existing quick sort. A priori analysis of proposed algorithm for different cases is made along with a proof of correctness. Later the algorithm is verified for its correctness and asymptotic performance. The algorithm is implemented using C++ and also we have compared with other popular quick-sort version.
References
[2] Levitin, A. Introduction to the Design and Analysis of Algorithms. Addison-Wesley, Boston MA, 2007. https://books.google.co.in/books? id=pOZSS9YeJYkC
[3] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest,Clifford Stein, Introduction to Algorithms, Second Edition, Prentice-Hall New Delhi,2004. https://books.google.co.in/books ?id=YsE2pwAACAAJ},
[4] Weiss, M. A., Data Structures and Algorithm Analysis in C,Addison-Wesley,Second Edition, 1997 ISBN: 0-201-49840-5.https://books.google.co.in/books? id=dG8YZ521YVYC
[5] C.A.R. Hoare. “Algorithm 64: Quicksort.” Communications of the ACM, vol. 4, pp. 321, Jul.1961. doi/10.1145/366622.366644
[6] C.A.R. Hoare. “Quicksort.” Computer Journal, vol. 5, 1962, pp. 10–15. https://academic.oup.com/comjnl/article/5/1/10/395338
[7] B.Randell & J. Russell. "Certification of algorithlns 63, 64, 65: Partition, Quicksort, Find . " Comm. ACM ,July 1961. https://dl.acm.org/doi/10.1145/366707.367561
[8] R.S. Scowen, “Algorithm 271: Quickersort,” Comm. ACM 8,11, pp 669-670, Nov. 1965. doi:10.1145/365660.365678
[9] BLAIR, C. R. “Certification of Algorithm 271: Quickersort”. Comm.ACM,9,5(May1966),354. https://doi.org/10.1145/355592.365613
[10] Van Emden, M.H. “Increasing the Efficiency of Quick-sort”. Communications of the ACM 13, 9 (September 1970), 563-567. https://doi.org/10.1145/362736.362753
[11] Van Emden, M.H. “Algorithm 402, qsort “,Comm. A C M 13, 11(Nov. 1970), 693-694. https://doi.org/10.1145/362790.362803
[12] M. Foley and C.A.R Hoare, “Proof of a rccursive program: Quicksort”. Computer . Journal. 14, 4 (Nov. 1971), 391-395.https://doi.org/10.1093/comjnl/14.4.391
[13] R. Loeser. “Some performance tests of: quicksort: and descendants.” ,Communications of the ACM, vol. 17, Mar. 1974, pp. 143–152.
[14] R. Sedgewick. “Quicksort.” PhD dissertation, Stanford University, Stanford, CA, USA, 1975.
[15] Sedgewick, R. “Quicksort With Equal Keys”. SIAM Journal of Computer, 6,2 (June 1977) 240-267. https://sedgewick.io/wp-content/themes/sedgewick/papers/1977Equal.pdf
[16] R. Sedgewick. “Implementing Quicksort programs”, Communications of the ACM, vol. 21(10), pp. 847–857, 1978. https://doi.org/10.1145/359619.359631
[17] Cook, CR.. and Kim, D.J. “Best sorting algorithm for nearly sorted lists”. Communications of the ACM, 23, 11 (Nov. 1980), 620-624. https://doi.org/10.1145/359024.359026
[18] Motzkin. D. “Meansort”, Communications of the ACM, 26,4 (Apr. 1983), 250-251. https://doi.org/10.1145/2163.358088
[19] J. Bentley. “Programming Pearl: How to sort.”, Communications of the ACM, vol. 27(4),1984. https://doi.org/10.1145/3894.315111
[20] R.L. Wainwright. “A class of sorting algorithms based on Quicksort”, Communications of the ACM ,vol. 28(4), pp. 396-402, April 1985. https://doi.org/10.1145/3341.3348
[21] CORPORATE “Tech Correspondence, Technical correspondence.” ,Communications of the ACM, vol. 29(4), pp. 331-335, Apr. 1986, https://doi.org/10.1145/5684.315618
[22] R.L. Wainright. “Quicksort algorithms with an early exit for sorted subfiles.” ,Communications of the ACM, pp. 183-190, 1987. https://doi.org/10.114
[23] J. L. Bentley, M. D. McilRoy, “Engineering a Sort Function” ,Software—Practice and Experience, Vol. 23(11), Nov. 1993, pp 249 – 1265 . https://doi.org/10.1002/spe.4380231105
[24] J.L. Bentley, R. Sedgewick, R. “Fast algorithms for sorting and searching strings” ,in Proc.8th Annual ACM-SIAM symposium on Discrete algorithms, 1997, pp. 360–369.https://dl.acm.org/doi/10.5555/314161.314321
[25] L. Khreisat. “QuickSort: A Historical Perspective and Empirical Study”, International Journal of Computer Science and Network Security, vol. 7(12), Dec. 2007. http://paper.ijcsns.org/07_book/200712/20071207.pdf
[26] L. Khreisat. “A Survey of Adaptive QuickSort Algorithms”,international Journal of Computer Science and Security (IJCSS), Volume (12) : Issue (1) : 2018. https://www.cscjournals.org/library/manuscriptinfo.php?mc=IJCSS-1372
[27] O.K. Durrani, S.A.K. Nazim, “Modified quick sort: worst case made best case”. International Journal for Emerging Technology and Advances Eng. 5(8). Website: www.ijetae.com . ISSN 2250-2459, August 2015.
[28] O. K. Durrani, A. S. Farooqi, A. G. Chinmai and K. S. Prasad, "Performances of Sorting Algorithms in Popular Programming Languages," 2022 International Conference on Smart Generation Computing, Communication and Networking (SMART GENCON), Bangalore,india,2022,pp.1-7. doi:10.1109/SMARTGENCON56628.2022.10084261
[29] Bal, A.B., Chakraborty, S. (2020). “An Experimental Study of a Modified Version of Quicksort”. Advances in Computational Intelligence. Advances in Intelligent Systems and Computing, vol 988.Springer,Singapore. https://link.springer.com/chapter/10.1007/978-981-13-8222-2_27
[30] Omar khan Durrani and Dr. Sayed Abdulhayan , “Asymptotic Performances of Popular Programming Languages for Popular Sorting Algorithms”, Semiconductor Optoelectronics,Vol. 42 No. 1 (2023), 149-169, https://bdtgd.cn/article/view/2023/149.pdf
To ensure uniformity of treatment among all contributors, other forms may not be substituted for this form, nor may any wording of the form be changed. This form is intended for original material submitted to AJCT and must accompany any such material in order to be published by AJCT. Please read the form carefully.
The undersigned hereby assigns to the Asian Journal of Convergence in Technology Issues ("AJCT") all rights under copyright that may exist in and to the above Work, any revised or expanded derivative works submitted to AJCT by the undersigned based on the Work, and any associated written, audio and/or visual presentations or other enhancements accompanying the Work. The undersigned hereby warrants that the Work is original and that he/she is the author of the Work; to the extent the Work incorporates text passages, figures, data or other material from the works of others, the undersigned has obtained any necessary permission. See Retained Rights, below.
AUTHOR RESPONSIBILITIES
AJCT distributes its technical publications throughout the world and wants to ensure that the material submitted to its publications is properly available to the readership of those publications. Authors must ensure that The Work is their own and is original. It is the responsibility of the authors, not AJCT, to determine whether disclosure of their material requires the prior consent of other parties and, if so, to obtain it.
RETAINED RIGHTS/TERMS AND CONDITIONS
1. Authors/employers retain all proprietary rights in any process, procedure, or article of manufacture described in the Work.
2. Authors/employers may reproduce or authorize others to reproduce The Work and for the author's personal use or for company or organizational use, provided that the source and any AJCT copyright notice are indicated, the copies are not used in any way that implies AJCT endorsement of a product or service of any employer, and the copies themselves are not offered for sale.
3. Authors/employers may make limited distribution of all or portions of the Work prior to publication if they inform AJCT in advance of the nature and extent of such limited distribution.
4. For all uses not covered by items 2 and 3, authors/employers must request permission from AJCT.
5. Although authors are permitted to re-use all or portions of the Work in other works, this does not include granting third-party requests for reprinting, republishing, or other types of re-use.
INFORMATION FOR AUTHORS
AJCT Copyright Ownership
It is the formal policy of AJCT to own the copyrights to all copyrightable material in its technical publications and to the individual contributions contained therein, in order to protect the interests of AJCT, its authors and their employers, and, at the same time, to facilitate the appropriate re-use of this material by others.
Author/Employer Rights
If you are employed and prepared the Work on a subject within the scope of your employment, the copyright in the Work belongs to your employer as a work-for-hire. In that case, AJCT assumes that when you sign this Form, you are authorized to do so by your employer and that your employer has consented to the transfer of copyright, to the representation and warranty of publication rights, and to all other terms and conditions of this Form. If such authorization and consent has not been given to you, an authorized representative of your employer should sign this Form as the Author.
Reprint/Republication Policy
AJCT requires that the consent of the first-named author and employer be sought as a condition to granting reprint or republication rights to others or for permitting use of a Work for promotion or marketing purposes.
GENERAL TERMS
1. The undersigned represents that he/she has the power and authority to make and execute this assignment.
2. The undersigned agrees to indemnify and hold harmless AJCT from any damage or expense that may arise in the event of a breach of any of the warranties set forth above.
3. In the event the above work is accepted and published by AJCT and consequently withdrawn by the author(s), the foregoing copyright transfer shall become null and void and all materials embodying the Work submitted to AJCT will be destroyed.
4. For jointly authored Works, all joint authors should sign, or one of the authors should sign as authorized agent
for the others.
Licenced by :
Creative Commons Attribution 4.0 International License.
