Speed up development with full-stack environments for every branch.

Learn More

Sorting [C++]

Forked from Hello World C++ Example.

45 Runs 79 Views 9 Copies
Saved

Saved

tliu61 4

tliu61
published 2 years ago

    #include <iostream>
    #include <vector>
    static int qsortCount = 0;
    void
    swap(std::vector<int>& v, size_t i,size_t j)
    {
      std::cout<<"swaping "<<v[i]<<" and "<<v[j]<<std::endl;
      int temp = v[i];
      v[i] = v[j];
      v[j]=temp;
    }
    void
    qSort(std::vector<int>& v, size_t l,size_t r )
    {
      qsortCount++;
      using namespace std;
      cout<<"working on "<<l<<"<->"<<r<<endl;
    
        int p = v[(l+r)/2];
        cout<<"pivot("<<p<<")"<<endl;
        int i = l;
        int j= r;
        while(i <= j)
        {
        while(v[i]<p)i++;
        while(v[j]>p)j--;
        if(i<=j) 
        {
          swap(v,i,j);
          i++;
          j--;
        }
    
      }
          if( l < j)
        qSort(v,l,j);
        if( i < r )
        qSort(v,i,r);
    
    }
    
    void 
    quickSort(std::vector<int>& arr, int left, int right) {
      using namespace std;
       qsortCount++;
       cout<<"working on "<<left<<"<->"<<right<<endl;
          int i = left, j = right;
          int pivot = arr[(left + right) / 2];
      cout<<"pivot("<<pivot<<")"<<endl;
          /* partition */
          while (i <= j) {
                while (arr[i] < pivot)
                      i++;
                while (arr[j] > pivot)
                      j--;
                if (i <= j) {
                     swap(arr,i,j);
                      i++;
                      j--;
                }
          };
     
          /* recursion */
          if (left < j)
                quickSort(arr, left, j);
          if (i < right)
                quickSort(arr, i, right);
    }
    
    int main ()
    {
    
      using namespace std;
      vector<int> v;
      v.push_back(10);
      v.push_back(15);
      v.push_back(20);
      v.push_back(21);
      v.push_back(45);
      v.push_back(27);
      v.push_back(7);
      qSort(v,0,v.size()-1);
      //quickSort(v,0,v.size()-1);
     for(int i=0;i<v.size();++i)
      {
        cout<<"["<<i<<"]\t->"<<v[i]<<endl;
      }
      std::cout<<"qsort count("<<qsortCount<<")"<<std::endl;
      return 0;
    }
     
    Please login/signup to get access to the terminal.

    Your session has timed out.

    Dismiss (the page may not function properly).