muffinman1015

pokersort quicksort

Dec 5th, 2019
140
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.69 KB | None | 0 0
  1. void swap(VI& a, int from, int to){
  2.     int temp = a[from];
  3.     a[from] = a[to];
  4.     a[to] = temp;
  5. }
  6.  
  7. int median_of_3(VI& a, int lo, int hi){
  8.     int l = a[lo];
  9.     int h = a[hi];
  10.     int mid = (lo + hi)/2;
  11.     int m = a[mid];
  12.     cout << "Taking median of " << l << " " << h << " " << m << endl;
  13.     if (compareTo(l, m) < 0 && compareTo(m, h) < 0){
  14.         return m;
  15.     }
  16.     if (compareTo(h, m) < 0 && compareTo(m, l) < 0){
  17.         return m;
  18.     }
  19.     if (compareTo(m, l) < 0 && compareTo(l, h) < 0){
  20.         return l;
  21.     }
  22.     if (compareTo(h, l) < 0 && compareTo(l, m) < 0){
  23.         return l;
  24.     }
  25.     return h;
  26. }
  27.  
  28. int qs3_Partition(VI& a, int lo, int hi) {
  29.     int x = median_of_3(a, lo, hi); //Coffee choice of partition
  30.     //cout << endl;
  31.     cout << "Choice of partition element is: " << x  << " and lo is: " << lo << " and hi is: " << hi << endl;
  32.     while (lo < hi) {
  33.         while (compareTo(a[lo], x) < 0){
  34.             cout << "Comparing " << a[lo] << " and " << x << " yielding: " << compareTo(a[lo], x) << endl;
  35.             ++lo;
  36.         }
  37.         while (compareTo(a[hi], x) > 0){
  38.             cout << "Comparing " << a[hi] << " and " << x << " yielding: " << compareTo(a[hi], x) << endl;
  39.             --hi;
  40.         }
  41.         if (lo < hi) {
  42.             cout << "Swapping " << a[lo] << " and " << a[hi] << endl;
  43.             swap(a, lo, hi);
  44.             /*int temp = a[lo];
  45.             a[lo++] = a[hi];
  46.             a[hi--] = temp;*/
  47.             if (compareTo(a[lo], a[hi] == 0)){
  48.                 lo++;
  49.             }
  50.             //print(a);
  51.             //cout << endl;
  52.             //cout << "lo is: " << lo << " and hi is: " << hi << endl;
  53.         }
  54.     }
  55.     //print(a);
  56.     //cout << endl;
  57.     return lo;
  58. }
  59.  
  60. int THRESHOLD = 4;
  61. void qs4 (VI& a, int lo, int hi) {
  62.     while (hi - lo > THRESHOLD) { //THRESHOLD from 30 years ago was 20, experiment!
  63.         while (lo < hi) {
  64.             int m = qs3_Partition(a, lo, hi);
  65.             if (m - lo < hi - m + 1) {
  66.                 qs4(a, lo, m - 1);
  67.                 lo = m;
  68.             } else {
  69.                 qs4(a , m , hi);
  70.                 hi = m - 1;
  71.             }
  72.         }
  73.     }
  74. }
  75.  
  76. void insertion_sort_int(vector<int>& a){
  77.     for(int j = 1; j < a.size(); ++j){
  78.         int t = a[j];
  79.         //cout << j << ": t = " << t << std::endl;
  80.         for (int i = j; i > 0 && compareTo(a[i-1], t) >= 0; --i){
  81.             //cout << a[i-1] << " >= " << t << std::endl;
  82.             a[i] = a[i - 1];
  83.             a[i - 1] = t;
  84.             //print(a, n);
  85.             //cout << std::endl;
  86.         }
  87.     }
  88. }
  89.  
  90. void quick_sortCh (VI& a, int n) {
  91.     qs4(a, 0, n-1);
  92.     //print(a);
  93.     //insertion_sort_int(a);
  94. }
Add Comment
Please, Sign In to add comment