Sorting Singly Linked List in C++

Discussion in 'Mac Programming' started by LtRammstein, Nov 16, 2006.

  1. LtRammstein macrumors 6502a

    LtRammstein

    Joined:
    Jun 20, 2006
    Location:
    Denver, CO
    #1
    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:
    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;
    }
    
     
  2. Catfish_Man macrumors 68030

    Catfish_Man

    Joined:
    Sep 13, 2001
    Location:
    Portland, OR
    #2
    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...

    Code:
    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;
    }
    
     
  3. szark macrumors 68030

    szark

    Joined:
    May 14, 2002
    Location:
    Arid-Zone-A
    #3
    Are you sure the sort routine is working correctly? Because this seems like it will cause a problem:

    Code:
    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:
    Code:
    [B]Node * temp = new Node();[/B]
    or this:
    Code:
    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.)
     
  4. LtRammstein thread starter macrumors 6502a

    LtRammstein

    Joined:
    Jun 20, 2006
    Location:
    Denver, CO
    #4
    Hey, thanks for the replies. It worked! Thanks szark! I should've known that, LOL!
     
  5. MarkCollette macrumors 68000

    MarkCollette

    Joined:
    Mar 6, 2003
    Location:
    Calgary, Canada
    #5
    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.
     

Share This Page