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:

	/*============================================================================
	Name : BubbleSort.java
	Author : Eric Swanson
	Date : Sep 10, 2011
	Version :
	Description :
	RequiredFile: LinkedList.java
	Copyright (C) 2011 Eric Swanson
	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.
	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	GNU General Public License for more details.
	You should have received a copy of the GNU General Public License
	along with this program. If not, see <http://www.gnu.org/licenses/>.
	============================================================================*/
	import java.util.*;
	import java.io.*;
	class BubbleSort
	{
	public static void main(String [] args) throws IOException
	{
	//Build a random LinkedList of integers
	LinkedList ll = new LinkedList(1);
	ArrayList<Integer> al = ArrayFromFile.getArrayFromFile("100");
	for(int i=0; i<al.size(); i++)
	{
	ll.addAtHead(al.get(i));
	}
	//Start the time, sort the LinkedList and stop the time
	long time = System.currentTimeMillis();
	bubbleSort(ll);
	time = System.currentTimeMillis() - time;
	//print the list
	ll.printList();
	//print time
	System.out.println("Program took: " + time + " milliseconds");
	}
	public static void bubbleSort(LinkedList list)
	{
	boolean unsorted = true;
	while(unsorted)
	{
	int topLimit = list.getSize();
	for(int i = 0; i < topLimit; i++)
	{
	int oneData = (Integer) list.find(i).getData();
	int twoData = (Integer) list.find(i+1).getData();
	System.out.println("Comparing " + oneData + " " + twoData);
	//If node one is greater than node two, switch them
	if(oneData > twoData)
	{
	list.switchWithNext(i);
	}
	list.printList();
	}
	topLimit--;
	unsorted = false;
	for(int i = 0; i < list.getSize(); i++)
	{
	int oneData = (Integer) list.find(i).getData();
	int twoData = (Integer) list.find(i+1).getData();
	if(oneData > twoData)
	{
	unsorted = true;
	}
	}
	}
	}
	}

view raw BubbleSort.java hosted with ❤ by GitHub

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.