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 64
- Downloads 0
Quarry Dust – A Key Player in Improving The Geo-Technical Properties of Subgrade Soil
:Quarries and aggregate crushers are basic requisites for construction industry and quarry dust is a byproduct of rubble crusher units. Disposal of such wastes poses lots of geo environmental problems such as landfill di...
Review of Elementary Crystallographic Cells of Important Intermediate Phases in Golden Alloys
Pure gold is rarely used, mainly from its low mechanical properties, first of all the strength and hardness, but the toughness is however on a high level. For improving the strength and hardness the gold shold be alloyed...
Improving The Rheological Properties of Drilling Mud Using Local Based Materials
Locally sourced materials have been used in the past to produce drilling fluids but the major problem encountered is that the gel strength of the drilling fluids produced using local substitutes is too low and the fluid...
Use of Experimental Designs to Evaluate the Influence of a triazole on the Corrosion of ordinary Steel in HCl (1 M) Environment
The present study attempted to investigate the best conditions for the use of Bromuconazole as corrosion inhibitor of ordinary steel in 1 M HCl through the use of the surface response methodology. In this work we have dr...
Design Improvement Study For cBN Coated Cutting Body Used In Piston Ring Cutting Process
In this study, the quality of non-alloy, non-heat treated, gray cast iron workpieces with lamellar graphite was compared with the cutter body with cubic boron nitride (cBN) coated with different hot work steel tool desig...