Quick sort question
Excuse me if this question is novice.
Does anyone know how quick sort can be made to run in O(nlgn) time in worst case?
I do not believe it is possible to do that without changing the algorithm until it is no longer "QuickSort." QuickSort has a worst case of O(n^2) , a best case of O(n) but an average case of O(nlogn). These figures are inherent in its design.
With careful optimizations based on the data you are sorting you can almost assure that it will never hit the worst case scenario, but you cannot change what its worst case scenario actually is.
You may want to try Mergesort, thought to be slower on average (in practice) but its worse case is O(nlogn) which is a better worst case scenario.
If you avoid the "worst case" of Quicksort then you are a good programmer.
If you change the worst case of Quicksort you have created a new algorithm and you get to name it.
Top DevX Stories
Easy Web Services with SQL Server 2005 HTTP Endpoints
JavaOne 2005: Java Platform Roadmap Focuses on Ease of Development, Sun Focuses on the "Free" in F.O.S.S.
Wed Yourself to UML with the Power of Associations
Microsoft to Add AJAX Capabilities to ASP.NET
IBM's Cloudscape Versus MySQL