/*******************************************************************************
QuickSort.cpp
Zhuo Wang.
*******************************************************************************/
 
#include <iostream>
#include <fstream>
#include "stdlib.h"
#include <ctime>
 
using namespace std;
 
template <class T>
long Partition(T* data, long* link, long low, long high, bool ascend)
{
  long i,j,k;
  long thresindex;
  bool tmpbool;
  thresindex=link[low];
  i=low;
  j=high;
  while(i<j)
  {
    do {
      i++;
      if(i>high-1) break;
      if(ascend)
        tmpbool=data[link[i]]<data[thresindex];
      else tmpbool=data[link[i]]>data[thresindex];
    } while(tmpbool);
    if(i>high-1) { j=high-1; break; }
 
    do {
      j--;
      if(j<low+1) break;
      if(ascend)
        tmpbool=data[link[j]]>data[thresindex];
      else tmpbool=data[link[j]]<data[thresindex];
    } while(tmpbool);
    if(j<low+1) { j=low; break; }
 
    if(i<j) {
      k=link[i];
      link[i]=link[j];
      link[j]=k;
    }
  }
  link[low]=link[j];
  link[j]=thresindex;
  return j;
}
 
template <class T>
void QuickSort(T* data, long* link, long low, long high, bool ascend)
{
  long mid=0;
  if(low<high)
  {
    mid=high+1;
    mid=Partition(data,link,low,mid,ascend);
    QuickSort(data,link,low,mid-1,ascend);
    QuickSort(data,link,mid+1,high,ascend);
  }
}
 
int main()
{
  long DATANUM=100000;
  long *data;
  long *link;
  long i;
  cout<<"Please input the total number of random-generated digits(default 100000):";
  cin>>DATANUM;
  if(DATANUM<1) DATANUM=100000;
 
  data=(long *)malloc(DATANUM*sizeof(long));
  link=(long *)malloc(DATANUM*sizeof(long));
 
  /* Create random numbers & initial the index in array "link" */
  srand((unsigned)(time(NULL)));
  for(i=0;i<DATANUM;i++)
  {
    data[i]=(rand()*10000+rand())%(DATANUM*2);
    link[i]=i;
  }
  cout<<endl;
 
  /* Sort! Then show how long of the sorting procedure! */
  clock_t start,end;
  double  duration;
  start=clock();
  QuickSort(&data[0],&link[0],0,DATANUM-1,1);
  end=clock();
  duration = (double)(end-start);
  cout<<"Time elapsed = "<<duration<<" ms!\n";
 
  /* Prlong results to screen! */
  ofstream out;
  char b[255];
  cout<<"Please input a filename to save the results:";
  cin>>b;
  out.open(b,ios::out);
  for(i=0;i<DATANUM;i++) {
    cout<<data[link[i]]<<" ";
    out<<data[link[i]]<<endl;
  }
  out.close();
  system("pause");
  return 0;
}