Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

|
Options

Ricky
2007-08-06 05:24:26

That is certainly not a wrong answer, but it only skirts the main issue.

mathsyperson
2007-08-06 05:19:11

I suppose it depends on how much easier it is to compare the items than to switch them.

For example, say you have a row of books that you want to put in alphabetical order, but some joker has written all the titles in Sanskrit. You need to look up each title in your English-Sanskrit dictionary whenever you want to make a comparison, but once you know the order they should be in, it's a simple matter to put them there.

However, say you have a group of elephants and you want to put them in order of size. It's fairly easy to see which of two elephants is the bigger one, but if they need to be swapped then it'd be fairly tricky to manoeuvre them without getting trunked.

That answer isn't very specific though, so it's probably not what you were thinking of.

Ricky
2007-08-06 04:53:41

Sorry, must have overlook this.  Yes, those are correct.  So here is the thing about models.  We have two models:

A. Count the number of list comparisons.
B. Count the number of swaps.

Both can be applied to bubble sort.  And we have the best and worst cases as follows:

|  A         |     B
-------------------------------
Worst  |  n^2     |     n^2
-------------------------------
Best    |  n         |     0

Now the question becomes which is a better model, A or B?  There is a very specific answer to this question.  But it is a more of a think-about-it-yourself-for-a-bit-then-I'll-tell-you-the-right-answer sort of question.

mikau
2007-08-06 03:48:36

are those solutions correct, Ricky?

mikau
2007-08-02 00:26:40

Ricky
2007-08-01 05:34:01

Corret.

mikau
2007-08-01 02:59:14

single swap = 1, everything else is zero?
Do you mean the total number of swaps, best and worst case?

Ricky
2007-07-30 16:49:48

I'm going to be attempting to illustrate something that I've waved my hands at, and really should have covered first.  Then hopefully we can move on to some more interesting problems.

Now do the same analysis for bubblesort, but this time by counting a single swap as a cost of 1, everything else counts as 0.

mikau
2007-07-30 14:00:30

btw, do you think this should be moved to Coders Corner?

Ricky
2007-07-30 12:52:15

Your worst case is right, but what happened with your best case?  You talk about swapping, but I need a number of comparisons.

mikau
2007-07-30 11:51:44

hey, Ricky! I finally got a chance to work on this. here are my solutions

Ricky
2007-07-21 11:22:45

Actually, best to take out the outer loop and change it to a while.  Changes made.

John E. Franklin
2007-07-21 08:29:57

Just one more thing Ricky...
Subtract one more at the end of the inner loop so when the comparison is made on the last two elements, you don't overstep the array boundary.
Isn't it neat the way items get moved along and dropped when a more significant value is found and then that is moved along and dropped off??  Pretty cool and easy to write.

Ricky
2007-07-21 01:58:51

Nope, it's only comparisons between list elements.  Note my comment on line 4.

mikau
2007-07-20 16:54:13

the old bubble sort, eh?

Well i'll work on it when i get some time. I've been teaching myself linnear algebra and C++ over the summer and its consuming a lot of my freetime. I'll tackle this next chance I get.

Question, i'm not sure what language you are using. Do I need to consider that a for loop makes a comparison for the entry condition on every itteration of the loop?