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 60
- Downloads 0
DQ Modeling and Dynamic Characteristics of a Three-Phase Induction Machine
AC motors as a drive have become more popular over its DC motors counterpart (For example Ward Leonard System) in the variable speed drives applications. The latter uses three electrical rotating machines and very costly...
Optimization Of Clutch Drum Welding Process Condition For Automobile AT Using "Parameter Design"
A lot of parts for transmitting power are built in the inside of the automatic transmission of the automobile. Clutch pack parts having important functions related to speed change adopt machining and heat treatment proce...
Study of Various Rainfall Estimation & Prediction Techniques Using Data Mining
It is important to estimate accurately rainfall for effective use of water resources and optimal planning of water structures and availability. For this purpose, the various models and techniques are developed to estimat...
A Design and Development of Rubrics System for Android Applications
Online grading systems have become extremely prevalent as majority of academic materials are in the process of being digitized, if not already done. In this paper, we present the concept of design and implementation of a...
Mapping 3D Geological Structures and Predicting the Kinematics of the Pitwalls Using Photogrammetric Techniques: A Case Study
Traditional method of Mapping geological structures in the mine is usually inaccurate, time consuming and very risky, especially in highly unstable areas. The introduction of 3D structural mapping and pit wall monitoring...