Sorting a linked list

[DeathLeap]

Hello cpp!

I am working on a linked list program and I did AddItem, DeleteItem perfectly. I am having issues with the sorting function. It's not working.

Type of problem: undesired output.

This is the file that I read into linked list:

5.5
6.2
7.1
8.0
9.0
10.0
1.0
2.0
3.3
4.4

Here is my code:


#include <iostream>
#include <fstream>
#include <ostream>
#include <string>
#define MAX_ITEMS  10
typedef   float  ItemType;
typedef struct node* nodePtr;
using namespace std;

struct node
{
	ItemType data;
	node *next;
};

class SortedList3
{
private:
	nodePtr head;             // nodePtr = struct node*
	nodePtr curr;
	nodePtr temp;
	nodePtr end;
	int length;

public:
	SortedList3();
	~SortedList3(){};
	void MakeEmpty();
	void InsertItem(ItemType x);
	void SortList();
	void DeleteItem(ItemType x);
	void PrintList();
	bool IsFull();     
	int Lengthls();
	void RetrieveItem(ItemType &x, bool &found);
	void ResetList();
	void ReadFileToLinkedList();
};

SortedList3::SortedList3()
{
	head = NULL;
	curr = NULL;
	temp = NULL;
	length = 0; 
}

void SortedList3::SortList()
{
	if (head != 0)
	{
		curr = head;
		node* prev = 0;
		node* tempNode = 0;
		bool changeFlag = false;
		while (curr->next != 0)
		{
			tempNode = curr->next;

			if (curr->data > tempNode->data)
			{
				changeFlag = true;
				curr->next = tempNode->next;
				tempNode->next = curr;
				if (prev != 0)
				{
					prev->next = tempNode;
				}
				if (head == curr)
				{
					head = tempNode;
				}
				if (curr->next == 0)
				{
					end = curr;
				}

				else
				{
					prev = curr;
					curr = curr->next;
				}
			}

			if (changeFlag == false)
			{
				break;
			}

			else
			{
				prev = 0;
				curr = head;
				changeFlag = false;
			}
		}
	}
}
void SortedList3::InsertItem(ItemType x)
{
	nodePtr newNode = new node;
	newNode->next = NULL;
	newNode->data = x;

	if (head != NULL)
	{
		curr = head;
		while (curr->next != NULL)
		{
			curr = curr->next;
		}
		curr->next = newNode;
	}
	else
	{
		head = newNode;
	}
}

void SortedList3::DeleteItem(ItemType x)
{
	nodePtr delPtr = NULL;
	temp = head;
	curr = head;
	while (curr != NULL && curr->data != x)
	{
		temp = curr;
		curr = curr->next;
	}
	if (curr == NULL)
	{
		cout << x << " was not in the list.\n";
		delete delPtr;
	}
	else
	{
		delPtr = curr;
		curr = curr->next;
		temp->next = curr;
		if (delPtr == head)
		{
			head = head->next;
			temp = NULL;
		}
		delete delPtr;
		cout << "The value " << x << " was deleted.\n";
	}
}

void SortedList3::PrintList()
{
	curr = head;
	while (curr != NULL)
	{
		cout << curr->data << endl;
		curr = curr->next;
	}
}

void SortedList3::ReadFileToLinkedList()
{
	string line;
	ifstream myfile("float.txt");
	if (myfile.is_open())
	{
		while (getline(myfile, line))
		{
			InsertItem(atof(line.c_str()));
		}
		myfile.close();
	}
	else cout << "Unable to open file";
}

int main()
{
	SortedList3 Said;

	//reading txt file into linked list
	Said.ReadFileToLinkedList();
	

	//add item to the list
	Said.InsertItem(30);
	Said.InsertItem(20);
	Said.InsertItem(50);
	Said.InsertItem(25);

	//sort the list
	Said.SortList();

	//print the list
	Said.PrintList();

	//output to txt file


	system("Pause");
	return 0;
}

[wildblue]

I haven't checked all the code in the sort function, but I don't see where the value of the length variable ever changes from the 0 it is initialized to in the constructor. If length is 0, the code in the for loop won't execute.

for (int i = 0; i < length; i++)

[DeathLeap]

@wildblue

I removed the for loop, nothing changed in the code. I had the thought that that for loop was useless.

I still get the same result. I am pretty sure that the sort function has a problem but I just can't find it.

[wildblue]

I walked through with just the values you enter on line 187-190. The code ends up breaking out of the loop before it gets through all the nodes. Only the first two nodes get sorted if they are not in order. If the first two nodes are in order, the code will break out of the loop the first time through.

I find it helpful with linked list debugging to draw out the nodes with pencil and paper and follow what happens step by step with the pointers.

Which sorting algorithm are you trying to implement?

[DeathLeap]

I didn't have the intention to use any sorting algorithm, I just tried to do it myself..