Advertisement
Dani_info

Quick Sort

Sep 19th, 2019
201
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int nrcomp;
  6.  
  7. int pivot(int n, int a[100], int st, int dr)
  8. {
  9.     int i, j, di=0, dj=1;
  10.     i=st; j=dr;
  11.     while(i!=j)
  12.     {
  13.         if(a[i]>a[j])
  14.         {
  15.             swap(a[i], a[j]);
  16.             swap(di, dj);
  17.         }
  18.         i+=di;
  19.         j-=dj;
  20.         nrcomp++;
  21.     }
  22.     return i;
  23. }
  24.  
  25. int pivot1(int n, int a[100], int st, int dr)
  26. {
  27.     if(st==dr)
  28.         return st;
  29.     else
  30.         {
  31.             if(a[st]>a[dr])
  32.             {
  33.                 swap(a[st], a[dr]);
  34.                 return pivot1(n, a, st, dr-1);
  35.             }
  36.             else
  37.                 return pivot1(n, a, st+1, dr);
  38.             //nrcomp++;
  39.         }
  40. }
  41.  
  42. void quicksort(int n, int a[100], int st, int dr)
  43. {
  44.     int p;
  45.     if(st<dr)
  46.     {
  47.        p=pivot1(n, a, st, dr);
  48.        quicksort(n, a, st, p-1);
  49.        quicksort(n, a, p+1, dr);
  50.     }
  51. }
  52.  
  53. int main()
  54. {
  55.     int a[100], n, i;
  56.     cout<<"n="; cin>>n;
  57.     for(i=0; i<n; i++) cin>>a[i];
  58.     quicksort(n, a, 0, n-1);
  59.     //cout<<pivot1(n, a, 0, n-1)<<endl;
  60.     for(i=0; i<n; i++) cout<<a[i]<<" ";
  61.     cout<<"\n Nr. comparatii="<<nrcomp;
  62.     return 0;
  63. }
Advertisement
RAW Paste Data Copied
Advertisement