NickAndNick

Сортировка Шелла

Mar 30th, 2013
118
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <ctime>
  3.  
  4. using namespace std;
  5.  
  6. template<typename T> void show(T *, const long);
  7. template<typename T> void shell(T *, const long);
  8. int sedgewick(long *, const long);
  9.  
  10. int main() {    
  11.     const long size = 12L;
  12.     int vector[size];
  13.     srand((unsigned)time(NULL));
  14.     for (long n = 0; n < size; n++) vector[n] = rand();
  15.     show(vector, size);
  16.     cout << endl;
  17.     shell(vector, size);
  18.     show(vector, size);
  19.     cin.get();
  20.     return 0;
  21. }
  22.  
  23. template<typename T> void show(T * _vector, const long _size) {
  24.     for (long n = 0; n < _size; n++) cout << _vector[n] << ' ';
  25.     cout << endl;
  26. }
  27.  
  28. template<typename T> void shell(T * _vector, const long _size) {
  29.     const long lim = 40;
  30.     long sequence[lim], increment, n, m;    
  31.     int size = sedgewick(sequence, _size);
  32.  
  33.     while (size >= 0) {
  34.         increment = sequence[size--];
  35.  
  36.         for (n = increment; n < _size; n++) {
  37.             T temp = _vector[n];
  38.             for (m = n - increment; (m >= 0) && (_vector[m] > temp); m -= increment)
  39.                 _vector[m + increment] = _vector[m];
  40.             _vector[m + increment] = temp;
  41.         }
  42.     }
  43. }
  44.  
  45. int sedgewick(long * _increment, const long _size) {
  46.     unsigned long x1, x2, x3;
  47.     x1 = x2 = x3 = 1;
  48.     int step = -1;
  49.    
  50.     do {
  51.         if (++step & 1) _increment[step] = 8 * x1 - 6 * x2 + 1;
  52.         else {
  53.             _increment[step] = 9 * x1 - 9 * x3 + 1;
  54.             x2 *= 2;
  55.             x3 *= 2;
  56.         }
  57.         x1 *= 2;
  58.     } while (3 * _increment[step] < _size);
  59.     return step > 0 ? --step : 0;
  60. }
RAW Paste Data