Bubblesort a Linked List

Sometimes when you're programming you just need to sort an array. You could use a built in function like any old schmuck; or you could whip out a shiny sorting algorithm and show off a little bit. Ok, so in all reality using a built in sorting function is most likely more efficient than building your own, but it is important to know what is going on behind the built in abstraction layer.

Today I am going to look at the bubblesort sorting algorithm. The main aspects I will be looking at are the Big-O analysis and general benchmarking.

Before I start I should give a basic summary of what big-O notation is and why it is used. Big-O notation is a way that computer scientists and mathematicians express the limits of a certain algorithm. Basically they show how an algorithm reacts to large data sets.

If you would like to read more, Wikipedia has a great article found here.
big-O

BubbleSort
Bubblesort is a simple "exchanging" algorithm. It starts at the first element of the data set and compares it to the second, if the first is greater it swaps them. It will then compare the second element to the third and so on until it reaches the end of the set. At this point we know that the last element is the largest element. The algorithm will then start at the first two elements of the set again and compare until it reaches the element before the end of the list (since we already decided that was the largest.) This pattern continues until the list is sorted.

As you may have guessed, this is not a very efficient algorithm for sorting a large data set. Bubblesort is rarely used due to this fact, however it does offer several small advantages - it uses a relatively small amount of code and can reach decent efficiency with an almost sorted data set.

Here is the code to the bubbleSort method I came up with. It requires the files LinkedList.java and ArrayFromFile.java which I posted about a week ago. The real meat of the program is in the method bubbleSort(LinkedList list). The main method is only there for testing purposes.

download a zip file with all the files you need to run the program

Code:

Bubblesort Stats:
Big-O best case: n
Big-O average case: n^2
Big-O worst case: n^2
Benchmark (100 elements in the collection): 7844 milliseconds (about 7.8 seconds)
This benchmark will likely be something completely different for you since it will be run on a different machine.