#include <stdio.h>
#include <time.h>

#define LIST_SIZE 150

typedef struct _node {
   int data;
   struct _node *next;
} node;

node *createList ( int n )
{
   node *head, *p;
   int i;

   srand((unsigned int)time(NULL));

   /* Create the dummy node */
   head = (node *)malloc(sizeof(node));
   head -> data = 0;

   /* Initialize the running pointer p */
   p = head;

   /* Node creation loop */
   for (i=0; i<n; ++i) {
      /* Create the next node */
      p -> next = (node *)malloc(sizeof(node));
      p = p -> next;
      p -> data = 1 + rand() % 999;
   }

   /* Terminate the list */
   p -> next = NULL;

   return head;
}

void printList ( node *head , char prompt[] )
{
   node *p;
   int i = 0;

   printf("%s", prompt);
   p = head -> next;
   while ( p != NULL ) {
      printf("%3d ", p -> data);
      p = p -> next;
      if (++i == 20) { printf("\n"); i = 0; }
   }
   if (i) printf("\n");
}

void selSort ( node *head )
{
   node *p, *maxp, *last;
   int max;

   if ((head == NULL)                          /* Uninitialized list */
      || (head -> next == NULL)                /* Empty list */
      || (head -> next -> next == NULL))       /* List of one element */
      return;

   /* Search for maximum continues before the node pointed to by last */
   last = NULL;

   /* When there are two or more elements to check */
   while (last != head -> next -> next) {

      /* Initialize max value and pointer to the max node */
      maxp = p = head -> next;
      max = maxp -> data;

      /* Continue search for a bigger maximum */
      while (p -> next != last) {
         p = p -> next;
         if (p -> data > max) {
            /* Adjust the max value and the pointer to the max node */
            max = p -> data;
            maxp = p;
         }
      }

      /* Swap the last node's data with the max node's data */
      maxp -> data = p -> data;
      p -> data = max;

      /* Let last point to the previous node */
      last = p;
   }
}

int main ()
{
   node *head;

   head = createList(LIST_SIZE);
   printList(head,"\nThe list before sorting\n-----------------------\n");
   selSort(head);
   printList(head,"\nThe list after sorting\n----------------------\n");
}