This week's lesson is on Sorting Algorithms. To take part in this lesson, you will need three things:
- A Table
- Three small objects varying in size
- A glass of water
First, place your three small objects on the table in front of you. Optionally, you may place the glass of water on the table, off to one side. If you choose not to place the glass of water on the table, place it on the floor, but be careful not to knock it over with your feet. Next, notice the three small objects on the table. Take into account the varying length, width, and depth of each object.
Now we will employ a method known as Estimation to determine the sizes of the objects. Remember the values you recorded on the varying length, width, and depth of each of the objects? Combine these values in numerical form per each object and you will have yourself a rough estimate of the size of each of these objects. Now, our goal here is to sort the small objects on the table in order from top to bottom in order of smallest to largest. If you need a break before we begin, take a sip of water from the glass of water.
Lets take a moment to understand more about Computer Science. Since Sorting Algorithms are algorithms that put elements of a list in a certain order, we are going to pretend that we are a computer, and we are unable to think as a human would. Therefore, we must rely on our programming and carry out this programming without error. (Teacher's note: Computers are incapable of making mistakes, they are capable only of following their programming. This means that you are not allowed to make mistakes.)
Finally, the sorting begins. We are going to use a Bubble sort to sort these three small objects that are sitting on your table. The Bubble sort gets it's name from the brilliant London Scientist Toby S. Alexander who was pouring himself a glass of water in 1956, when he noticed that smaller bubbles move quicker to the top than larger bubbles do*, a phenomenon you may have noticed yourself when pouring your glass of water for this exercise**. A Bubble sort works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted***. Say we have object 1, which we will refer to as "a", object 2 will be "b" just like a bee bee bee, and object 3 will be "c". The estimated size values we calculated earlier will directly follow our object identification letters (a,b,c.) This means, if a had a size value of 14, b had a size value of 10, and c had a size value of 3, we will call them a14, b10, and c3. Starting at the top, our bubble sort will take place as follows:
- Compare the next pair of adjacent objects.
- Swap the two objects if needed so that the lower value object is higher.
- Repeat until no swaps are needed.
Congratulations, you have completed your first Bubble sort! Toby S. Alexander would be proud.
In conclusion, the Bubble sort is just one of the many Sorting Algorithms at your disposal. We highly recommend utilizing these sorting algorithms in everyday life to accomplish a wide array of sorting goals. For all your difficult sorting tasks, we suggest the Bogosort as an extremely efficient sorting algorithm.
* no citation on bubble sort name origin available.
** probably not, huh?
*** Bubble sort from Wikipedia, The Free Encyclopedia http://en.wikipedia.org/wiki/Bubble_sort
Homework for this week
To further hone your sorting algorithm skills, this week's homework puts you in charge of an absolutely splendid doughnut bakery. Put to use what you've learned from this week's lesson and sort away!