LinkedListBubbleSort.cpp

/*
This code is used to submit your assignment #4.
You need to implement another version of Bubble sort algorithm that works by swapping the pointers instead of swapping the data between the nodes. 
You are not allowed to modify the LinkedList Class, only complete class implementation.
Complete the missing lines, test your code, and then submit your answers.
Methods to be completed:
* sortBySwappingPointers()
*/

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime> 

using namespace std;

class LinkedList{
private:
	struct node{
		int id;
		node* next;
	};

	node* head;
	node* tail;
	int size;	// to keep track of the list size
public:
	LinkedList();
	void insertAtBeginning( const int addID);
	int getSize();
	void sortBySwappingPointers();
	void displayList();
};

// initialize head and tail pointers to NULL
LinkedList::LinkedList(){

	head = NULL;
	tail = NULL;
}

// to add a node at the beginning, we have two cases:
// 1. Empty list and 2. Non-empty list.
// if the list is empty we need to update both pointers head and tail.

void LinkedList::insertAtBeginning(const int addID){

	node* newNode = new node;
	newNode->id = addID;
	newNode->next = NULL;

	if(head == NULL){
		head = newNode;
		tail = newNode;
	}
	else{
		newNode->next = head;
		head = newNode;
	}

	size++;
}



// get the number of elements in the list
int LinkedList::getSize(){
	return size;
}

// create a temporary pointer and traverse the entire list
// do not use head pointer.

void LinkedList::displayList(){

	node* curr = head;

	while( curr != NULL){
		cout<<curr->id<< " -> ";
		curr = curr->next;
	}
	cout<<"NULL"<<endl;

}


// another version of Bubble sort algorithm
// your algorithm should not swap the data between
// nodes, only swap pointers.
// make sure that your code works in all cases.

void LinkedList::sortBySwappingPointers(){
	int size = getSize();
	int i = 0;

	//Decrease the size by one because last node does not need to be evaluated
	while (size--)
	{
		//Initialize curr and prevNode pointer to the beginning, nothing should be behind curr node
		node* curr = head,
			*prevNode = NULL; 

		// Run through all elements in the list until null
		while (curr->next != NULL) 
		{
			node* nextNode = curr->next;
			//Check which node is larger
			if ((curr->id) > (nextNode->id))
			{
				//swap the items
				curr->next = nextNode->next;
				nextNode->next = curr;
				if (prevNode == NULL) // we are at the beginning
					head = nextNode;
				else
					prevNode->next = nextNode;

				prevNode = nextNode;
			}

			//if values are already sorted evaluate next node
			else
			{
				prevNode = curr;
				curr = curr->next;
			}
		}
	}
}


int main(){

	LinkedList myList;
		
	int listSize, sid;
	cout<<"List will be generated randomly, insert list size .."<<endl;
	cin>>listSize;
	cout<<endl;

	if( listSize > 0 ){

		srand(time(NULL));
		for(int i=0; i < listSize ; i++)
			myList.insertAtBeginning( rand()%150 + 1 );

		myList.sortBySwappingPointers();
		myList.displayList();

	} else{

		cout<<"Invalid list size .."<<endl;
	}


	return 0;
}