Solved

Quicksort

Posted on 1998-03-25
4
373 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
[X]
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
  • 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

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

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…
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…
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.

734 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