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.

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.)

	/*============================================================================
	Name : LinkedList.java
	Author : Eric Swanson
	Date : Sep 7, 2011
	Version :
	Description :
	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/>.
	============================================================================*/
	class LinkedList
	{
	//Class variables for the Linked List
	private static Node head;
	private static int numNodes;
	public LinkedList(Object dat)
	{
	head = new Node(dat);
	}
	public void addAtHead(Object dat)
	{
	Node temp = head;
	head = new Node(dat);
	head.next = temp;
	numNodes++;
	}
	public void addAtTail(Object dat)
	{
	Node temp = head;
	while(temp.next != null)
	{
	temp = temp.next;
	}
	temp.next = new Node(dat);
	numNodes++;
	}
	public void addAtIndex(int index, Object dat)
	{
	Node temp = head;
	Node holder;
	for(int i=0; i < index-1 && temp.next != null; i++)
	{
	temp = temp.next;
	}
	holder = temp.next;
	temp.next = new Node(dat);
	temp.next.next = holder;
	numNodes++;
	}
	public void addAtIndex(int index, Node node)
	{
	Node temp = head;
	Node holder;
	for(int i=0; i < index-1 && temp.next != null; i++)
	{
	temp = temp.next;
	}
	holder = temp.next;
	temp.next = node;
	temp.next.next = holder;
	numNodes++;
	}
	public void deleteAtIndex(int index)
	{
	Node temp = head;
	for(int i=0; i< index - 1 && temp.next != null; i++)
	{
	temp = temp.next;
	}
	temp.next = temp.next.next;
	numNodes--;
	}
	public void switchWithNext(int index)
	{
	if(index != 0)
	{
	Node bOne = find(index - 1);
	Node one = find(index);
	Node two = one.next;
	one.next = two.next;
	bOne.next = two;
	two.next = one;
	}
	else
	{
	Node one = find(index);
	Node two = one.next;
	head = two;
	one.next = two.next;
	two.next = one;
	}
	}
	public static int find(Node n)
	{
	Node t = head;
	int index = 0;
	while(t != n)
	{
	index++;
	t = t.next;
	}
	return index;
	}
	public static Node find(int index)
	{
	Node temp=head;
	for(int i=0; i<index; i++)
	{
	temp = temp.next;
	}
	return temp;
	}
	public static void printList()
	{
	Node temp = head;
	while(temp != null)
	{
	System.out.print(temp.data + ",");
	temp = temp.next;
	}
	System.out.print("\n");
	}
	public static int getSize()
	{
	return numNodes;
	}
	class Node
	{
	//Declare class variables
	private Node next;
	private Object data;
	public Node(Object dat)
	{
	data = dat;
	}
	public Object getData()
	{
	return data;
	}
	}
	}

view raw LinkedList.java hosted with ❤ by GitHub