The basic concept of a bubble sort is very simple - Go through the data, from the bottom. Take data in pairs. If the lower piece of data is larger than the higher one, swap them around. Repeat up to the top. Then, repeat the whole process, but stop one from the top, then 2... until you've run through all the data. The highest data basically 'floats' to the top, hence the name.
def Bubblesort(array)
size = array.size() # find the size of the array
pass = size
while pass > 2 # If we're down to less than 2 pieces of data to sort this won't work, and it's finished
(pass-1).times do |current|
if array[current] > array[current+1]
array[current],array[current+1] = array[current+1], array[current] # swap them around
end # if
end # times
end # while
return array
end
Get it now? It's not a very efficient algorithm, but it's easy to implement, and not bad if you need something in a hurry. (Also note that ruby has Array.sort, which sorts it automatically, but with a different, probably more effecient algorithm)Here's a C implementation as well, if it's easier to understand: (swap() is a nonexistent function, but you get the idea)
void BubbleSort(int *data, int size){ // pass an array with the data, this func works right onto the data.
int pass = size,k,current; //k for the iterator, instead of i, just for a change
while (;pass > 1;pass--)
for (k=0;k data[current+1])
swap(data[current],data[current+1]); // my nonexistent function
return;
}
Well, you should have it figured out by now. Hopefully you'll be able to use this somewhere, but with many of the OO languages coming out, you won't need it, the Array class (if it exists) has the sort function.
This article was originally written by rekless |
Copyright Open Source Institute, 2006 
