Need help with selection sort for singly linked lists

[mhroseh]

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!

#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;
}

[AndiPersti]

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;
            }

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