Quick sort Recursive Approch

There are many way to sort a list using quick sort concept .i.e recursive way & iterative way.

quick sort 

Recursive Approach

1. choose a no in the list a pivote
2. now sort list such that no less then pivote no. come on left of it & other on right
3. In above steps list break in two part . let left list as brand new list and repeat all steps(1,2,3).
4. do similar operation on right list as on left.

Now how to do Steps 2. there are many ways I did mention few of them..


Related post : bubble-sort-in-c

---

quick sort algorithm

Steps shown in image :

1. first we choose last element as pivote i.e. 66
2. Than move from left to right till encounter first no greater than pvote(66).
3. Than move from upper bound -1 to first no. encounter less than pivote (66).
4. Now swap element found in step 2 & step 3.
5. Repeat step 2,3,4 until encounter index of data found in step 2 is greater than thay of index of data in step 3
6. Now put pivote at divider position.by swapping to element found at step three in step 5.  

Note : see the Program given below carefully.follow all comments .And remember in our C program we take first element at pivote.

---

Better Understand : quick-sort-concept-algorithm

---

Quick Sort ( C++ Program ):

1. //Quick SOrt
2. //beginer2cs
3. #include<iostream>
4. #include<new>
5. using namespace std;
7. void Display(int *A,int n);
8. void Quick_sort(int *A,int p, int r);
9. int Partition(int *A,int p,int r);
11. int main(){
12.         int size,*arr;
13.         cout<<"Enter Size of list to sort : ";
14.         cin>>size;
15.        
16.         arr=new int[size]; //allocate space
17.         for(int i=0;i<size;i++){
18.                 cin>>arr[i];
19.         }
20.         Quick_sort(arr,0,size-1);
21.         Display(arr,size);
22.         return 0;
23. }
25. void Quick_sort(int *A,int p, int r){
26.                 int q;
27.                 if(p<r){
28.                         q=Partition(A,p,r);
29.        
30.                         Quick_sort(A,p,q-1); //left Subarray
31.                         Quick_sort(A,q+1,r); //right subarray
32.                 }
33. }
34. int Partition(int *A,int p,int r){
35.         int pivote=A[p]; //we choose first element as pivote
36.         int dn=p;
37.         int up=r;
38.         int temp;
39.         while(dn<up){
40.                 while(A[dn]<=pivote)
41.                         dn++;
42.                 while(A[up]>pivote) //important point
43.                         up--;
44.                 if(dn<up){
45.                         //swap dn & up index value
46.                         temp=A[dn];
47.                         A[dn]=A[up];
48.                         A[up]=temp;
49.                 }
50.                 else
51.                         break;
52.         }
53.         //put pivote at middle
54.         temp=A[up];
55.         A[up]=A[p];
56.         A[p]=temp;
57.         return up; //return index of pivote
58.        
59. }
60. void Display(int *A,int n){
61.         int i;
62.         cout<<"Dispaly Data :";
63.         for(i=0;i<n;i++){
64.                 cout<<A[i]<<" ";
65.         }
66.         cout<<endl;
67. }

Quick Sort Modified (C++)

1. //Quick SOrt
2. //Modified Partition function
3. #include<iostream>
4. #include<new>
5. using namespace std;
7. void Display(int *A,int n);
8. void Quick_sort(int *A,int p, int r);
9. int Partition(int *A,int p,int r);
10. void swap(int &a, int &b);
12. int main(){
13.         int size,*arr;
14.         cout<<"Enter Size of list to sort : ";
15.         cin>>size;
16.        
17.         arr=new int[size]; //allocate space
18.         for(int i=0;i<size;i++){
19.                 cin>>arr[i];
20.         }
21.         Quick_sort(arr,0,size-1);
22.         Display(arr,size);
23.         return 0;
24. }
26. void Quick_sort(int *A,int p, int r){
27.                 int q;
28.                 if(p<r){
29.                         q=Partition(A,p,r);
30.        
31.                         Quick_sort(A,p,q-1); //left Subarray
32.                         Quick_sort(A,q+1,r); //right subarray
33.                 }
34. }
35. int Partition(int *A,int p,int r){
36.         int pivote=A[r]; //we choose last element as pivote
37.         int i=p-1;
38.         int temp;
39.         for(int j=p;j<=r-1;j++){
40.                 if(A[j]<=pivote){
41.                         i++;
42.                         //swap A[i] & A[j]
43.                          temp=A[i];
44.                          A[i]=A[j];
45.                          A[j]=temp;
46.                 }
47.         }
48.        
49.         temp=A[i+1];
50.         A[i+1]=A[r];
51.         A[r]=temp;
52.         return i+1;
53. }
54. void Display(int *A,int n){
55.         int i;
56.         cout<<"Dispaly Data :";
57.         for(i=0;i<n;i++){
58.                 cout<<A[i]<<" ";
59.         }
60.         cout<<endl;
61. }