#define huge /* Remove if using PC */
#define length 200000L

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

long int pivot(long int len,long int huge tab[])
{
  long int i,j,v;
  if (len<=1) return 0L;
  j=0L;
  for (i=1L;i<len;i++) {
    if (tab[i]<tab[0L]) {
      v=tab[++j];
      tab[j]=tab[i];
      tab[i]=v;
    }
  }
  v=tab[j];
  tab[j]=tab[0L];
  tab[0L]=v;
  return j;
}

void quicksort(long int len,long int huge tab[])
{
  long int p;
  if (len<=1L) return;
  p=pivot(len,tab);
  quicksort(p,tab);
  quicksort(len-p-1L,&tab[p+1L]);
}

void heapsort(long int len,long int huge tab[])
{
  long int i; /* Indicates length of heap */
  long int j,v;
  /* First heap */
  for (i=1L;i<=len;i++) {
    j=i;
    while (j>1) {
      if (tab[j-1]<=tab[j/2-1]) break;
      v=tab[j-1];
      tab[j-1]=tab[j/2-1];
      j/=2;
      tab[j-1]=v;
    }
  }
  /* Then unheap */
  for (i=len;i>=1L;i--) {
    v=tab[(j=1)-1];
    tab[j-1]=tab[i-1];
    tab[i-1]=v;
    while (1) {
      if (j*2>i-1) break;
      if (j*2==i-1) {
	if (tab[j-1]<tab[j*2-1]) {
	  v=tab[j-1];
	  tab[j-1]=tab[j*2-1];
	  j*=2;
	  tab[j-1]=v;
	}
	break;
      }
      if ((tab[j-1]<tab[j*2-1])||(tab[j-1]<tab[j*2])) {
	if (tab[j*2-1]>=tab[j*2]) {
	  v=tab[j-1];
	  tab[j-1]=tab[j*2-1];
	  j*=2;
	  tab[j-1]=v;
	}
	else {
	  v=tab[j-1];
	  tab[j-1]=tab[j*2];
	  j*=2; ++j;
	  tab[j-1]=v;
	}
      }
      else break;
    }
  }
}

long int huge tab0[length];
long int huge tab[length];

int main()
{
  long int i;
  clock_t qs_b,qs_e,hs_b,hs_e;
  printf("Sorting %12ld entries.\n",length);
  /*randomize();*/
  for (i=0L;i<length;i++) {
    tab0[i]=(((long)rand())<<16)|((long)rand());
  }
  for (i=0L;i<length;i++) {
    tab[i]=tab0[i];
  }
  printf("Quicksort...");
  qs_b=clock();
  quicksort(length,tab);
  qs_e=clock();
  printf("done.\n");
  printf("Verification: ");
  for (i=0L;i<5;i++) {
    printf("%12ld",tab[i]);
  }
  printf("\n");
  printf("Time taken: %5.1f\n",((float)qs_e-(float)qs_b));
  for (i=0L;i<length;i++) {
    tab[i]=tab0[i];
  }
  printf("Heap sort...");
  hs_b=clock();
  heapsort(length,tab);
  hs_e=clock();
  printf("done.\n");
  printf("Verification: ");
  for (i=0L;i<5;i++) {
    printf("%12ld",tab[i]);
  }
  printf("\n");
  printf("Time taken: %5.1f\n",((float)hs_e-(float)hs_b));
  return 0;
}