Brief explanation of Quick Sort algorithm
@manish-r2Hoep
•
Oct 22, 2024
Oct 22, 2024
1.1K
On request of one user from ce,i am going to explain one of the most commonly used sorting algorithm ie quick sort
It is based on Divide and conquer approach.
It is one of the common practical example of recursion
There are generally 3 steps in this
1:-Divide a problem a multiple sub problems
2:-Solve them individually.
3:-Merge those sub problems to find solution of main problem
Algorithm
1. Choose any key element in an array which is know a pivot.
2. Reorder the array such that that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it. After the partitioning, the pivot is in its final position.
3. Recursively reorder two sub-lists: the sub-list of lesser elements and the sub-list of greater elements.
Below is the program written in c++ ,it can help you for better understanding
//Program for Quicksort
#include<iostream.h>
#include<conio.h>
int partition(int a[],int,int);
void quick(int a[],int,int);
void main()
{
int *a,n,i;
cout<<"Enter size of array"<<endl;
cin>>n;
a=new int[n];
cout<<"Please enter elements for array"<<endl;
for(i=0;i<n;i++)
{
cin>>a;
}
quick(a,0,n-1);
cout<<"Elments are"<<endl;
for(i=0;i<n;i++)
{
cout<<a<<endl;
}
getch();
}
void quick(int a[],int start,int finish)
{
if(start<finish)
{
int q=partition(a,start,finish);
quick(a,start,q-1);
quick(a,q+1,finish);
}
}
int partition(int a[],int start,int finish)
{
int x=a[finish],temp,temp1,j;
int i=start-1;
for(j=start;j<=finish-1;j++)
{
if(a[j]<=x)
{
i=i+1;
temp=a;
a=a[j];
a[j]=temp;
}
}
temp1=a[i+1];
a[i+1]=a[j];
a[j]=temp1;
return (i+1);
}
It is based on Divide and conquer approach.
It is one of the common practical example of recursion
There are generally 3 steps in this
1:-Divide a problem a multiple sub problems
2:-Solve them individually.
3:-Merge those sub problems to find solution of main problem
Algorithm
1. Choose any key element in an array which is know a pivot.
2. Reorder the array such that that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it. After the partitioning, the pivot is in its final position.
3. Recursively reorder two sub-lists: the sub-list of lesser elements and the sub-list of greater elements.
Below is the program written in c++ ,it can help you for better understanding
//Program for Quicksort
#include<iostream.h>
#include<conio.h>
int partition(int a[],int,int);
void quick(int a[],int,int);
void main()
{
int *a,n,i;
cout<<"Enter size of array"<<endl;
cin>>n;
a=new int[n];
cout<<"Please enter elements for array"<<endl;
for(i=0;i<n;i++)
{
cin>>a;
}
quick(a,0,n-1);
cout<<"Elments are"<<endl;
for(i=0;i<n;i++)
{
cout<<a<<endl;
}
getch();
}
void quick(int a[],int start,int finish)
{
if(start<finish)
{
int q=partition(a,start,finish);
quick(a,start,q-1);
quick(a,q+1,finish);
}
}
int partition(int a[],int start,int finish)
{
int x=a[finish],temp,temp1,j;
int i=start-1;
for(j=start;j<=finish-1;j++)
{
if(a[j]<=x)
{
i=i+1;
temp=a;
a=a[j];
a[j]=temp;
}
}
temp1=a[i+1];
a[i+1]=a[j];
a[j]=temp1;
return (i+1);
}
