Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people, just like you, are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
Solved

Quicksort

Posted on 1998-03-25
4
369 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 our DevOps Teams Maximize Uptime

Our Dev teams are like yours. They’re continually cranking out code for new features/bugs fixes, testing, deploying, responding to production monitoring events and more. It’s complex. So, we thought you’d like to see what’s working for us. Read the use case whitepaper.

Question has a verified solution.

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

Suggested Solutions

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.

839 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