Dear mohd12356,
I provide the following answers only as examples to help you learn the
principles involved. You should not attempt to pass them off as your
own work.
1. Since comments are not properly program statements, we can leave
them out of the runtime analysis altogether.
Cost #Times
BUBBLESORT(A) ---- ------
for pass <- 1 to (n-1) do c (n-1)
for j <- 1 to (n-pass) do c (n-1)*n/2
if A[j] > A[j+1] then c (n-1)*n/2
tmp <- A[j] c (n-1)*n/2
A[j] <- A[j+1] c (n-1)*n/2
A[j+1] <- tmp c (n-1)*n/2
In the worst case, the "if" statement will always be true, so the swap
operation will be performed with each iteration of the inner loop.
The outer loop is obviously carried out (n-1) times.
The inner loop is carried out (n-1)*(n-pass) times, where (n-pass) is
incremented from (n-1) to (n-(n-1))=1. Using the classic Gaussian
formula, we know that the sum over the sequence is (n-1)*((n-1)+1)/2 =
(n-1)*n/2.
The total cost in the worst case, then, is
(n-1) + 5*((n-1)*n/2) = 2*(n-1)/2 + (5*n*n - 5*n)/2
= (5n^2 - 3n - 2) / 2
units of time. This is within a constant factor of n^2, so Bubblesort
is what we call an O(n^2) algorithm. (Read O(n^2) as "order of n
squared".)
2. We can insert at the beginning of any sorting algorithm a routine
that runs through the array to check whether each element is no
greater than the one following it. This takes constant time per
element, and only n-1 comparisons need be made for an array of length
n.
If, indeed, each element is no greater than the one following it, the
array is already in order. The algorithm can therefore halt without
performing any sorting operations. In the best case, therefore, such
an algorithm will take time linearly proportional to the length of the
array.
If you find that the above work is incomplete or inaccurate in any
way, please post a clarification request so that I have a chance to
meet your needs before you assign a rating.
Regards,
leapinglizard |
Request for Answer Clarification by
mohd123456-ga
on
03 Sep 2004 07:52 PDT
but what i need to know is that in part one i have compute worst case
time as a funciton of 'n' . but its mentioned in the pdf document
....Use the method in class for INSERTIONSORT (add entries under
columns Cost and #Times). Assume a cost of c for every executable
statement and a cost of zero for comments......
can you explain this
or if you can give me the example of cost and #times of the mentioned
INSERTIONSORT class
|
Clarification of Answer by
leapinglizard-ga
on
03 Sep 2004 08:15 PDT
I believe you're misreading this PDF document of yours. The exercise
instructs you to use the same method for BUBBLESORT that was
demonstrated in class -- in a classroom, during a lecture -- for
INSERTIONSORT. It does not ask you to analyze INSERTIONSORT; that was
previously done in class. The exercise is to analyze BUBBLESORT. That
is exactly what I have done for you. The worst-case runtime as a
function of n is the following.
f(n) = c * (5n^2 - 3n - 2) / 2
Everything clear now?
leapinglizard
|
Request for Answer Clarification by
mohd123456-ga
on
03 Sep 2004 16:19 PDT
I'm OK now,
But do you have the base for BUBBLESORT.
I mean when I can the worst-case and a best-case?
Thank you.
|
Clarification of Answer by
leapinglizard-ga
on
03 Sep 2004 16:30 PDT
The exercise doesn't ask for the best-case input to BUBBLESORT, but I
can tell you that it's an array where the elements are already in
order, implying that no elements will be swapped. The inner loop would
still execute the same number of times, though, so the saving over the
worst case is only a constant factor.
The worst-case input to BUBBLESORT, upon which my analysis is based,
is where the elements are exactly in reverse order. That is why the
"if" condition in the inner loop is true in every instance, as I
mention above.
Let me know if there's any further detail you feel I should mention.
leapinglizard
|
Request for Answer Clarification by
mohd123456-ga
on
03 Sep 2004 17:09 PDT
Thank you leapinglizard-ga ,
But my Question just for general base for:
base for BUBBLESORT:1-worst-case and,2- a best-case?
Thank you so much.
|
Clarification of Answer by
leapinglizard-ga
on
03 Sep 2004 17:24 PDT
I'm afraid I don't understand what you're asking for, and it doesn't
seem to be part of the original question in any event. Aren't you
satisfied with my description of the worst-case and best-case input to
BUBBLESORT?
leapinglizard
|
Clarification of Answer by
leapinglizard-ga
on
03 Sep 2004 17:29 PDT
I guess my chief difficulty is that I don't know what you mean by
"general base". What is a general base? I believe I've given
comprehensive solutions to both exercises. As for the knowledge that I
brought to bear, that's something that falls outside the scope of the
question. There are entire university courses devoted to algorithmic
analysis. Surely you can't expect me to summarize the content of
several dozen lectures in this small space.
Are we agreed that I have properly solved your exercises?
leapinglizard
|
Request for Answer Clarification by
mohd123456-ga
on
04 Sep 2004 10:20 PDT
Yes, I agreed for solved your exercises.
And
Thank you so much.
|
Clarification of Answer by
leapinglizard-ga
on
04 Sep 2004 10:28 PDT
You're welcome.
leapinglizard
|
,
0 Comments
)