Thread: Bubble Sort on a Singly Linked List

  1. #1
    Registered User
    Join Date
    Oct 2007
    Posts
    118

    Bubble Sort on a Singly Linked List

    Main:
    Code:
    #include <iostream>
    #include <fstream>
    #include <string>
    #include <iomanip>
    
    #include "StudentRecordDataNode.h"
    #include "Course.h"
    #include "StudentSingleListedLink.h"
    
    #define SIZE_BUF   15
    
    using namespace std;
    
    void sortNodes(StudentRecordDataNode * ptr);
    
    void main()
    {
    	double marks[18];
    	unsigned int Age;
        unsigned int ID;
        unsigned int CourseCount;
        char FirstName[10];
        char LastName[10];
    	Course Courses[18];
    	StudentRecordDataNode *node = 0;
    	StudentSingleListedLink iList;
    	StudentRecordDataNode *nd = 0;
    	ifstream is;
    	is.open ("OOP344_Assignment_3_2011_01.dat", ios::binary );
    	do {
    		//beginning of saving records from the file
    		for(int i=0; i<18; i++)
    			marks[i] = 0;
    
    		is.read(reinterpret_cast<char *>(&marks), sizeof(double)*18);
    
    		is.read(reinterpret_cast<char *>(&Age), sizeof(Age));
    		is.read(reinterpret_cast<char *>(&ID), sizeof(ID));
    		is.read(reinterpret_cast<char *>(&CourseCount), sizeof(CourseCount));
    		is.read(reinterpret_cast<char *>(&FirstName), sizeof(FirstName));
    		is.read(reinterpret_cast<char *>(&LastName), sizeof(LastName));
    
    		for (int i=0; i < 18; i++)
    		{
    			is.read(reinterpret_cast<char *>(&Courses[i].Semester), sizeof(Courses[i].Semester));
    			is.read(reinterpret_cast<char *>(&Courses[i].Name), sizeof(Courses[i].Name));
    		}
    		//end of saving
    	
    		StudentRecordData *r;
    		r = new StudentRecordData(marks,Age,ID,CourseCount,FirstName,LastName, Courses);
    		node = new StudentRecordDataNode(r);
    		iList.AddNode(node);
    	} while (!is.eof());
    
    	//nd=iList.getFirstNode();
    	sortNodes(node);
    
    	for(nd=iList.getFirstNode();nd;nd=iList.getNextNode(nd))
    			nd->getValue()->display();
    
    	is.close();
    
    	cin.get();
    	return;
    }
    
    void sortNodes(StudentRecordDataNode * ptr) {
    	StudentRecordData * temp=0;
    	StudentRecordDataNode * curr;
    	for(bool didSwap = true; didSwap; ) {
    		didSwap = false;
    		for(curr = ptr; curr->next != NULL; curr = curr->next) {
    			if(curr->getValue()->getAge() > curr->next->getValue()->getAge()) {
    				temp = curr->getValue();
    				*curr->getValue() = *curr->next->getValue();
    				*curr->next->getValue() = *temp;
    				didSwap = true;
    			} 
    		}
    	}
    }

    StudentRecordDataNode.h
    Code:
    #ifndef STUDENTRECORDDATANODE_H
    #define STUDENTRECORDDATANODE_H
    #include "StudentRecordData.h"
    
    class StudentRecordDataNode
    {
    	StudentRecordData *Value;
    	friend class StudentSingleLinkedList;
    public:
    	StudentRecordDataNode *next;
    	StudentRecordDataNode();
    	StudentRecordDataNode(StudentRecordData *val)
    	{
    		Value = val;
    		next = 0;
    	}
    	StudentRecordData *getValue()
    	{
    		return Value;
    	}
    };
    #endif
    StudentSingleListedLink.h
    Code:
    #ifndef StudentSingleListedLink_H
    #define StudentSingleListedLink_H
    
    #include "StudentRecordDataNode.h"
    
    class StudentSingleListedLink
    {
    	StudentRecordDataNode *root;
    public:
    	StudentSingleListedLink();
    	~StudentSingleListedLink();
    	void AddNode(StudentRecordDataNode *);
    	StudentRecordDataNode *getFirstNode();
    	StudentRecordDataNode *getNextNode(StudentRecordDataNode *nd);
    };
    
    #endif
    StudentSingleListedLink.cpp
    Code:
    #include "StudentSingleListedLink.h"
    
    StudentSingleListedLink::StudentSingleListedLink()
    {
    	root = 0;
    }
    
    StudentSingleListedLink::~StudentSingleListedLink()
    {
    	StudentRecordDataNode *curr=root;
    	StudentRecordDataNode *next;
    	
    	while(curr)
    	{
    		next = curr->next;
    		delete curr;
    		curr = next;
    	}
    }
    
    void StudentSingleListedLink::AddNode(StudentRecordDataNode *nd)
    {
    	if(!root)
    	{
    		root = nd;
    		return;
    	}
    	nd->next = root;
    	root = nd;
    }
    
    StudentRecordDataNode *StudentSingleListedLink::getFirstNode()
    {
    	return root;
    }
    
    StudentRecordDataNode *StudentSingleListedLink::getNextNode(StudentRecordDataNode *nd)
    {
    	return nd->next;
    }
    StudentRecordData.h
    Code:
    #ifndef STUDENTRECORDDATE_H
    #define STUDENTRECORDDATE_H
    
    #include "Course.h"
    
    #define MAX_COURSES      18
    #define LEN_FN           10
    #define LEN_LN           10
    
    class StudentRecordData
    {
       double Marks[MAX_COURSES];
       unsigned int Age;
       unsigned int ID;
       unsigned int CourseCount;
       char FirstName[LEN_FN];
       char LastName[LEN_FN];
       Course  Courses[MAX_COURSES];
    public:
    	StudentRecordData();
    	StudentRecordData(double m[18], unsigned int age, unsigned int id, unsigned int cc, char fn[10], char ln[10], Course c[18]);
    	unsigned int getID() {return ID;}
    	unsigned int getAge() {return Age;}
    	void display();
    };
    
    #endif
    StudentRecordData.cpp
    Code:
    #include <iostream>
    #include <fstream>
    #include <string>
    
    #include "StudentRecordData.h"
    #include "Course.h"
    
    using namespace std;
    
    StudentRecordData::StudentRecordData(double m[18], unsigned int age, unsigned int id, unsigned int cc, char fn[10], char ln[10], Course c[18])
    {
    	for(int i=0;i<18;i++)
    		Marks[i] = m[i];
    
    	Age = age;
    	ID = id;
    	CourseCount = cc;
    	strcpy(FirstName, fn);
    	strcpy(LastName, ln);
    	for(int i=0;i<18;i++)
    	{
    		strcpy(Courses[i].Name,c[i].Name);
    		Courses[i].Semester = c[i].Semester;
    	}
    	
    }
    
    void StudentRecordData::display()
    {
    	for(int i=0; i<18; i++)
    	{
    		if (Marks[i] > -1)
    			cout << Marks[i] << " ";
    	}
    	cout << endl << "Age: " << Age << " ID: " << ID << " Course Count: " << CourseCount << " First Name: " << FirstName
    		<< " Last Name: " << LastName << endl;
    	for(int i=0;i<CourseCount;i++)
    	{
    		cout << Courses[i].Name << " ";
    	}
    	cout << endl<<endl;
    }
    the file needed to be read:
    Code:
         @Q@     €J@      O@     €L@     ΐX@     ΐS@     €Q@      O@     ΐQ@      N@      X@     €J@     ΐV@     @X@      M@      R@ΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜ   ؐ    Mitcha ΜΜΜAdru ΜΜΜΜΜAPC100 EAC150 ICA002 IOS110 IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 DCN455 ΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜ      J@     €W@      R@     €L@     @U@     ΐX@     €V@      Q@      O@     €K@     @S@     €T@     @T@     ΐU@      W@     @U@     ΐR@     €R@   Ί6    James ΜΜΜΜHarkley ΜΜAPC100 EAC150 ICA002 IOS110 IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 DCN455 EAC397 JAC444      ΐR@      P@     €W@     €Q@      L@     ΐP@      O@     €V@     @X@     ΐX@     €V@     €T@     ΐV@     @W@ΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜ"   βκ	    Jake ΜΜΜΜΜChoy ΜΜΜΜΜAPC100 EAC150 ICA002 IOS110 IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 ΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜ     €T@     €Q@     @X@     @P@     @P@     €T@     @U@     @U@     €L@      U@     €R@      R@     €M@     ΐQ@     €S@      I@      R@      J@   }T    David ΜΜΜΜHansen ΜΜΜAPC100 EAC150 ICA002 IOS110 IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 DCN455 EAC397 JAC444       T@     €Q@      S@      V@      L@     @T@     @V@      W@     ΐR@     €S@     €P@     @S@      L@     €O@     €M@      W@      T@      O@   |˜    Matt ΜΜΜΜΜFaria ΜΜΜΜAPC100 EAC150 ICA002 IOS110 IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 DCN455 EAC397 JAC444       L@      V@     @T@     €M@     ΐS@     €V@      X@      P@      N@      S@     ΐX@      X@      N@     ΐX@     ΐT@      I@     €K@ΜΜΜΜΜΜΜΜ   ξί    Maria ΜΜΜΜDallan ΜΜΜAPC100 EAC150 ICA002 IOS110 IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 DCN455 EAC397 ΜΜΜΜΜΜΜΜ     €N@     @X@      T@     €P@     @T@     ΐV@     €W@      T@     €Q@      R@      M@     €X@     @X@     €T@     €T@     @U@     €W@     @U@   ι	    Brandon ΜΜLay ΜΜΜΜΜΜAPC100 EAC150 ICA002 IOS110 IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 DCN455 EAC397 JAC444      €V@     €L@      J@     ΐX@     @P@     €U@     ΐV@     @Q@      J@      J@      P@     @P@     ΐR@     ΐS@     €I@ΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜ   Ξω    Bruno ΜΜΜΜCondello ΜAPC100 EAC150 ICA002 IOS110 IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 ΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜ     €J@      L@      M@     €U@     ΐX@     @T@     ΐS@     €V@     €S@     ΐT@      S@      V@     ΐR@     @P@      M@     ΐP@      S@     ΐQ@   ΗΡ
        Lui ΜΜΜΜΜΜDonghui ΜΜAPC100 EAC150 ICA002 IOS110 IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 DCN455 EAC397 JAC444       Q@     €I@     @Q@     @U@     @U@     ΐW@     @U@     ΐQ@     @R@     @R@     ΐS@     @S@      X@     ΐQ@      T@     €N@     €O@ΜΜΜΜΜΜΜΜ#   Ÿ8    Alex ΜΜΜΜΜChow ΜΜΜΜΜAPC100 EAC150 ICA002 IOS110 IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 DCN455 EAC397 ΜΜΜΜΜΜΜΜ     ΐV@     ΐR@      Q@     €K@      R@      V@      R@     @R@     @S@      V@     €T@     ΐR@     @X@ΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜ   i 
       Phuong ΜΜΜLy ΜΜΜΜΜΜΜAPC100 EAC150 ICA002 IOS110 IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 ΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜ     €U@     @W@     ΐS@     €M@     €Q@     @V@     ΐU@     ΐU@     ΐP@     €X@      Q@     €Q@     €W@     ΐV@     €M@     €M@     @W@ΜΜΜΜΜΜΜΜ   `β    Arthur ΜΜΜBradlow ΜΜAPC100 EAC150 ICA002 IOS110 IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 DCN455 EAC397 ΜΜΜΜΜΜΜΜ     @Q@      W@      S@     ΐU@     ΐX@      O@     €P@     €W@      M@     ΐP@     €N@     @V@      J@      T@     €O@     €R@ΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜ   gl    Roya ΜΜΜΜΜSakedad ΜΜAPC100 EAC150 ICA002 IOS110 IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 DCN455 ΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜ     @S@     €N@     @V@      J@     €N@     €M@     ΐX@      M@      K@     @S@     €S@      N@     ΐW@     @W@     @U@     @X@ΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜ   Κ½    Charles ΜΜBrady ΜΜΜΜAPC100 EAC150 ICA002 IOS110 IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 DCN455 ΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜΜ
    The problem lies in the sort. It is duplicating a few of the nodes multiple times. While it is in sorted order. A good bunch of the nodes are gone because a few where duplicated. Any suggestions?

  2. #2
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    Quote Originally Posted by bigmac(rexdale) View Post
    Any suggestions?
    Fix it!

    Now seriously, ask yourself: Why some nodes get duplicated while others are gone?
    Take a deep breath, dive into your code, and tell us what you found, ok?
    Devoted my life to programming...

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Don't try using bubble sort on a linked list. Though it is very easy for an array, it is far harder to get right with a linked-list. There are way more things that make it very very hard to get right, that you haven't even thought of.

    Implement Insertion Sort instead. It is the simplest linked-list sorting algorithm.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Oct 2007
    Posts
    118
    I checked up on insertion sort and got this so far:
    Code:
    void StudentSingleListedLink::AddNode(StudentRecordDataNode *nd)
    {
    	if(!root)
    	{
    		root = nd;
    		return;
    	}
    	else if (nd->getValue()->getAge() < root->getValue()->getAge())
    	{
    		nd->next = root;
    		root = nd;
    	}
    }
    is this correct? (well so far atleast?)

    Code:
    void StudentSingleListedLink::AddNode(StudentRecordDataNode *nd)
    {
    	if(root==NULL)
    	{
    		root = nd;
    		return;
    	}
    	else if (root->getValue()->getAge() <= nd->getValue()->getAge())
    	{
    		nd->next = root;
    		root = nd;
    	}
    	else if(root->getValue()->getAge() == NULL)
    	{
    		root->next = nd;
    	}
    	else
    	{
    		StudentRecordDataNode * current = root;
    		StudentRecordDataNode * going = current->next;
    		while(going!=NULL)
    		{
    			if(nd->getValue()->getAge() >= going->getValue()->getAge())
    			{
    				current->next = nd;
    				nd->next = going;
    			}
    			else
    			{
    				if(going->next == NULL)
    				{
    					going->next = nd;
    					going = going->next;
    					current = going;
    					going = current->next;
    				}
    				else
    				{
    					current = going;
    					going = current->next;
    				}
    			}
    		}
    	}
    }
    This is what i finished writing. Doesnt work though
    Last edited by bigmac(rexdale); 03-21-2011 at 01:32 PM.

  5. #5
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    #1. If you are going to use C-style strings (null terminated char arrays) then you should be including the <cstring> header and not the <string> header. The former holds the declarations of strcpy and the like, the later helps with using C++ std::string containers.


    #2. It should always be int main, not void main.


    #3
    Code:
    do {
        ...
    } while (!is.eof());
    Controlling loops with an end-of-file test usually is not the right way to do things 99.99999% of the time (link example is C but the lesson still applies to C++). Usually you want to directly test a read operation instead of EOF otherwise you sometimes may end up with a duplicate record being processed.


    #4 These (in red) don't need the ampersands:
    Code:
    //beginning of saving records from the file
    for(int i=0; i<18; i++)
        marks[i] = 0;
    
    is.read(reinterpret_cast<char *>(&marks), sizeof(double)*18);
    
    is.read(reinterpret_cast<char *>(&Age), sizeof(Age));
    is.read(reinterpret_cast<char *>(&ID), sizeof(ID));
    is.read(reinterpret_cast<char *>(&CourseCount), sizeof(CourseCount));
    is.read(reinterpret_cast<char *>(&FirstName), sizeof(FirstName));
    is.read(reinterpret_cast<char *>(&LastName), sizeof(LastName));
    
    for (int i=0; i < 18; i++)
    {
        is.read(reinterpret_cast<char *>(&Courses[i].Semester), sizeof(Courses[i].Semester));
        is.read(reinterpret_cast<char *>(&Courses[i].Name), sizeof(Courses[i].Name));
    }
    //end of saving
    You really don't need the casts on those lines either since these name fields are already effectively char pointers when used by themselves in the above context.


    #5 Would it be possible to attach the data file as well instead of a cut and past job?


    Haven't looked at anything else, just a brief glance.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  6. #6
    Registered User
    Join Date
    Oct 2007
    Posts
    118
    Fixed the following problems you stated and uploaded the .dat to sendspace:
    Code:
    http://www.sendspace.com/file/khr1rf

  7. #7
    Registered User
    Join Date
    Oct 2007
    Posts
    118
    anyone get a chance to check this out?

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Oh, it appears that rather than implement insertion sort, you're opting to insert each item into the correct place in the list immediately. I guess that's fine if you don't need to iterate over it in the unsorted order first, and this too is easier than doing bubble sort on a linked-list.

    The first two cases are okay, but I don't know why you have this case:
    Code:
    	else if(root->getValue()->getAge() == NULL)
    It doesn't make sense for getAge to return NULL.

    It should be a little shorter than what you have. It can certainly be done with only two if-statements. Having said that, can you follow through your logic with the debugger and try out some of the cases? Try inserting one item by itself, then another item before that, then another item after that etc and follow it through with a pen and paper if necessary.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User
    Join Date
    Oct 2007
    Posts
    118
    Code:
    void StudentSingleListedLink::AddNode(StudentRecordDataNode *nd)
    {
    	StudentRecordDataNode * current = root;
    	StudentRecordDataNode * temp = nd;
    	if(!root)
    	{
    		root = nd;
    	}
    	else if(root->getValue()->getAge() > temp->getValue()->getAge())
    	{
    		temp->next = root;
    		root = temp;
    	}
    	else
    	{
    		current = root;
    		while(current->next && current->getValue()->getAge() < nd->getValue()->getAge())
    		{
    			current = current->next;
    		}
    		nd->next = current->next;
    		current->next = nd;
    	}
    }
    I shortened it and it seems to work until age 22. Basically the first half is sorted but the remaining is unsorted. Ill try debugging it now but let me know if you find the problem.

  10. #10
    Registered User
    Join Date
    Oct 2007
    Posts
    118
    any one can help me out?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 07:47 PM
  2. Linked List Merge Sort
    By LostNotFound in forum C++ Programming
    Replies: 2
    Last Post: 02-17-2003, 10:34 PM
  3. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM
  4. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM