home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / gnu / g / bug / 2146 < prev    next >
Encoding:
Text File  |  1993-01-06  |  8.7 KB  |  372 lines
  1. Newsgroups: gnu.g++.bug
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!cs.utexas.edu!bwest
  3. From: bwest@cs.utexas.edu (Brian Neal West)
  4. Subject: you ask for it ...
  5. Message-ID: <9301052009.AA06932@peaches.cs.utexas.edu>
  6. Sender: gnulists@ai.mit.edu
  7. Organization: GNUs Not Usenet
  8. Distribution: gnu
  9. Date: Tue, 5 Jan 1993 08:09:51 GMT
  10. Approved: bug-g++@prep.ai.mit.edu
  11. Lines: 359
  12.  
  13. #include <stdio.h>
  14. #include <math.h>
  15.  
  16. //#include "CACMrandom.h"
  17. float CACMrandom(void);
  18.  
  19. enum boolean {FALSE, TRUE};
  20.  
  21. class ARRAY {
  22.   private:
  23.     int *array;
  24.     int size;
  25.  
  26.   public: //protected:
  27.     void Randomize(void);
  28.     boolean Ordered(void);
  29.     void Dump(void);
  30.  
  31.     void StraightInsertionSort(void);
  32.     void StraightBinaryInsertionSort(void);
  33.     void StraightSelectionSort(void);
  34.     void BubbleSort(void);
  35.     void ShakerSort(void);
  36.     void ShellSort(void);
  37.     void HeapSort(void); void Heapify(int i, int j);
  38.     void QuickSort(void); void QSort(int left, int right);
  39.     void MergeSort(void); void Msort(int i, int j); void Merge(int i, int m, int j);
  40.     void MergeExchangeSort(void);
  41.  
  42.     typedef void (ARRAY::* sortSig)(void) ;
  43.     ARRAY(sortSig mySort, int size=128) {array = new int[size]; sort = mySort; };
  44.     void SelectSort(void) {
  45.         if      (0  <= size && size <= 50  ) sort = &ARRAY::StraightInsertionSort; 
  46.         else if (51 <= size && size <= 5000) sort = &ARRAY::ShellSort; 
  47.         else                                 sort = &ARRAY::QuickSort; 
  48.     };
  49.     void CheckAllSorts(void);
  50.  
  51.   public:
  52.     sortSig sort;
  53.  
  54.     ARRAY(int size=128) {
  55.         ARRAY::size = size;
  56.         array = new int[size];
  57.         SelectSort();
  58.     };
  59. };
  60.  
  61.  
  62. void
  63. ARRAY::Randomize(void) {
  64.     int i;
  65.     for (i=0; i<size; i++)
  66.         array[i] = i;
  67.     for (i=0; i<size; i++) {
  68.         long x = long(CACMrandom() * float(size));
  69.         long y = long(CACMrandom() * float(size));
  70.         int temp = array[x];
  71.         array[x] = array[y];
  72.         array[y] = temp;
  73.     }
  74. }
  75.  
  76. boolean
  77. ARRAY::Ordered(void) {
  78.     int i;
  79.     for (i=0; i<size; i++) 
  80.         if (array[i] != i) return FALSE;
  81.     return TRUE;
  82. }
  83.  
  84. void
  85. ARRAY::Dump(void) {
  86.     int i;
  87.     for (i=0; i<size; i++) {
  88.         printf("array[%2d] is %2d. \n", i, array[i]);
  89.     } 
  90. }
  91.  
  92. void 
  93. ARRAY::CheckAllSorts(void) {
  94.     static sortSig AllSorts[] = {
  95.         &ARRAY::StraightInsertionSort,
  96.         &ARRAY::StraightBinaryInsertionSort
  97.     };
  98.     int i;
  99.  
  100.     for (i=0; i<2; i++) {
  101.         Randomize();
  102.         AllSorts[i]();
  103.     }
  104. }
  105.  
  106. // .25N**2 comparisons and .25N**2moves
  107. void
  108. ARRAY::StraightInsertionSort(void) {
  109.     int i, j, temp, insert;
  110.     for (i=1; i<size; i++) {
  111.         temp = array[i];
  112.         insert = i;
  113.         for (j=i-1; j>=0 && temp < array[j]; j--) {
  114.             array[j+1] = array[j];
  115.             insert--;
  116.         }
  117.         array[insert] = temp;
  118.     }
  119. }
  120.  
  121. // N*log2(N) comparisons and .25n**2moves
  122. void 
  123. ARRAY::StraightBinaryInsertionSort(void) {
  124.     int i, j, temp, l, r, m;
  125.     for (i=1; i<size; i++) {
  126.         temp = array[i];
  127.         l = 0;
  128.         r = i-1;
  129.         while (l <= r) {
  130.             m = (l + r)/2;
  131.             if (temp < array[m]) r = m - 1;
  132.             else                 l = m + 1;
  133.         }
  134.         for (j=i-1; j>=l; j--)
  135.             array[j+1] = array[j];
  136.         array[l] = temp;
  137.     }
  138. }
  139.  
  140. void 
  141. ARRAY::StraightSelectionSort(void) {
  142.     int i, j, k;
  143.     for (i=0; i<size-1; i++) {
  144.         k = i;
  145.         for (j=i+1; j<size; j++) {
  146.             if (array[j] < array[k])
  147.                 k = j;
  148.         }
  149.         if (k != i) {
  150.             int temp = array[k];
  151.             array[k] = array[i];
  152.             array[i] = temp;
  153.         }
  154.     }   
  155. }
  156.  
  157. void 
  158. ARRAY::BubbleSort(void) {
  159.     int i, j;
  160.     for (i=1; i<size-1; i++)
  161.         for (j=size-1; j>=i; j--)
  162.             if (array[j-1] > array[j]) {
  163.                 int temp = array[j-1];
  164.                 array[j-1] = array[j];
  165.                 array[j] = temp;
  166.             }
  167. }
  168.  
  169. void 
  170. ARRAY::ShakerSort(void) {
  171.     int j, k, l, r;
  172.     l = 1;
  173.     r = k = size - 1;
  174.     do {
  175.         for (j=r; j>=l; j--) {
  176.             if (array[j-1] > array[j]) {
  177.                 int temp = array[j-1];
  178.                 array[j-1] = array[j];
  179.                 array[j] = temp;
  180.                 k = j;
  181.             }
  182.         }
  183.         l = k + 1;
  184.         for (j=l; j<=r; j++) {
  185.             if (array[j-1] > array[j]) {
  186.                 int temp = array[j-1];
  187.                 array[j-1] = array[j];
  188.                 array[j] = temp;
  189.                 k = j;
  190.             }
  191.         }
  192.         r = k - 1;
  193.     } while (l<=r);
  194. }
  195.  
  196. // N**1.3 or ~ N(log2(N))**2
  197. void 
  198. ARRAY::ShellSort(void) {  // insertion sort by diminishing intervals
  199.     int i, j, k, interval, temp, insert, intervalNum;
  200.     for (intervalNum=int(log(double(size))/log(2.0)); intervalNum>=1; intervalNum--) {
  201.         interval = int(pow(2.0, double(intervalNum))) - 1;
  202.         for (i=0; i<=interval-1; i++) {
  203.             for (j=i+interval; j<=size-1; j+=interval) {
  204.                 temp = array[j];
  205.                 insert = j;
  206.                 for (k=j-interval; k>=0 && array[k] > temp; k-=interval) {
  207.                     array[k+interval] = array[k];
  208.                     insert = k;
  209.                 }
  210.                 array[insert] = temp;
  211.             }
  212.         }
  213.     }
  214. }
  215.  
  216. // N*log2(N) : average and worst case
  217. void 
  218. ARRAY::Heapify(int i, int j) { // heap => array[root] > array[either son]
  219.     int leftSon, rightSon, k;
  220.     leftSon = i*2 + 1;
  221.     rightSon = i*2 +2;
  222.     if (leftSon <= j) {
  223.         if (rightSon <= j) {
  224.             if (array[leftSon] > array[rightSon]) k = leftSon;
  225.             else                                  k = rightSon;
  226.         } else                                    k = leftSon;
  227.         if (array[k] > array[i]) {
  228.             int temp = array[i];
  229.             array[i] = array[k];
  230.             array[k] = temp;
  231.             Heapify(k, j);
  232.         }
  233.     }
  234. }
  235.  
  236. void 
  237. ARRAY::HeapSort(void) {
  238.     int i;
  239.     for (i=size-1; i>=0; i--) 
  240.         Heapify(i, size-1);
  241.     for (i=size-1; i>=1; i--) {
  242.         int temp = array[0];
  243.         array[0] = array[i];
  244.         array[i] = temp;
  245.         Heapify(0, i-1);
  246.     }
  247. }
  248.  
  249. // N*log2(N) : average ; N**2 : worst case (already ordered)
  250. void 
  251. ARRAY::QSort(int left, int right) {
  252.     int i, j, x;
  253.     i = left;
  254.     j = right;
  255.     x = array[ (left+right)/2 ];
  256.     do {
  257.         while (array[i] < x) i++;
  258.         while (x < array[j]) j--;
  259.         if (i <= j) {
  260.             int temp = array[i];
  261.             array[i] = array[j];
  262.             array[j] = temp;
  263.             i++;
  264.             j--;
  265.         }
  266.     } while (i <= j);
  267.     if (left < j) 
  268.         QSort(left, j);
  269.     if (i < right) 
  270.         QSort(i, right);
  271. }
  272.  
  273. void 
  274. ARRAY::QuickSort(void) {
  275.     QSort(0, size-1);
  276. }
  277.  
  278. // needs an axillary array of size N 
  279. // N*log2(N) : average and worst case
  280. int *AUXarray;
  281.  
  282. void 
  283. ARRAY::Merge(int i, int m, int j) {
  284.     int k, index1, index2, n;
  285.     k = i;
  286.     index1 = i;
  287.     index2 = m + 1;
  288.     while ((index1 <= m) && (index2 <= j)) {
  289.         if (array[index1] < array[index2])
  290.             AUXarray[k++] = array[index1++];
  291.         else 
  292.             AUXarray[k++] = array[index2++];
  293.     }
  294.     if (index1 <= m)
  295.         while (index1 <= m)
  296.             AUXarray[k++] = array[index1++];
  297.     else if (index2 <= j)
  298.         while (index2 <= j)
  299.             AUXarray[k++] = array[index2++];
  300.  
  301.     for (k=i; k<=j; k++)
  302.         array[k] = AUXarray[k];
  303. }
  304.  
  305. void 
  306. ARRAY::Msort(int i, int j) {
  307.     int m;
  308.     if (i != j) {
  309.         m = (i + j)/2;
  310.         Msort(i, m);
  311.         Msort(m+1, j);
  312.         Merge(i, m, j);
  313.     }
  314. } 
  315.  
  316. void 
  317. ARRAY::MergeSort(void) {
  318.     AUXarray = new int[size];
  319.     Msort(0, size-1);
  320. }
  321.  
  322.     
  323. void 
  324. ARRAY::MergeExchangeSort() { // Batcher's parallel sort
  325.     int t, t0, p, q, r, d, i ;
  326.  
  327.     for (t = t0 = int(ceil(log(double(size))/log(2.0))); t>0; t--) {
  328.         p=int(pow(2.0, double(t-1)));
  329.         q = int(pow(2.0, double(t0-1)));
  330.         r = 0;
  331.         d = p;
  332.         while (1) {
  333.             for (i=0; i < size - d; i++) { 
  334.                 if ((i & p) == r) { // each selected i can "campare and exchange" in parallel
  335.                     if (array[i] > array[i+d]) {
  336.                         int temp = array[i];
  337.                         array[i] = array[i+d];
  338.                         array[i+d] = temp;
  339.                     } 
  340.                 }
  341.             }
  342.             if (p == q) break;
  343.             d = q - p;
  344.             q = q / 2;
  345.             r = p;
  346.         }
  347.     }
  348. }
  349.  
  350.  
  351. int
  352. main()
  353. {
  354.     ARRAY ARRAYobject(16);
  355.     ARRAYobject.Randomize();
  356.     ARRAYobject.Dump();
  357.     ARRAYobject.MergeExchangeSort();
  358.     if (ARRAYobject.Ordered())
  359.         printf("Array is ordered.\n");
  360.     else {
  361.         printf("Array is not ordered.\n");
  362.         ARRAYobject.Dump();
  363.     }
  364. }
  365.  
  366. -- 
  367. bwest@cs.utexas.edu
  368. ============================================================================
  369. STANDARD DISCLAIMER: No one is responsible. 
  370. My Astral-Projection did this, if you get my drift.
  371.  
  372.