/*
 * This code is from "Algorithms in C, Third Edition,"
 * by Robert Sedgewick, Addison Wesley Longman, 1998.
 * (possibly with some small changes---check the book!)
 */
#include <stdio.h>
#include <stdlib.h>

typedef struct node* link;
struct node { int item; link next; };

void print_list(link t)
{
  for ( ; t; t = t->next) 
    printf("%d\n", t->item);
}

int main(int argc, char *argv[])
{
  int i, N = atoi(argv[1]);
  struct node heada, headb;
  link t, u, x, a = &heada, b;
  
  for (i = 0, t = a; i < N; i++) {
      t->next = malloc(sizeof *t); 
      t = t->next; t->next = NULL;
      t->item = rand() % 1000; 
    }
  printf("Lista original:\n");
  print_list(a->next);
  b = &headb; b->next = NULL;
  for (t = a->next; t != NULL; t = u) {
      u = t->next;
      for (x = b; x->next != NULL; x = x->next)
	if (x->next->item > t->item) break;
      t->next = x->next; x->next = t; 
    }
  printf("Lista ordenada:\n");
  print_list(b->next);
  return 0;
}