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.

Linked List

Linked lists are important topics in computer science. The theory behind them is something that computer science students learn in classes like data structures and algorithms. I have created a linked list for you to study. It is fairly simple, but has the necessary methods to expand to it with a BubbleSort algorithm etc.

The following picture explains the idea behind a linked list.

Basically you have a list of these things called Nodes that are linked together. Each node is a bucket of sorts that contains a piece of data. A Linked List is a group of these buckets strung together one at a time. The head bucket is linked to the 2nd bucket, the 2nd bucket is linked to the 3rd and so on until you get to the tail bucket which isn't linked to anything.

Currently I am implementing the following methods on the linked list:
-addAtHead(Object) - creates a node and adds it to the beginning of the linked list as the head Node
-addAtTail(Object) - creates a node and adds appends it to the end of the list as the tail Node
-addAtIndex(Object) - creates a node with Object as its data and adds the node at the index
-addAtIndex(Node) - adds the node at the index
-deleteAtIndex(int index) - deletes the node at the index
-switchWithNext(int index) - switches the current index with the one right after it. This is used by the bubble sorting algorithm.
-printList() - prints out the whole LinkedLIst
-find(Node) - returns index
-find(index) - returns Node
-getSize

To Do:
-Sorting by different algorithms(bubble sort, selection sort etc.)