Need help with selection sort for singly linked lists

This is a discussion on Need help with selection sort for singly linked lists within the C Programming forums, part of the General Programming Boards category; I've written code for a selection sort algorithm to sort through a singly linked list, However, it only brings the ...

  1. #1
    Registered User
    Join Date
    Feb 2013
    Posts
    1

    Need help with selection sort for singly linked lists

    I've written code for a selection sort algorithm to sort through a singly linked list, However, it only brings the smallest node to the front, but doesnt swap positions of any of the remaining nodes, even though they are not in order.

    Input list: 3 6 17 15 13 15 6 12 9 1 2 7 10 19 3 6 0 6 12 16

    Sorted list: 0 6 17 15 13 15 6 12 9 1 2 7 10 19 3 6 3 6 12 16

    Please help! Thanks!

    Code:
    #include<stdio.h>
    #include<stdlib.h>
    
    
    
    
    struct node{
    	int val;
    	struct node *next;
    };
    
    
    
    
    struct node* create_node(int val)
    {
    	struct node *first = (struct node*) malloc(sizeof(struct node));
    	first->val = val;
    	return first;
    }
    
    
    void print_list(struct node *first)
    {
    	for(;first; first = first->next)
    	{
    		printf("%d\n", first->val);
    	}
    }
    	
    struct node *create_list(int n)
    {
    	struct node *first, *node = NULL;
    	int i;
    	for (i=0; i<n; i++)
    	{
    		if(node)
    		{
    			node->next = malloc(sizeof(struct node));
    			node = node->next;
    		}
    		else
    		{
    			first = malloc(sizeof(struct node));
    			node = first;
    		}
    		node->val = rand() % n;
    	}
    	node->next = NULL;	
    	return first;
    }
    
    
    void selection_sort(struct node **first)
    {
    	struct node *head = *first, *i, *j, *min, *prev, *temp, *list_prev;
    	for(i = head; i->next; i = i->next)
    	{
    		min = i;
    		for(j = i; j->next; j = j->next)
    		{
    			if(j->next->val < min->val)
    			{
    				prev = j;
    				min = j->next;
    			}
    		}
    		if(min != i)
    		{
    			if(i == head)
    			{
    				temp = head->next;
    				head->next = min->next;
    				prev->next = head;
    				min->next = temp;
    				*first = min;
    			}
    			else
    			{
    				for(list_prev = head; list_prev->next; list_prev = list_prev->next)
    				{
    					if(list_prev->next == i)
    						break;
    				}
    				temp = i;
    				list_prev->next = min;
    				prev->next = temp;
    				temp->next = min->next;
    				min->next = i->next;
    			}
    		}
    	}
    }
    
    
    
    
    int main()
    {
    	struct node *first;
    	first = create_list(20);
    	print_list(first);
    	printf("done\n");
    	selection_sort(&first);
    	print_list(first);
    	return 1;
    }

  2. #2
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    Code:
    void selection_sort(struct node **first)
    {
        struct node *head = *first, *i, *j, *min, *prev, *temp, *list_prev;
        for(i = head; i->next; i = i->next)
        {
            min = i;
            for(j = i; j->next; j = j->next)
            {
                if(j->next->val < min->val)
                {
                    prev = j;
                    min = j->next;
                }
            }
            if(min != i)
            {
                if(i == head)
                {
                    temp = head->next;
                    head->next = min->next;
                    prev->next = head;
                    min->next = temp;
                    *first = min;
                }
    Quote Originally Posted by mhroseh View Post
    Input list: 3 6 17 15 13 15 6 12 9 1 2 7 10 19 3 6 0 6 12 16

    Sorted list: 0 6 17 15 13 15 6 12 9 1 2 7 10 19 3 6 3 6 12 16
    'i' and 'head' start out pointing at the same node (the beginning of your list). Your code finds the minimum value and 'min' points to it. After the for-loop 'i' and 'head' still point to the same node. Then you change "head->next" to point to "min->next" and consequently 'i->next' will also point to 'min->next'. Thus 'i' will point to the last 6 in your next iteration and since the other two values following it (12 and 16) are in order you don't change anything.

    Try to work out the algorithm on paper with just 3 or 4 nodes (it really helps to draw the boxes and arrows and changing the arrows step by step).

    Bye, Andreas

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How do i use singly linked lists to store name ..
    By uday.rnsit in forum C Programming
    Replies: 3
    Last Post: 04-10-2010, 01:08 PM
  2. Need help with FIFO Queue using Singly Linked Lists
    By astou in forum C++ Programming
    Replies: 6
    Last Post: 03-15-2008, 03:36 PM
  3. Singly Linked Lists: Clarification Needed
    By jedispy in forum C++ Programming
    Replies: 4
    Last Post: 12-14-2006, 05:30 PM
  4. eof in fstream & singly linked lists
    By mazo in forum C++ Programming
    Replies: 3
    Last Post: 06-03-2002, 10:50 AM
  5. Re: Singly Linked Lists
    By Linette in forum C++ Programming
    Replies: 2
    Last Post: 01-23-2002, 12:10 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21