gistfile1.cpp

#include <iostream>

using namespace std;

class Node
{
public:
	int data;
	Node *next;

	bool operator >(Node &n)
	{
		return data > n.data;
	}

	bool operator <(Node &n)
	{
		return data < n.data;
	}
};


Node* addAfter(Node *node, int data)
{
	Node *newNode = new Node;
	newNode->data = data;
	newNode->next = node->next;
	node->next = newNode;
	return newNode;
}

Node* addFirst(Node *&start, int data)
{
	Node *newNode = new Node;
	newNode->data = data;
	newNode->next = start;
	start = newNode;
	return newNode;		
}

int getListSize(Node* start)
{
	int count = 0;
	while(start != NULL)
	{
		count++;
		start = start->next;
	}
	return count;
}

void bubbleSort(Node *&start) // <-- Pass a reference to pointer, because we may need to modify the start pointer.
{
	int size = getListSize(start);
	int i = 0;

	Node *lastSwapped = NULL;
	
	while(size--)
	{
		Node
			*current = start,
			*prev = NULL, // We are at the beginnig, so there is no previous node.
			*currentSwapped = NULL;

		while(current->next != lastSwapped) // We have at least one node (size > 0) so `current` itself is not NULL.
		{
			Node *after = current->next;
			if((*current) > (*after))
			{
				//swap the items
				current->next = after->next;
				after->next = current;
				if (prev == NULL) // we are at the beginning
					start = after;
				else
					prev->next = after;

				prev = after;
				currentSwapped = current;
			}
			else
			{
				prev = current;
				current = current->next;
			}
		}

		if (currentSwapped == NULL)
			break; // No swapping occured. The items are sorted.
		else
			lastSwapped = currentSwapped;
	}
}

void printList(Node *start)
{
	while(start != NULL)
	{
		cout << start->data << " ";
		start = start->next;
	}
}

int main()
{
	Node *myList = NULL;
	Node *n = addFirst(myList, 10);
	n = addAfter(n, 15);
	n = addAfter(n, 11);
	n = addAfter(n, 3);
	n = addAfter(n, 8);

	cout << "Original List:" << endl;
	printList(myList);
	cout << endl << "After sorting:" << endl;
	bubbleSort(myList);
	printList(myList);
	cout << endl;

	return 0;
}