Quick Sort

- Recursive sorting algorithm involves moving a data, called pivot. The algorithm
then partitions the array into two parts by moving the pivot into its correct position,
so that items to the pivot's left are smaller then the pivot, and the items to the right are bigger.

- The algorithm then is called recursively so that it will partition the two subordinate arrays
on either side of the pivot until the entire array is sorted.

PROGRAM WRITTEN IN C++ FOR BUBBLE SORT

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

int count=0;
void quick(int A[], int lb,int ub, int n);
void partition( int A[], int lb, int ub, int *pj);

main()
{
int A[20],no,lb=0,ub,n;

     cout << " Input n: " ;
     cin >> n;
     cout << "\n Input number : ";
     for(int i=0;i<n;i++)
     {     cin >>no;
            A[i]=no;
     }

      ub= n-1;
      quick(A,lb,ub,n);

getch();
return 0;

}

void quick(int A[], int lb,int ub, int n)
{ int j ;

if (lb >= ub)
return ; // array is sorted

partition(A,lb,ub,&j);
#include<iostream.h>
#include<string.h>
#include<conio.h>

int count=0;
void quick(int A[], int lb,int ub, int n);
void partition( int A[], int lb, int ub, int *pj);

main()
{
clrscr();
int A[20],no,lb=0,ub,n;
//A[0]=4;
//A[1]=3;
//A[2]=5;
//A[3]=9;
//A[4]=2;
//A[5]=7;
cout << " Input n: " ;
cin >> n;
cout << "\n Input number : ";
for(int i=0;i<n;i++)
{ cin >>no;
A[i]=no;
}
cout << "\n Sorted order : \n";
ub= n-1;
quick(A,lb,ub,n);
cout << "\n No of iteration : " << count ;
getch();
return 0;

}

void quick(int A[], int lb,int ub, int n)
{ int j ;

if (lb >= ub)
return ; // array is sorted

partition(A,lb,ub,&j);

    // partition the elements of the subarray such that one of the
    // elements (possibly A[lb] is now at A[j] ( j is an output
    // parameter ) and:
    // 1. A[i] <= A[j] for lb <= i<j
    // 2. A[i] >= A[j] for j < i <=ub
    //       A[j] is now at its final position

quick(A,lb,j-1,n);
// recursively sort the subarray between positions lb and j-1

quick(A,j+1,ub,n);
// recursively sort the subarray between positions j+1 and ub

cout << " ";
for (int k=0;k<n;k++)
cout << A[k] <<' ';

cout << '\n';

}

void partition( int A[], int lb, int ub, int *pj)
{ count++;
int a,down,temp,up,n;

a=A[lb+ub]; // a is the element whose final
// position is sought(seek)

up=ub;
down=lb;
while (down<up)
{ while (A[down] <= a && down <ub)
down ++; // move up the array

while (A[up] >a)
up--; // move down the array
if(down<up)
{
// interchange A[down} and A[up]

        temp=A[down];
        A[down]=A[up];
        A[up]=temp;

} // end if
} // end while

A[lb]=A[up];
A[up]=a;
*pj=up;

} // end partition

quick(A,lb,j-1,n); // recursively sort the subarray

// between positions lb and j-1
quick(A,j+1,ub,n); // recursively sort the subarray

// between positions j+1 and ub
}