pBendan

  1 #include <stdlib.h>
  2 #include <iostream>
  3 #include <vector>
  4 
  5 using namespace std;
  6 
  7 template <class T>
  8 void print_array(const vector<T> &array)
  9 {
 10     for ( unsigned int i = 1; i < array.size() + 1; ++i )
 11     {
 12         cout<<array[i-1]<<" ";
 13         if ( array[i - 1] < 10 )
 14             cout<<" ";
 15         if ( i % 10 == 0 )
 16             cout<<endl;
 17     }
 18 }
 19 
 20 template <class T>
 21 void shuffling(vector<T> &array)
 22 {
 23     int n = array.size();
 24     for ( int i = 0; i < n; ++ i )
 25     {        
 26         int r = i == 0 ? 0 : rand() % i;
 27         T temp = array[i];
 28         array[i] = array[r];
 29         array[r] = temp;
 30     }
 31 
 32     return;
 33 }
 34 
 35 template <class T>
 36 unsigned int partition(vector<T> &array, unsigned int lo, int unsigned hi)
 37 {
 38     if ( lo == hi ) return lo;
 39 
 40     unsigned int i = lo;
 41     unsigned int j = hi;
 42     T partition_val = array[lo];
 43 
 44     while ( i < j )
 45     {
 46         while ( array[i] <= partition_val )
 47         {
 48             if ( i < hi ) ++i;
 49             else break;
 50         }
 51 
 52         while ( array[j] > partition_val )
 53         {
 54             if ( j > lo ) --j;
 55             else break;
 56         }
 57 
 58         if ( i < j )
 59         {
 60             T temp = array[i];
 61             array[i] = array[j];
 62             array[j] = temp;
 63         }
 64 
 65     }
 66 
 67     array[lo] = array[j];
 68     array[j] = partition_val;
 69 
 70     return j;
 71 }
 72 
 73 template <class T>
 74 void quick_sort(vector<T> &array, unsigned int  lo, unsigned int  hi)
 75 {
 76     if ( lo >= hi ) return;
 77     int partition_pos = partition(array, lo, hi);
 78     quick_sort(array, lo, partition_pos);
 79     quick_sort(array, partition_pos + 1, hi);
 80 
 81     return;
 82 }
 83 
 84 int main()
 85 {
 86     vector<int> array;
 87     for ( int i = 0; i < 20; ++i )
 88         array.push_back(i);
 89 
 90     cout<<"shuffling the array..."<<endl;
 91     shuffling(array);
 92 
 93     cout<<"the shuffled array: "<<endl;
 94     print_array(array);
 95 
 96     cout<<"quick sort the array: "<<endl;
 97     quick_sort(array, 0, array.size() - 1);
 98 
 99     cout<<"array after quick sorted: "<<endl;
100     print_array(array);
101 
102     return 0;
103 }