How to do a Bubble sort

Bubble sort is one of the easiest sort algorithms. It is called bubble sort because the it will 'bubble' values in your list to the top (or bottom depending on how you think of it). While it is an easy sort, it is not nearly as efficient as more advanced sorts, and should only really be used for learning purposes (unless you know your list is almost sorted, in which case it's not bad)

Things You'll Need

• A computer that can compile some programming language OR
• Pencil and paper to go through the example

Instructions

1. I think the best way to discuss bubble sort is with an example. I'll give an overview of the algorithm, and then we'll work through an example step-by-step to give you an idea of how it works. So first, the idea.

2. Bubble sort is used to sort a list of items into ascending or descending order. Let's assume for this sort that you want to put the list in ascending order (i.e 1,2,3,etc.). The sort works by passing over each element in your list and comparing it to the next element in the list. If the first element is greater than the second element, the two are switched. If the first element is less than or equal to the second, nothing happens. After looking at this element, the next element is looked at, and the process repeats.

3. When the sort has looked at every element, one 'pass' has completed. After one pass, you know for sure that one number has to be in the correct position. In our ascending order, the greatest value will 'bubble' to the end of the list. Unfortunately, you don't know if the rest of the list is sorted, so you have to take another pass. However, on this pass, you can stop one element before the end since you know that number is already in the correct position.

4. Bubble sort (usually) requires several passes to complete. The most passes it will require is equal to the number of elements in the list minus 1. So if you have 10 elements in your list, it might take 9 passes to complete the sort. Let's go through an example to better explain it.

5. Let's use the following unsorted list:
   6, 3, 1, 8, 2, 4

   We would like the list to look like this:
   1, 2, 3, 4, 6, 8

   On the first pass, we'll compare the numbers one at a time, and we know that after one pass we should have the greatest number all the way to the right, so in this case, that will be 8. For our example, the ^ sign will point to the spot in the list that we are currently examining.

6. 6, 3, 1, 8, 2, 4

   Pass 1, Step 1) Compare the 6 and the 3. 6 is greater than 3, so we'll swap them.
   3,^6, 1, 8, 2, 4

   Pass 1, Step 2) Compare the 6 and the 1. 6 is greater than 1, so we'll swap them.
   3, 1,^6, 8, 2, 4

   Pass 1, Step 3) Compare the 6 and the 8. 6 is less than or equal to 8, so nothing happens.
   3, 1, 6,^8, 2, 4

   Pass 1, Step 4) Compare the 8 and the 2. 8 is greater than 2, so swap them.
   3, 1, 6, 2,^8, 4

   Pass 1, Step 5) Compare the 8 and the 4. 8 is greater than 4, so swap them.
   3, 1, 6, 2, 4, 8

   And you're done the first pass!

7. 3, 1, 6, 2, 4, 8 is hardly a sorted list, but you can see, as promised, the 8 is on the end. I'll now write out what the list looks like after each pass. Try it yourself, and see if yours matches mine:
   Pass 2: 1, 3, 2, 4, 6, 8 (looking better)
   Pass 3: 1, 2, 3, 4, 6, 8 (done)
   Pass 4: 1, 2, 3, 4, 6, 8 (umm ... weren't we already done?)
   Pass 5: 1, 2, 3, 4, 6, 8 (still done!)

8. As you can see, the list was sorted after 3 passes, but the bubble sort kept going. Why is that? Well, the basic bubble sort algorithm is pretty dumb. It wants to make sure that it will work in the worst case (which is a list that is completely backwards like 9, 8, 7, 6, 5). You can add a speed up to make your bubble sort run a bit faster. On each pass, have a flag that gets set to true ONLY if you actually switch two numbers. Before you do the next pass, check to see if the flag is true or false. If it's true, you swapped two numbers, and you have to do another pass. If it's false, your list is sorted, and you can be done. In our example, even though the list was sorted after 3 passes, we would still need to make a 4th pass because we made a swap in the 3rd pass.

9. Now you know how to do a bubble sort. Leave comments with any questions you might have. Thanks for reading!

Tips & Warnings

• If you're trying to implement bubble sort in a programming language, and you're having trouble, a pencil and paper can help you visualize what your algorithm is trying to do

• Remember, bubble sort is not a very efficient sort. So if you need to sort a huge list, you should look to some other methods.