Back to Search
Start Over
Optimizing Complexity of Quick Sort
- Source :
- Communications in Computer and Information Science ISBN: 9789811566479
- Publication Year :
- 2020
- Publisher :
- Springer Singapore, 2020.
-
Abstract
- Quick Sort is considered as the fastest sorting algorithm among all the sorting algorithms. The idea of selecting a pivot was introduced in classical Quick Sort in 1962. This sorting algorithm takes favorably less time compared to other methods. It needs a complex time O(\( nlogn \)) for the best case and O(\( n^{2} \)) for worst-case which occurs when the input array is already sorted or reversely sorted. To reduce the worst-case complexity we provide a strong algorithm where it makes fewer comparisons and the time complexity after using this algorithm becomes a function of logarithm O(\( nlogn \)) for worst-case complexity. We experimentally evaluate our algorithms and compare them with classical algorithms and with other papers. The algorithm presented here has profound implications for future studies of handling worst-case complexity and may one day help to solve this occurrence of the fastest sorting method.
Details
- Database :
- OpenAIRE
- Journal :
- Communications in Computer and Information Science ISBN: 9789811566479
- Accession number :
- edsair.doi...........c2ffec3645600c1904d4ba3a65d2534f