Quick Sort with Optimal Worst Case Running Time
Journal Title: American journal of Engineering Research - Year 2017, Vol 6, Issue 1
Abstract
Quick sort is more than 50 years old and yet is one of the most practical sorting techniques used in the computing industry. Its average running time matches the best asymptotic running time for a sorting algorithm and with a constant factor that outperforms most of the known sorting techniques. However, it suffers from the theoretical worst case time bound of š¯‘‚(š¯‘› 2 ) on a list of size n. Ironically, this worst case occurs when the list is already sorted in ascending or descending order! We present ways to improve the worst case time performance to asymptotically match the optimal worst case running time for any comparison based sorting techniques. Our technique, however, tries not to affect the average running time but the slightest.
Authors and Affiliations
Dr. Mirza Abdulla
Keywords
Related Articles
- EP ID EP398600
- DOI -
- Views 68
- Downloads 0
Gas Chromatography-Mass Spectrometry (GC-MS) Analysis of Extracted Oil from Whole Garden Cress (Rashaad) Seeds
The fine powderfrom whole Garden Cress seeds, which is widely known as Rashaad seed and Thufaā€²a in Middle East area and Arabic countries, was extracted with methanol to yield the essential oil. The chemical composition o...
Characterization of Moganite Obtained From Natural Zeolite By Ball Milling
The aim of this study is to investigate the effect of mechanical activation on the phase change of the zeolite composition of the Hekimhan region which is located in the northern of the Malatya Basin in Eastern Anatolia....
Geotechnical Properties and Geochemical Composition of Kaolin Deposits in Parts of Ifon, Southwestern Nigeria
:This study dealt with the geotechnical and compositional characteristics of the kaolin deposits in Ifon area of Ondo State using a combination of methods including X-ray diffraction analysis. The results show that kaoli...
Arithmetic Sequence with Multiple Reasons
The study of the mathematical series provides an advance in the concepts of analysis and probability, by contributing with the predictions and simulations for diverse performances. Serious mathematics saves time and ener...
Modeling the Effect of Pollution on Dissolved Oxygen (Do) Content of River Benue in Makurdi Town
River Benue, one of the two major rivers in Nigeria is polluted due to human activities in the area and the environs. Samples were taken from different sources for the study. Field sampling, laboratory analysis and regre...