Quick Sort is a Sorting Algorithm based on Divide And Conquer Technique. In this at every step element is placed in its proper position.It performs very well on a longer list. It works recursively, by first selecting a random "Pivot value" from the list. Then it partitions the list into elements that are less than the pivot and greater the pivot and greater than the pivot. The problem of sorting a given list is reduced to the problem of sorting two sublists It is to be noted that the reduction step in the quick sort finds the final position of particular element; which can be accomplished by scanning that last element of list from the right to left and check with the element.
Quick sort is Developed by C.A.B. Hoare. The main purpose of quick sort is to find the element that partitions the array into tow halves and to place it at its proper location in the array.
Working Of Quick Sort
Before we start the learning how quick sort works, we make some assumptions . Set the index of first element of array to LOC and LEFT variable and index of last element of the array to RIGHT variable. Then proceeds as follows :-
1. Start with element pointed to by Right. The array is scanned from right to left , comparing each element on the way with the element pointed by LOC till either.
( a ) Element smaller than the element pointed to by LOC is found and elements are interchanged . Procedure continues with Step2.
( b ) If the value of the RIGHT becomes equal to value of LOC, the procedure terminates here. This indicates that element is placed in its final position.
2. Start with element pointed to by LEFT. The array is scanned from left to right, comparing each element on the way with the element pointed by LOC till either.
( a ) Element greater than the element pointed to by LOC is found . In this case the elements are interchanged and procedure continues with step 1.
( b ) If the value of LEFT becomes equal to value of LOC , athea procedure terminates. This condition indicates that the element is placed in its final position
At the end of this procedure the first element ( PIVOT ) of original array is placed in its final location in the sorted array. The elements to its left will be less than this element and element to the right will be greater than this element . Now whole procedure that we applied on complete file will be applied on first subfile ( first index to LOC-1) and second (LOC + 1 to last index ) until we get the sorted array
Algorithm : QUICK SORT
Consider an Array( A ) with N elements having LB as lowerbound and UB as upperbound.
ALGORITHM : QUICK_SORT(A, LB, UB )
Step 1 If ( LB < UB ) then
P = SUB_ARRAY (A, LB, UB )
QUICK_SORT(A, LB, P-1 )
QUICK_SORT(A, P+1, UB )
Else
// Print sorted Array
Step 2 End
The above function is using the Divide and conquer strategy for algorithms. In above step we are dividing a large available Array named 'A' into smaller arrays and then we are passing these smaller arrays to SUB_ARRAY function that sorts the small list . And get back to Quick_Sort function and then again the divide the remaining list into another portion of a small array and then again take it to SUB_ARRAY function to sort this small array list in this way full or all elements of array are sorted
ALGORITHM : SUB_ARRAY(A, LB, UB )
Step 1 Set LEFT = LB,
Set RIGHT = UB,
Set LOC = LB
Step 2 Repeat step 3 and 4
Step 3 // Scanning Array from Right To Left
Repeat while A[LOC] <= A[ Right] and LOC != Right
Right = Right -1
( a ) If LOC == Right then
Return LOC
( b ) Interchange A [LOC] & A [RIGHT]
( c ) Set LOC == RIGHT
Explanation :- In Step 3 Array 'A' is scanned starting from Rightmost element of array and going towards the Left of array . In this step this algorithm finds the element which is greater the element at A[LOC] or pivot element and when element which is greater than pivot is found it is replaced with A[LOC] and LOC is set the Location of element with which we have replaced the location it means A[RIGHT] and else the Right is decremented by 1 until it comes to location same as LOC
Step 4 // Scanning Array from LEFT to Right
Repeat while A[LOC] >= A[LEFT] and LOC != LEFT
LEFT = LEFT +1
( a ) If LOC == LEFT then
Return LOC
( b ) Interchange A[LOC] and A[LEFT]
( c ) Set LOC = LEFT
Explanation :- In Step 4 Array 'A' is scanned starting from Leftmost element of array and going towards the Right of array . In this step this algorithm finds the element which is smaller the element at A[LOC] or pivot element and when element which is smaller than pivot is found it is replaced with A[LOC] and LOC is set the Location of element with which we have replaced the location means A[LEFT].
Step 5 End
Implementation of Quick Sort Algorithm in Cplusplus ( c++ ) Program
#include< iostream.h >
#include< conio.h >
int a[20], n, lb, loc, ub, left, right, temp, temp1;
void quicksort(int[10],int,int);
int pivot(int[],int,int);
void main()
{
cout<<"Enter size of array";
cin>>n;
cout<<"Enter Array Elements ";
for(int i=0;i<n;i++)
{
cin>>a[i];
}
quicksort(a,0,n-1);
for(int z=0;z<n;z++)
{
cout<<" "<<a[z];
}
getch();
}
void quicksort(int a[], int lb, int ub)
{
int p;
if(lb<ub)
{
p=pivot(a,lb,ub);
quicksort(a,lb,p-1);
quicksort(a,p+1,ub);
}
}
int pivot( int a[],int lb,int ub )
{
for(int z=0;z<n;z++)
{
cout<<" "<<a[z];
}
cout<<endl;
left =lb;
right = ub;
loc =lb;
cout<<"right is :- "<<right;
cout<<"\tloc is :-"<<loc;
cout<<"left is :- "<<left;
cout<<"Now right \n";
while((a[loc]<=a[right]) && (loc!=right))
{
right=right-1;
}
if(loc==right)
{
return loc;
}
temp=a[loc];
a[loc]=a[right];
a[right]=temp;
loc=right;
cout<<"Now left \n";
while((a[left]<=a[loc]) && (loc!=left))
{
left=left+1;
}
if(loc==left)
{
return loc;
}
temp1=a[loc];
a[loc]=a[left];
a[left]=temp1;
loc=left;
}
OUTPUT QUICK SORT PROGRAM |
| Output of Quick Sort Program |
For any type of more explanation to this program and for any suggest to this post you can freely comment . your comment are very crucial to us.