Solved

Quicksort

Posted on 1998-03-25
4
361 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

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
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…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

744 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

13 Experts available now in Live!

Get 1:1 Help Now