Divide Et Impera Quick Sort

quicksort.cpp

/*

Sortare rapida: Quicksort

Big O Notation: n log n


v = [1,2,8,7,9];

Bubble Sort : O(n^2);

Insertion Sort : O(n^2);

Selection by Minimum: O(n^2) 


Quick Sort O(n log n);

Divide Et Impera

*/
#include <iostream>
#define FIN "algsort.in"
#define FOUT "algsort.out"
#define MAX  500005

using namespace std;

class QuickSort {

	  public:
	  QuickSort() {

	  	  read_data(); 

	  } 	

      void solve() {

      	   //cout<<"Algoritmul Quick Sort in Action";

      	   _quicksort(0, n - 1); //0-based index /(0+9)/2 = 4
      }	  

      void read_data() {

           freopen(FIN, "r", stdin);

           scanf("%d", &n);

           for(int i = 0; i < n; ++i) {

           	  scanf("%d", &vec[i]);
           }

           fclose(stdin);


      }

      void print() {

             freopen(FOUT, "w", stdout);

             for(int i = 0; i < n; ++i) cout<<vec[i]<<" ";

             fclose(stdout); 
      }

      private:
      int n, 
          vec[ MAX ];	


//9 2 3 4 8 7 1 22 18 23
//i                   j

      void _quicksort(int lo, int high) {

           int i, j, 

               PIVOT; 

           i = lo;
           j = high;

           PIVOT = vec[(lo + high) >> 1]; //(lo + high)/2

           while( i <= j) {

                 while(vec[i] < PIVOT) i++;

                 while(vec[j] > PIVOT) j--;


                 //interchimbare (i,j)

                 if(i <= j) {
                 	  int temp = vec[i];
                 	  vec[i] = vec[j];
                 	  vec[j] = temp;

                 	  i++;
                 	  j--;
                 }   
           }    

           if( lo < j ) _quicksort(lo, j);

           if( i < high ) _quicksort(i, high);
      }          

};

//1 2 3 4 8 17 9 22 7 23
//  i      P j   
//0 1 2 3 4 5 6 7 8  9
//PIVOT = 8
// 9 < 8 ?

int main() {
	
	QuickSort q;

    //cout<<"Vectorul initial: ";

    //q.print();

    //cout<<"\n";

	q.solve();

    //cout<<"Vectorul sortat: ";

	q.print();

}