#include "iostream.h"
#include "fstream.h"
#include "math.h"
#include "stdlib.h"

void qcksrt(int n, double arr[])
{
    int m = 7; int nstack = 50; int fm = 7875; int fa = 211;
	int fc = 1663; double a,fmi = 0.00012698413;
    int istack[51];
    int jstack = 0;
    int i,j,done,iq,l = 1;
    int ir = n;
    int fx = 0;
    do
	{
		if (ir - l < m)
		{
			for (j = l + 1; j<=ir; j++)
			{
				a = arr[j];
				for (i = j - 1; i>=1; i--)
				{
					if (arr[i] <= a)
					{
						break;
					}
					arr[i + 1] = arr[i];
				}
				if (arr[i] == 0)
				{
					i = 0;
				}
				arr[i + 1] = a;
			}
			if (jstack == 0)
			{
				return;
			}
			ir = istack[jstack];
			l = istack[jstack - 1];
			jstack = jstack - 2;
		}
		else
		{
			i = l;
			j = ir;
			fx = fx * fa + fc - fm * int((fx * fa + fc) / fm);
			iq = int (l + (ir - l + 1) * (fx * fmi));
			a = arr[iq];
			arr[iq] = arr[l];
			do
			{
				do
				{
					if (j > 0)
					{
						if (a < arr[j])
						{
							j = j - 1;
							done = 0;
						}
						else
						{
							done = -1;
						}
					}
				}while(!done);
				if (j <= i)
				{
					arr[i] = a;
					break;
				}
				arr[i] = arr[j];
				i = i + 1;
				do
				{
					if (i <= n)
					{
						if (a > arr[i])
						{
							i = i + 1;
							done = 0;
						}
						else
						{
							done = -1;
						}
					}
				}while(!done);
				if (j <= i)
				{
					arr[j] = a;
					i = j;
					break;
				}
				arr[j] = arr[i];
				j = j - 1;
			}while(1);
			jstack = jstack + 2;
			if (jstack > nstack)
			{
				cout<<"nstack must be made larger."<<endl;
				return;
			}
			if (ir - i >= i - l)
			{
				istack[jstack] = ir;
				istack[jstack - 1] = i + 1;
				ir = i - 1;
			}
			else
			{
				istack[jstack] = i - 1;
				istack[jstack - 1] = l;
				l = i + 1;
			}
		}
	}while(1);
}

void main()
{
    //program d7r9
    //driver for routine qcksrt
    double a[101];
	int i,j;
	ifstream fin;
	fin.open("d:\\vc常用數(shù)值算法集\\data\\tarray.dat",ios::in|ios::nocreate);
	if (!fin)
	{
		cerr<<"could not open d:\\vc常用數(shù)值算法集\\data\\tarray.dat"<<endl;
		exit(1);
	}
	for (i=1; i<=100; i++)
	{
		fin>>a[i];
	}
	fin.close();
    //print original array
    cout<<"Original array:"<<endl;
	cout<<endl;
    for (i = 1; i<=10; i++)
	{
        for (j = 1; j<=10; j++)
		{
			cout.width(7);
			cout.setf(ios::left);
            cout<<a[10 * (i - 1) + j];
        }
        cout<<endl;
    }
    //sort array
    qcksrt(100, a);
    //print sorted array
	cout<<endl;
    cout<<"Sorted array:"<<endl;
    for (i = 1; i<=10; i++)
	{
        for (j = 1; j<=10; j++)
		{
			cout.width(7);
			cout.setf(ios::left);
            cout<<a[10 * (i - 1) + j];
        }
        cout<<endl;
    }
}