Solved

Quicksort

Posted on 1998-03-25
4
364 Views
Last Modified: 2008-07-03
How would yo modify a quicksort algorithm so that it would run in O(N * log2N) time if the initial array was sorted or random?    Be sure to explain why your modification makes a difference.   Note:  O(N * log2N) <- 2 is a subscript
0
Comment
Question by:gokou
  • 2
4 Comments
 
LVL 4

Accepted Solution

by:
jos010697 earned 100 total points
ID: 1257808
Average big-oh (read: for random input) of the quicksort algorithm is n*log2(n)
already, prepending a single sweep (big-oh == n) checking whether or not
the input is sorted already doesn't change the overall big-oh value ...

kind regards,

Jos aka jos@and.nl
0
 

Author Comment

by:gokou
ID: 1257809
Jos, I'm not sure if your answer is correct.  I also looked up the word prepending in Webster's Dictionary and I couldn't find the definition for this word.  Can you explain what you mean by prepending?


0
 
LVL 4

Expert Comment

by:jos010697
ID: 1257810
I apologize if I didn't make myself clear enough; I meant: before starting the
original quicksort algorithm, a simple check could be performed figuring
out whether or not the input is sorted already (ascending or descending),

if so, the quicksort algorithm does not have do be started, otherwise,
a simple quicksort is started; the big-oh of this check+quicksort is

O(n)+O(n*2log(n)) == O(n*2log(n))

kind regards,

Jos aka jos@and.nl



0
 
LVL 84

Expert Comment

by:ozo
ID: 1257811
Nor does the pre-check change the n² worst case behavior for pathologically almost sorted input.
There are ways to select a near median pivot element in O(n) time which guarantee O(n*log(n) worst case behavior,
but these can affect the constant factor that makes quicksort so useful in the average case.
0

Featured Post

Superior storage. Superior surveillance.

WD Purple drives are built for 24/7, always-on, high-definition security systems. With support for up to 8 hard drives and 32 cameras, WD Purple drives are optimized for surveillance.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.

911 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now