Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Quicksort

Posted on 1998-03-25
4
Medium Priority
?
376 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 400 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

Industry Leaders: 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

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
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 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.
Suggested Courses

705 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