/**************************************************************************
  **************************************************************************

	 A C++ Program to illustrate the Quick Sort.

 **************************************************************************
 **************************************************************************/
 /*************************************************************************

	  By :
		Muhammad Tahir Shahzad  [ MTS ]
		B.C.S Honours  [ 2000-04 ]
		Government College University Lahore
		Pakistan

      E-mail :  mtshome@wol.net.pk

    Web-Site :  www.mts-home.cjb.net  [ www.wol.net.pk/mtshome ]
		www.mtshome.cjb.net   [ www.geocities.com/mtahirshahzad ]

  *************************************************************************/

 /*************************************************************************/
 /*************************************************************************/
 /****************************  Header Files  *****************************/
 /*************************************************************************/
 /*************************************************************************/

 # include <iostream.h>
 # include <conio.h>

 /*************************************************************************/
 /*************************************************************************/
 /***********************  Function Prototypes  ***************************/
 /*************************************************************************/
 /*************************************************************************/

 void swap(long &,long &);
 void quick_sort(long [],int,int);

 /*************************************************************************/
 /*************************************************************************/
 /*********************************  Main(  )  ****************************/
 /*************************************************************************/
 /*************************************************************************/

 main( )
    {
       clrscr( );

       const int array_size=10;

       long array[array_size]={0};

       cout<<"\n ******************************************************************************"<<endl;
       cout<<" ********************************  Quick Sort  ******************************"<<endl;
       cout<<" ******************************************************************************"<<endl;

       cout<<"\n * Array size = 10"<<endl;
       cout<<" * Data Type = long"<<endl;

       gotoxy(1,24);
       cout<<" ******************************************************************************";
       gotoxy(1,25);
       cout<<" ******************************************************************************";

       gotoxy(1,10);
       cout<<" Enter the array : "<<endl<<endl;

       for(int count_1=0;count_1<array_size;count_1++)
	  {
	     cout<<"\t Element["<<count_1<<"] = ";
	     cin>>array[count_1];
	  }

       quick_sort(array,0,array_size-1);

       gotoxy(40,10);
       cout<<" Sorted Array : ";

       for(int count_2=0;count_2<array_size;count_2++)
	  {
	     gotoxy(50,12+count_2);
	     cout<<"Element["<<count_2<<"] = "<<array[count_2]<<endl;
	  }

       getch( );
       return 0;

    }

 /*************************************************************************/
 /*************************************************************************/
 /***********************  Function Definitions  **************************/
 /*************************************************************************/
 /*************************************************************************/

 /*************************************************************************/
 //--------------------------  swap(long,long)  --------------------------//
 /*************************************************************************/

 void swap(long &element_1,long &element_2)
    {
       long temp=element_1;
       element_1=element_2;
       element_2=temp;
    }

 /*************************************************************************/
 //--------------------  quick_sort(long [],int,int)  --------------------//
 /*************************************************************************/

 void quick_sort(long array[],int first,int last)
    {
       if(first>=last)
	  {  }

       else
	  {
	     int middle=array[last];
	     int count_1=first-1;
	     int count_2=last;

	     while(count_1<count_2)
		{
		   do
		      {
			 count_1++;
		      }
		   while(array[count_1]<middle);

		   do
		      {
			 count_2--;
		      }
		   while(count_2>=0 && array[count_2]>middle);

		   if(count_1<count_2)
			 swap(array[count_1],array[count_2]);
		}

	     swap(array[count_1],array[last]);

	     quick_sort(array,first,count_1-1);
	     quick_sort(array,count_1+1,last);
	  }
    }

 /*************************************************************************/
 /*************************************************************************/
 /*******************************  THE END  *******************************/
 /*************************************************************************/
 /*************************************************************************/