//==========================================================C
//  Speed test program for sort with integer                C
//    Two method are bubble sort and quicksort              C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2011/04/03              C
//        ( JAMSTEC ES Adviser & Waseda University )        C
//==========================================================C
#include <stdio.h>
#include <time.h>
int A1[1000000], A2[1000000];
//==========================================================C
//  bsort is a bubble sort                                  C
//    Bubble sort is a simple sort, but the speed is slow   C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2011/04/03              C
//        ( JAMSTEC ES Adviser & Waseda University )        C
//==========================================================C
void bsort(int n, int A[])
{int  k,j, W;
 for (j=0; j<n-1; j++) {
   for (k=j+1; k<n; k++) {
     if(A[j]>A[k]) {
       W=A[k]; A[k]=A[j]; A[j]=W; }
  } } 
}
//==========================================================C
//  quicksort is a quick sort                               C
//    qsort is a subprogram for quicksort                   C
//    quick sort is a high speed sort method                C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2011/04/03              C
//        ( JAMSTEC ES Adviser & Waseda University )        C
//==========================================================C
void qsort(int L, int R, int A[])
{ int k, j, P, W;
  k=L; j=R; P=A[L]; 
  while (1) {
    while (A[k] < P) { k++; }
    while (P < A[j]) { j--; }
    if (k >= j) break;     
    W=A[k]; A[k]=A[j]; A[j]=W;
    k++; j--; }
  if (L < k-1) qsort(L, k-1, A); 
  if (j+1 < R) qsort(j+1, R, A); }
void quicksort(int n, int A[])
{ qsort(0, n-1, A); } 
//==========================================================C
//  Speed test main program for sort with integer           C
//    Two method are bubble sort and quicksort              C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2011/04/03              C
//        ( JAMSTEC ES Adviser & Waseda University )        C
//==========================================================C
int main()
{ int  k, n;
  long long int T1, T2;
  double CPU;
// Input number of sort elements
  printf("Input n(<=1000000) \n");
  scanf("%d",&n);
// Make random integers of n
  for (k=0; k<n; k++)
    { A1[k] = rand(); A2[k] = A1[k]; }
// Test quick sort
  T1 = clock();
  quicksort(n, A1);
  T2 = clock();
  CPU = (double)(T2 - T1)/CLOCKS_PER_SEC ;
  printf("quick-sort, time=%6.2f (s)\n",CPU);
// Test bubble sort
  T1 = clock();
  bsort(n, A2);
  T2 = clock();
  CPU = (double)(T2 - T1)/CLOCKS_PER_SEC ;
  printf("simple-sort, time=%6.2f (s)\n",CPU);
  return 0;}