DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 2 of 2
  1. #1
    Join Date
    Oct 2004

    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
    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
Latest Articles
Questions? Contact us.
Web Development
Latest Tips
Open Source

   Development Centers

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

By using this site, you agree to the Privacy Policy