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