Saturday, 26 October 2013

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

Quick Sort Modified (C++)

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

No comments:

Post a comment

THANKS FOR UR GREAT COMMENT

Blogger Widgets