//Tao class sap xep

#include<conio.h>

#include<stdio.h>

#include<iostream.h>

#include<math.h>

//----------

class sort

{

      protected:

              int n;

              int *a;

             void swap(int i, int j);

        public:

             virtual void solve(int &aa, int nn);

};

//---------

void sort::swap(int i,int j)

{

     int temp;

     temp=a[i];

     a[i]=a[j];

     a[j]=temp;

}

//-----------

void sort::solve(int &aa,int nn)

{

     a=&aa;n=nn;

}

//------

class ss:public sort

{

      public:

             virtual void solve(int &aa,int nn);

             void in(int &aa,int nn);

};

//----------

class is:public sort

{

      public:

             virtual void solve(int &aa,int nn);

             void in(int &aa,int nn);

};

//-------

class bs:public sort

{

      public:

             virtual void solve(int &aa,int nn);

             void in(int &aa,int nn);

};

//---------

class qs:public sort

{

      public:

             virtual void solve(int &aa,int nn);

             virtual void quicksort(int left,int right);

             void in(int &aa,int nn);

};

//-------

void ss::solve(int &aa,int nn)

{

     a=new int[100];

     a=&aa;n=nn;

     for(int i=0;i<n;i++)

     {

       for(int j=i+1;j<n;j++)

       {

               if(a[i]>a[j])

               swap(i,j);

       }

       }

}

//--------

void ss::in(int &aa,int nn)

{

     a=new int[100];

     a=&aa;n=nn;

     for(int i=0;i<n;i++)

     {cout<<a[i]<<" ";}

}

//----------

void is::solve(int &aa, int nn)

{

     a=new int[100];

     a=&aa;n=nn;

     int temp,j;

     for(int i=0;i<n;i++)

     {

        temp=a[i];

        j=i-1;

        while(a[j]>temp&&j>=0)

        {

           a[j+1]=a[j];j--;

        }

        a[j+1]=temp;

     }

}

//---------

void is::in(int &aa,int nn)

{

     a=new int[100];

     a=&aa;

     for(int i=0;i<nn;i++)

     {cout<<a[i]<<" ";}

}

//---------

void bs::solve(int &aa,int nn)

{

     a=new int[100];

     a=&aa;

     int k=0,i;

     i=1;

     while((k==0)&&(i<nn-1))

     {

         k=1;

         for(int j=nn-1;j>=i;j--)

         {

            if(a[j-1]>a[j])

            {swap(j-1,j);k=0;}

         }

         i++;

     }

}

//-----------

void bs::in(int &aa,int nn)

{

     a=new int[100];

     a=&aa;

     for(int i=0;i<nn;i++)

     {cout<<a[i]<<" ";}

}

//------------

void qs::quicksort(int left, int right){

        int i,j,k;

            i = left;

            j = right;

            k = a[left];

            while( i <= j){

                   while( a[i] < k && i < right ) i++;

                   while( a[j] > k && j > left ) j--;

                   if( i <= j ) {

                       swap(i,j);

                       i++;

                       j--;

                       }

                   }

            if( left < j ) quicksort(left,j);

            if( i< right ) quicksort(i,right);

       }

//---------

void qs::solve(int &aa, int nn){

       a = new int[100];

       a = &aa;

       quicksort(0,nn-1);

       }

//--------

void qs::in(int &aa, int nn){

       a = new int[100];

       a = &aa;

       for( int i = 0 ; i < nn ; i++ )

            cout<<a[i]<<" ";

            }

//--------

int main()

{

    int n,a[100];

    ss s1;

    is s2;

    bs s3;

    qs s4;

    srand(time(0));

    cout<<"

Nhap N: ";cin>>n;

    for(int i=0;i<n;i++)

    {a[i]=rand()%n;}

    cout<<"

Day so ban dau: ";

    for(int i=0;i<n;i++)

    {cout<<a[i]<<" ";}

    cout<<"

Day sau khi sx lua chon: ";

    s1.solve(*a,n);

    s1.in(*a,n);

    cout<<"

Day sau khi sx chen: ";

    s2.solve(*a,n);

    s2.in(*a,n);

    cout<<"

Day sau khi sx noi bot: ";

    s3.solve(*a,n);

    s3.in(*a,n);

    cout<<"

Day sau khi sx quicksort: ";

    s4.solve(*a,n);

    s4.in(*a,n);

getch();

}