Jump to content
  • Advertisement

Archived

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

Tsu

What the heck is a bubble sort?

This topic is 6302 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
// 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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!