#include <stdio.h>

#define o n_comps++

/* as nossas listas terão elementos do tipo No */

typedef struct no_struct {
  long chave;
  struct no_struct *prox;
} No;

No *z; /* esta é a cauda de todas as listas */ 

long n_comps=0;

/* inicialize_cauda: esta rotina deve ser chamada antes de começarmos
   a manipular as nossas listas.  Note que aqui pomos LONG_MAX na chave de z
   para que ele possa fazer o papel de sentinela. */

void inicialize_cauda()
{
  z=(No *)malloc(sizeof(No));
  z->prox=z;
}

/* inicialize_lista: devolve um ponteiro para uma nova lista.  Devido
   a nossa convecao de que todas as listas terminam com z, isto é muito
   facil. */ 

No *inicialize_lista()
{
  return z;
}

/* insira: insere novo elemento no comeco da lista.  Note que devolvemos um
   ponteiro para o novo comeco da lista; não alteramos o ponteiro fornecido.
   */

No *insira(long v, No *comeco)
{
  No *x;
  x=(No *)malloc(sizeof(No));
  x->chave=v;
  x->prox=comeco;
  return x;
}

void quicksort(long *a, int l, int r)
{
  int i, j;
  long v, tmp;

  if (l<r) {
    v=a[l];
    i=l-1; j=r+1;
    while (1) {
      while (o,a[++i]<v) ;
      while (o,a[--j]>v) ;
      if (i>=j) break;
      tmp=a[i]; a[i]=a[j]; a[j]=tmp;
    }
    quicksort(a, l, j);
    quicksort(a, j+1, r);
  }
}

double H(long N)
{
  long k;
  double s=0.0;

  for (k=N; k>0; k--)
    s+=(double)1/k;

  return s;
}

/* main: nada muito excitante aqui... */

main()
{
  long k, n_els=0;
  long *v;
  int i;
  double aux;
  No *p;

  inicialize_cauda();
  p=inicialize_lista();

  while (scanf("%ld", &k)>0) {
    p=insira(k,p);
    n_els++;
  }

  v=(long *)malloc(n_els*sizeof(long));

  for (i=0; p!=z; i++,p=p->prox) 
    v[i]=p->chave;
    /* não vou fazer free aqui... */   
  
  quicksort(v,0,n_els-1);

  for (i=0; i<n_els; i++)  
    printf("%ld\n", v[i]); 

  aux=2*n_els*H(n_els)+n_els;

  printf("\nNumero de comparacoes entre chaves total: %ld\n", n_comps);
  printf("Numero esperado aproximado para entradas aleatorias: %.1f\nRazao: %.5f\n",
          aux, n_comps/aux); 

  return 0;
}