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 59
- Downloads 0
The Effect of Mineralizing Fluorine Varnish on the Progression of Initial Caries of Enamel in Temporary Dentition by Laser Fluorescence
Objective: Our study aims to evaluate the effect of mineralizing fluorine varnish on the progression of initial caries of enamel in temporary dentition by laser fluorescence. Material and Methods: Object of observation....
Mechanical and Electrical Properties of Polyaniline/ Lead Oxide Nano Composites
Lead oxide nanoparticles were synthesized by ecofriendly low temperature solution combustion method.Polyaniline (PANI) and PANI- Lead oxide nanocomposites through in-situ chemical oxidative polymerization. The XRD spectr...
Design and implementation of High Altitude Platform Systems to cover Diyala City
The improvement of sharing range between High Altitude Platform System (HAPS) and Terrestrial System (TS) in the 2.4 GHz band is the paper principle point. The High Altitude Platform System (HAPS) works in this apportion...
Analysis on Dispersion & Propagation Optical Fiber of Different Materials at Different Temperatures
Temperature dependent Sell Meier coefficients are necessary for determining different optical design parameters which are important for optical fiber communication system. These coefficients are calculated for fused Sili...
Invariant Stabilization Algorithms in a Control System with Rotating Operating Device
The publication suggests how to significantly improve the spacecraft center of mass movement stabilization accuracy in the active phases of trajectory correction during interplanetary and transfer flights, which in some...