Sorting (Part 1.0): Bubble Sort

Alright, NB community! Here we go... Bubble Sort.

What Is Bubble Sort?

Bubble Sort is a certain sorting algorithm that is often used as an introduction to sorting. It is not the best sorting algorithm, but it is very easy to implement and works fast with small sample sizes.

Bubble Sort works like this: go through an unsorted array. If one element is bigger than the next element, switch those elements. It does this through the entire array.

But, how do we know the array is sorted after just one run? We don't. We have to go through that array at most N times, where N is the size of the array to sort.

So, we cycle through the array again and swap values when an element is bigger than the one after it, meaning that a[k] > a[k+1] == true, where 0 <= k < N-1.

Follow this link for a visual representation of Bubble Sort.

Let's Implement the Algorithm...

Ruby

First Up: Ruby, because it's easier. Click "Ruby" to see the code on pastebin.

And here's a screenshot, if you'd like use this instead:

The first eight lines are just about taking input from the user. If you need this explained, PM me.

Line 9 declares a boolean called changes_made. As said in the comment, it's an optimization and is really not that important.

On Line 11, we start a for loop. I know, I know; you're going to say, "But oaktree, we don't use for loops in Ruby!" The for loop is preferential in this case because it explicitly denotes what we are doing, and helps to translate over to the C++ code I'll show you later.

Inside that for, we have another for, but with j instead of i, because we want to keep the value of i as a tracker for how many times we've looped through the array.

So, we continue in that nested for loop to swap the values if str[j] > str[j+1].

After we close out that nested for, we check if any changes were made by reading the value of changes_made. There's no reason to keep going through the array if it's already been sorted and, if the array is already sorted, the next round -- or the just-finished round -- of the nested for wouldn't have changed the array at all.

Then, we print out the result. Tada!

C++
Follow this link to the C++ implementation.

And, again, a screenshot:

Okay, one big different is that I've made a special bubblesort(...) function instead of writing it all inline. This is because I wanted to isolate the actual sorting from main().

Note: don't look through main() too closely, because that has all the gathering and processing of input.

In bubblesort(...), we have the same two, nested for loops. The notation of the loops changes slightly because C++ and Ruby are very different, syntax-wise. However, the algorithm is fundamentally the same.

Note: one big thing that may throw you off is the vector notation that you see inside bubblesort(...)'s parenthesis. vector<char>& vec means that our function takes a parameter that is a vector of characters. A vector is essentially an array, but it expandable and easier to manipulate than your typical C array, because it dynamically handles memory in almost all cases.

Anyway, treat the vector as an array for our purposes.

Conclusion

Well, I feel I have sufficiently explained Bubble Sort. Your "homework" is to compile and/or run the programs and test them out. If you stumble upon a bug, please PM me.

I want you guys to think about the complexity of Bubble Sort. Is it an efficient algorithm? Could we make it better? What are its limitations?

I'll be talking about complexity in the near future, but I figure I'd let you guys ponder the subject first.

Thanks NBers,
oaktree