/*
 * This code is (basically) from "Algorithms in C, Third Edition,"
 * by Robert Sedgewick, Addison Wesley Longman, 1998.
 */

#include <stdio.h>
#include <stdlib.h>

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

/* Prototipos das funcoes */

void imprima_lista(link p);

/* Programa principal */

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

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

  imprima_lista(b->next);

  return 0;
}

/* Implementacoes das funcoes */

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