Archived

This topic is now archived and is closed to further replies.

Tsu

What the heck is a bubble sort?

Recommended Posts

My computer science teacher used the term when we were learning about sorting arrays, but never gave me (or the rest of the class) a decent defenition of what it means...
  • is there another kind of sort?
  • why bubble?
  • does it really make bubbles when you sort it?

Share this post


Link to post
Share on other sites
// assume an array of ints
int array[n];

// no we sort from lowest to highest so that array[0] is the lowest and array[n-1] is the highest number...

for(int i = 0; i < n - 1; i++)
{
for(int i2 = 0; i2 < n - i; i2++)
{
if(array[i2] > array[i2 + 1])
swap(array[i2], array[i2 + 1]); // assume a function that switches two variables...
}
}

Share this post


Link to post
Share on other sites
The name comes from the fact that the high values ( or low depending on your sort ) "bubble up" to the top. On each pass through you swap two values. The higher (or lower) values keep getting swapped up. It looks like they are bubbling up to the surface.

Here''s a few applets that show what''s going on.


Bubble Sort Applet

Another One

-------
Andrew

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
It''s called a bubble sort because the entries of the array. . . "bubble" to the top. Or in that examples case the bottom (depending on how you think of it). Yes there are other sorts of sorts (. . . sorry, guess that wasn''t funny), bubble sort seems to be the most common from my perspective, but then again it is very limited. I forget what my instructor called another type, stacked sort or something like that. He never bothered explaining it either though. Basically if you want to learn something about programming do it outside of class, you will never get what you need to know from a teacher. . . after all who would want to teach computer science if they were any good at programming? They could be out making games or in some Buisness setting making millions.

Share this post


Link to post
Share on other sites
ok thanks, i get it now...

i can see how it could be the slowest... just for fun i made my program sort a list of about 1000 random numbers (between 1 and 100) instead of 10... it took a while... (it was in ''Turbo pascal'' (Win3.1), and it was on a Pentium 2(?) 233, and the computer was running all kinds of security junk that doesnt do anything anyway). my teacher said he was impressed that i was that creative...

Yes there are other sorts of sorts
Actually, it was kindof funny...

you will never get what you need to know from a teacher
Yeah, good point... i ask him a question every so often, but he''s usually too pre-occupied with other things to pay attention to what my problem is... thats why i visit gamedev frequently...

Share this post


Link to post
Share on other sites
just check this link :

http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

for arithmetic, there''s nothing matter if it''s written in C or Java or whatever

Share this post


Link to post
Share on other sites
Some other kinds of sorts:

Selection sort
Insertion sort
Radix sort
Shell sort
Merge sort
Quick sort

Merge sort and quick sort are the most efficient sorts... that I know of anyway.

Harry.

Share this post


Link to post
Share on other sites
quote:
Original post by omegasyphon

its basically the easiest sort to implement if not the slowest also


I made a slower sort once, called the ''random sort''.

basically, it randomly re-organizes the list until one of the organizations is in order.

lets see here, the efficiency was O(n^n), wheras bubble is O(n^2).

hehee.

===============================================
Hurry up madness, hurry up disease,
hurry up insanity, hurry up please.
Hooray! I say, for the end of the world.

Share this post


Link to post
Share on other sites
quote:
Original post by HarryW

Some other kinds of sorts:

Selection sort
Insertion sort
Radix sort
Shell sort
Merge sort
Quick sort

Merge sort and quick sort are the most efficient sorts... that I know of anyway.

Harry.


the heap sort is also on the order of O(nlogn) (quick, merge), and it doesnt require any recursion.

===============================================
Hurry up madness, hurry up disease,
hurry up insanity, hurry up please.
Hooray! I say, for the end of the world.

Share this post


Link to post
Share on other sites
Egads! What a trip down college memory lane.

I can''t believe somebody actually drooped the Big O into the discussion.

I won''t go back there! I won''t! You can''t make me!

OK, back to my database design work.. >;-)

Dustin

Share this post


Link to post
Share on other sites
Quick sort, thanks to its recursiveness, has a good "locality of reference", because it does linear runs through memory, whereas heapsort goes lots of times through the hole sort data, trashing the cache.

Share this post


Link to post
Share on other sites
depends on the processor. on highly optimised processors, yeah, thats true.

but simple processors (or most RISC processors) usually run through the heap sort better because the caching is not really efficient.


and dont forget that each function call generates overhead of its own.


btw, in reference to my ''random sort'', i figured out it is actually O(n!), not O(n^n) like i bragged about. sigh.

can anyone come up with a good O(n^n) sorting algorithm? .

===============================================
Hurry up madness, hurry up disease,
hurry up insanity, hurry up please.
Hooray! I say, for the end of the world.

Share this post


Link to post
Share on other sites
quote:
Original post by Mithrandir
can anyone come up with a good O(n^n) sorting algorithm?



Take your original random method, but when placing each element, take it from the original set of elements, not the remaining set. Much easier because you don''t have to keep looking up what''s already been placed.

Share this post


Link to post
Share on other sites
The claim that quicksort is the fastest is a very valid one, except in special cases, most of which cannot be forecasted. For instance, if you had an array of elements with only the last two swapped (i.e. 1 2 3 4 5 6 7 9 8), then an optimized insertion sort (which is usually n^2 time) would be only n+1 time whereas the quicksort is always n log n time as far as I can remember. I always use quicksort due to its reliable nature.

One last note: Mergesort is only effective when you have two separate volumes of pre-sorted data to make one large sorted volume made of the two smaller volumes.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
A little "bubble" variation that does the same... This way is easier to remember for me

for(int i = 0; i < n - 1; i++)
{
for(int j = i; j < n ; j++)
{
if(array > array[j])
// assume a function that switches two variables...
swap(array[i], array[j]);
}
}


EDU

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
A little "bubble" variation that does the same... This way is easier to remember for me

for(int i = 0; i < n - 1; i++)
{
for(int j = i; j < n ; j++)
{
if(array > array[j])
// assume a function that switches two variables...
swap(array[i], array[j]);
}
}


EDU

Share this post


Link to post
Share on other sites
The bubble sort is the easiest to implement and it is also the smallest to code. In college we had a program to write in (VMS) asm - the objective was to make it as small as possible and input/sort/output 10 integers. Everyone used a bubble sort because it takes ~6lines of asm.

The insertion sort is faster than a quick or merge sort on nearly sorted data - much faster if you know the list is already sorted.

And the quick sort ain''t so quick when it''s done with recursive functions - for the same reason recursive FFTs are hideously slow.

Magmai Kai Holmlor
- The disgruntled & disillusioned

Share this post


Link to post
Share on other sites
The fast quick sort appears to quicksort the data until it''s in an almost-sorted state, then switches to an insertion sort. Seems quite effecient to me.

If you really want to get a good idea of how long it all takes, use a profiler.

Share this post


Link to post
Share on other sites