Sorting with BubbleSort

Goals

By the end of this lab you should:

• Know how to implement the Bubble Sort algorithm.
• Have seen a handful of sorting algorithms in action.
• Have a basic idea of which sorting algorithms are faster than others.

Introduction

The bubble sort algorithm gets its name from the way in which the smaller elements "bubble" to the front of the list of items. It is one of the slowest sorting algorithms but is worth taking a look at because it is relatively easy to implement.

How the Algorithm Works

Given a list of items, the bubble sort algorithm walk from the beginning of the list to the end. At each item, if the next item in the list is smaller than the current one, the algorithm swaps the places of the two items.

If the algorithm walks the list one time for every element in the list, after all of the walks through the list are finished the elements will be in ascending order.

Why does doing as many walks through the list as there are elements ensure that the list will be ordered in the end?

Implementing the Algorithm

The natural way to implement the bubble sort algorithm is with two for loops; one nested inside the other. The inner loop represents a single walk through the list, and the outer loop represents the number of walks throught the list that must be made.

Optimizing Bubble Sort

The algorithm described here is often called "naive" bubble sort because it does not take advantage of the possibe optimizations that can be done in order to make bubble sort run faster. To lead you toward one of the simplest optimizations, consider the following questions: After the first walk through the list is finished, where is the largest element? Given the location of the largest element after the first walk, is it necessary to walk through the entire list of elements on the next iteration? If not, what part of the list can be ignored on the 2nd walk? ... on the 3rd? ...

Other Sorting Algorithms

There are many other sorting algorithms out there that are worth taking a look at; most notable is quick sort. The following link is to a page of java applets demonstrating a wide variety of sorts.

You may need to log into windows or use a java enabled browser for the applets to work properly, but it's definately worth it. Which applets seemed to run the fastest? Which ones were the slowest? What's behind the difference in running time of the different algorithms?