Quick sort question


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 2 of 2

Thread: Quick sort question

  1. #1
    Join Date
    Oct 2004
    Posts
    1

    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?

  2. #2
    Join Date
    Sep 2004
    Posts
    150
    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.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center