macOS Sorting Singly Linked List in C++

[LtRammstein]

Hey all! I want to know if you can help me with something. I'm creating a singly linked list to be sorted. I can change it to a doubly linked list if need to. At the moment my Bubble Sort function sorts it well, but when I try and print it out again, there's double of one number, I remember seeing this kinda problem a year ago, but I don't remember how I fixed it.

Also, if you can suggest a better way to sort it, please do! Also incorporate on how I would go about writing the function as a linked list.

Thanks!

Here's the code:

#include <iostream>

using namespace std;

struct Node {

	Node * next;
	int data;
	
	Node(Node * ptr = NULL, int _data = 0) : next(ptr), data(_data) {}
};

void insert(Node * &ptr, int d) {
	ptr = new Node(ptr, d);
	
}
	
void display(Node * ptr) {
	Node * curr = ptr;
	cout << "{";
	while(curr != 0) {
		cout << curr->data;
		if(curr->next != NULL)
			cout << ", ";
		curr = curr->next;
	}
	cout << "}" << endl;
}

void sortNodes(Node * ptr) {
	Node * temp = ptr;
	Node * curr;
	for(bool didSwap = true; didSwap; ) {
		didSwap = false;
		for(curr = ptr; curr->next != NULL; curr = curr->next) {
			if(curr->data > curr->next->data) {
				temp->data = curr->data;
				curr->data = curr->next->data;
				curr->next->data = temp->data;
				didSwap = true;
			} 
		}
	}
}

int main () {
	int input;
	Node * newNode;
	
	cout << "Enter as many numbers as you want for the linked list. It will"
		<< "automatically sort it. Press -1 to quit." << endl;
	while(true) {
	cin >> input;
		if(input == -1)
			break;
		insert(newNode, input);
	}
	
	cout << "The list is: ";
	display(newNode);
	cout << endl;
	
	cout << "The sorted list is: ";
	sortNodes(newNode);
	display(newNode->next);
	cout << endl;
	
	return 0;
}

 

[Catfish_Man]

Here's one off-the-top-of-my-head way of doing a non-inplace sort on a linked list. Pardon the lack of encapsulation, mix of C and C++ idioms, etc...

void List::insertSorted(Node *n, Node *curr, Node *prev)
{
      if(!this->root)
      {
           Node *copy = new Node(n);
           this->root = copy;
      }
      else if(n->value < curr->value &&  (!prev || n->value > prev->value))
      {
           Node *copy = new Node(n);
           prev->next = copy; 
           copy->next = curr;
      }
      else
           insertSorted(n, curr->next, curr);
}

List* List::sortList(List *oldList)
{
      List *newList = new List();
      Node *n = oldList->root;
      do
      {
           newList->insertSorted(n);
      } while(n = n->next);
      return newList;
}

 

[szark]

Are you sure the sort routine is working correctly? Because this seems like it will cause a problem:

void sortNodes(Node * ptr) {
	[B]Node * temp = ptr;[/B]
	Node * curr;
	for(bool didSwap = true; didSwap; ) {
		didSwap = false;
		for(curr = ptr; curr->next != NULL; curr = curr->next) {
			if(curr->data > curr->next->data) {
				temp->data = curr->data;
				curr->data = curr->next->data;
				curr->next->data = temp->data;
				didSwap = true;
			} 
		}
	}
}

By initializing temp to ptr, you are overwriting the first data node every time you swap values.

I would think you would want this:

[B]Node * temp = new Node();[/B]

or this:

void sortNodes(Node * ptr) {
	[B]int temp = 0;[/B]
	Node * curr;
	for(bool didSwap = true; didSwap; ) {
		didSwap = false;
		for(curr = ptr; curr->next != NULL; curr = curr->next) {
			if(curr->data > curr->next->data) {
				[B]temp = curr->data;[/B]
				curr->data = curr->next->data;
				[B]curr->next->data = temp;[/B]
				didSwap = true;
			} 
		}
	}
}

(Disclaimer: I don't program in C++. I'm using my knowledge of C and Java to interpret your code.)

 

[LtRammstein]

Hey, thanks for the replies. It worked! Thanks szark! I should've known that, LOL!

 

[MarkCollette]

Personally, I'd be more partial to an insertion sort, instead of a bubble sort, for a singly linked list. Basically, just linearly iterate over the original unsorted linked list, taking each node off. Then put them into a new sorted list, where you just iterate over it until you find the insertion point. Worst case scenario, your original list was already sorted, so every insertion requires traversing the new list.

Insertion operations:
0 + 1 + 2 + 3 + ... + (n-2) + (n-1) + n
==> (n/2) * n
==> (n^2)/2

Plus, the operations for traversing the original list:
==> n

So, we have O( (n^2)/2 + n )

Of course, we could address that by keeping a pionter to the last node in the new sorted list, and specifically checking it before iterating down the whole list. In that case, the sort would take O( 2n ) operations, which would also be the best case scenario.

Also, the memory overhead is a single new root node pointer, and possibly a tail node pointer, and all of those operations are basically just pointer dereferences or pointer assignments, which are pretty cheap.