1. Optimizing Complexity of Quick Sort
- Author
-
Hossain, Md. Sabir, Mondal, Snaholata, Ali, Rahma Simin, and Hasan, Mohammad
- Subjects
Time complexity ,Reversely sorted ,Logarithm ,Best case ,Worst case ,Article ,Quick Sort - 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(\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ nlogn $$\end{document}nlogn) for the best case and O(\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ n^{2} $$\end{document}n2) 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(\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ nlogn $$\end{document}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.
- Published
- 2020