- is there another kind of sort?
- why bubble?
- does it really make bubbles when you sort it?
What the heck is a bubble sort?
Author
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...
// 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...
}
}
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...
}
}
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
Here''s a few applets that show what''s going on.
Bubble Sort Applet
Another One
-------
Andrew
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.
Author
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...
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...
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
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
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
