Brief explanation of Quick Sort algorithm
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
#include
int partition(int a[],int,int);
void quick(int a[],int,int);
void main()
{
int *a,n,i;
cout<<"Enter size of array"<
a=new int[n];
cout<<"Please enter elements for array"<
cin>>a;
}
quick(a,0,n-1);
cout<<"Elments are"<
cout<<
getch();
}
void quick(int a[],int start,int finish)
{
if(start
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
#include
int partition(int a[],int,int);
void quick(int a[],int,int);
void main()
{
int *a,n,i;
cout<<"Enter size of array"<
a=new int[n];
cout<<"Please enter elements for array"<
cin>>a;
}
quick(a,0,n-1);
cout<<"Elments are"<
cout<
getch();
}
void quick(int a[],int start,int finish)
{
if(start
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);
}
Replies
-
rishi0922its very helpful nd clearing many doubts -
Morningdot HabluNice post goyal.
Hope you come with more in future. -
paresh006Quick sort like merge sort,is based on divide and conquer paradigm..
Three steps are required to be done these are:-
Divide:-Suppose an array is A[p...r]...rearrange the array into two(possibly empty)subarrays A[p....q-1]and A[q+1...r] such that each element of A[p....q-1]is less than or equal to A[q],which is,in turn, less than or equal to each element of A[q+1...r]..compute the index q as part of this partitioning procedure.
Conquer:-Sort the two subarrays A[p...q-1]and A[q+1...r]by recursive calls to quicksort.
Combine:-Since the subarrays are sorted in place,no work is needed to combine them.the entire array A[p..r]is now sorted..
QUICKSORT(A,p,r)
1:if p
3: QUICKSORT(A,p,q-1)
4: QUICKSORT(A,q+1,r)
To sort an entire array A,the initial call is QUICKSORT(A,1,length[A]).
Partitioning the array
PARTITION(A,p,r)
1:x<-A[r]
2:i<-p-1
3: for j<-p to r-1
4: do if A[j]<=x
5: then i<-i+1
6: exchange A<->A[j]
7:exchangeA[i+1]<->A[r]
8:return i+1 -
BCA_GIRLThanks..........really its very useful.
-
anandkumarjhaFabulous job Goyal...It's easy to learn by this method
hope that you will bribg such useful stuff regularly
You are reading an archived discussion.
Related Posts
ٌWhat is it?
and where we can use it ?
British physicist Stephen Hawking has said that the creation of the universe was a result of the inevitable laws of physics and it did not need God's help.
In his...
I am B.E (C.S.E) Final year student, developing a project on E-Learning.
I have designed some modules like mail,e-library etc.
I was doing video conferencing in LAN.
I have little...
Google Chrome is celebrating its 2nd birthday and has released stable version 6. If you're using chrome, there's a chance that it has automatically updated itself.
Those who want to...
Hello, this is my first post here.
I am currently working with a Wheatstone bridge containing 1 JFET to sense atmospheric static fields, and the circuit is working. However, having...