muffinman1015

all_pokersort

Dec 5th, 2019
211
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 23.53 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. #include <utility>
  5. #include <chrono>
  6.  
  7. using namespace std;
  8. using namespace std::chrono;
  9.  
  10. using std::cout;
  11. using std::cin;
  12. using std::endl;
  13. using std::vector;
  14.  
  15. typedef vector<int> VI;
  16. typedef vector<VI> VVI;
  17.  
  18. void print(VI& a){
  19.     for (int i : a){
  20.         cout << i << " ";
  21.     }
  22. }
  23.  
  24. void print(VVI& a){
  25.     for(VI x: a){
  26.         print(x);
  27.     }
  28. }
  29.  
  30. const int CLUBS = 0;
  31. const int DIAMONDS = 1;
  32. const int HEARTS = 2;
  33. const int SPADES = 3;
  34. const int TWO = 0;
  35. const int THREE = 1;
  36. const int FOUR = 2;
  37. const int FIVE = 3;
  38. const int SIX = 4;
  39. const int SEVEN = 5;
  40. const int EIGHT = 6;
  41. const int NINE = 7;
  42. const int TEN = 8;
  43. const int JACK = 9;
  44. const int QUEEN = 10;
  45. const int KING = 11;
  46. const int ACE = 12;
  47. const int HIGH_CARD = 0;
  48. const int PAIR = 1;
  49. const int TWO_PAIR = 2;
  50. const int THREE_KIND = 3;
  51. const int STRAIGHT = 4;
  52. const int FLUSH = 5;
  53. const int FULL_HOUSE = 6;
  54. const int FOUR_KIND = 7;
  55. const int STRAIGHT_FLUSH = 8;
  56.  
  57. void insertion_sort_hand(VVI& a){
  58.     for(int j = 1; j < a.size(); ++j){
  59.         VI t = a[j];
  60.         //cout << j << ": t = " << t[0] << ", " << t[1] << std::endl;
  61.         for (int i = j; i > 0 && a[i-1][0] > t[0]; --i){
  62.             //cout << a[i-1][0] << " > " << t[0] << std::endl;
  63.             a[i] = a[i - 1];
  64.             a[i - 1] = t;
  65.             //print(a);
  66.             //cout << std::endl;
  67.         }
  68.     }
  69. }
  70.  
  71. VI int_to_card(int card){
  72.     int suit = card % 4;
  73.     int rank = (card-suit) / 4;
  74.     VI C0 = {rank, suit};
  75.     return C0;
  76. }
  77.  
  78. int card_to_int(VI& card){
  79.     return 4*card[0] + card[1];
  80. }
  81.  
  82. void print_card_names(VI& card){
  83.     switch(card[0]){
  84.         case 0:
  85.             cout << "TWO of ";
  86.             break;
  87.         case 1:
  88.             cout << "THREE of ";
  89.             break;
  90.         case 2:
  91.             cout << "FOUR of ";
  92.             break;
  93.         case 3:
  94.             cout << "FIVE of ";
  95.             break;
  96.         case 4:
  97.             cout << "SIX of ";
  98.             break;
  99.         case 5:
  100.             cout << "SEVEN of ";
  101.             break;
  102.         case 6:
  103.             cout << "EIGHT of ";
  104.             break;
  105.         case 7:
  106.             cout << "NINE of ";
  107.             break;
  108.         case 8:
  109.             cout << "TEN of ";
  110.             break;
  111.         case 9:
  112.             cout << "JACK of ";
  113.             break;
  114.         case 10:
  115.             cout << "QUEEN of ";
  116.             break;
  117.         case 11:
  118.             cout << "KING of ";
  119.             break;
  120.         case 12:
  121.             cout << "ACE of ";
  122.             break;
  123.         default:
  124.             cout << "INVALID RANK!";
  125.             break;
  126.     }
  127.     switch(card[1]) {
  128.         case 0:
  129.             cout << "CLUBS ";
  130.             break;
  131.         case 1:
  132.             cout << "DIAMONDS ";
  133.             break;
  134.         case 2:
  135.             cout << "HEARTS ";
  136.             break;
  137.         case 3:
  138.             cout << "SPADES ";
  139.             break;
  140.         default:
  141.             cout << "INVALID SUIT";
  142.             break;
  143.     }
  144. }
  145.  
  146. void print_card_values(VI& card){
  147.     cout << "{" << card[0] << ", " << card[1] << "} ";
  148. }
  149.  
  150. void print_hand_names(VVI& hand){
  151.     for (auto i : hand){
  152.         print_card_names(i);
  153.     }
  154.     cout << endl;
  155. }
  156.  
  157. void print_hand_values (VVI& hand){
  158.     for (auto i : hand){
  159.         print_card_values(i);
  160.     }
  161.     cout << endl;
  162. }
  163.  
  164. VVI convert_to_hand(int n){
  165.     VVI hand;
  166.     int C0 = n % 52;
  167.     //cout << "c0 int: " << C0 << " => ";
  168.     VI c0 = int_to_card(C0);
  169.     //print_card(c0);
  170.     //cout << endl;
  171.     hand.push_back(c0);
  172.  
  173.     int C1 =  n/52 % 52;
  174.     //cout << "c1 int: " << C1 << " => ";
  175.     VI c1 = int_to_card(C1);
  176.     //print_card( c1);
  177.     //cout << endl;
  178.     hand.push_back(c1);
  179.  
  180.     int C2 =  (n/(52*52)) % 52;
  181.     //cout << "c2 int: " << C2 << " => ";
  182.     VI c2 = int_to_card(C2);
  183.     //print_card( c2);
  184.     //cout << endl;
  185.     hand.push_back(c2);
  186.  
  187.     int C3 =  (n/(52*52*52)) % 52;
  188.     //cout << "c3 int: " << C3 << " => ";
  189.     VI c3 = int_to_card(C3);
  190.     //print_card( c3);
  191.     //cout << endl;
  192.     hand.push_back(c3);
  193.  
  194.     int C4 =  (n/(52*52*52*52)) % 52;
  195.     //cout << "c4 int: " << C4 << " => ";
  196.     VI c4 = int_to_card(C4);
  197.     //print_card( c4);
  198.     //cout << endl;
  199.     hand.push_back(c4);
  200.     return hand;
  201. }
  202.  
  203. void test_cards(){
  204.     for (int i = 0; i < 52; i++) {
  205.         VI card = int_to_card(i);
  206.         cout << i << " : ";
  207.         print_card_names(card);
  208.         cout << endl;
  209.     }
  210. }
  211.  
  212. bool is_four(VVI& hand){
  213.     if (hand[0][0] == hand[1][0] && hand[1][0] == hand[2][0] && hand[2][0] == hand[3][0]){
  214.         return true;
  215.     }
  216.     return hand[1][0] == hand[2][0] && hand[2][0] == hand[3][0] && hand[3][0] == hand[4][0];
  217. }
  218.  
  219. bool is_flush(VVI& hand){
  220.     int suit = hand[0][1];
  221.     for (auto i: hand){
  222.         if(i[1] != suit){
  223.             return false;
  224.         }
  225.     }
  226.     return true;
  227. }
  228.  
  229. bool is_straight(VVI& hand) { //use second to last value later when valuing
  230.     if (hand[0][0] == TWO && hand[1][0] == THREE && hand[2][0] == FOUR && hand[3][0] == FIVE && hand[4][0] == ACE){
  231.         return true;
  232.     }
  233.     for (int i = 1; i < hand.size(); i++){
  234.         /*print_card_names(hand[i]);
  235.         cout << " ";
  236.         print_card_names(hand[i-1]);
  237.         cout << endl;
  238.         cout << hand[i][0] << " " << hand[i-1][0] << endl;*/
  239.         if (hand[i][0] - hand[i-1][0] != 1){
  240.             return false;
  241.         }
  242.     }
  243.     return true;
  244. }
  245.  
  246. bool is_straightflush(VVI& hand){
  247.     return is_straight(hand) && is_flush(hand);
  248. }
  249.  
  250. bool is_full_house(VVI& hand){ //use middle element later when valuing
  251.     if(!is_four(hand)) {
  252.         if (hand[0][0] == hand[1][0] && hand[2][0] == hand[3][0] && hand[3][0] == hand[4][0]){
  253.             return true;
  254.         }
  255.         if (hand[0][0] == hand[1][0] && hand[1][0] == hand[2][0] && hand[3][0] == hand[4][0]){
  256.             return true;
  257.         }
  258.     }
  259.     return false;
  260. }
  261.  
  262. bool is_triple(VVI& hand){
  263.     if(!is_full_house(hand) && !is_four(hand)){
  264.         if (hand[0][0] == hand[1][0] && hand[1][0] == hand[2][0]){
  265.             return true;
  266.         }
  267.         if (hand[1][0] == hand[2][0] && hand[2][0] == hand[3][0]){
  268.             return true;
  269.         }
  270.         if (hand[2][0] == hand[3][0] && hand[3][0] == hand[4][0]){
  271.             return true;
  272.         }
  273.     }
  274.     return false;
  275. }
  276.  
  277. bool is_two_pair(VVI& hand){
  278.     if (!is_triple(hand) && !is_four(hand)){
  279.         if (hand[0][0] == hand[1][0] && hand[2][0] == hand[3][0]){
  280.             return true;
  281.         }
  282.         if (hand[0][0] == hand[1][0] && hand[3][0] == hand[4][0]){
  283.             return true;
  284.         }
  285.         if (hand[1][0] == hand[2][0] && hand[3][0] == hand[4][0]){
  286.             return true;
  287.         }
  288.     }
  289.     return false;
  290. }
  291.  
  292. bool is_pair(VVI& hand){
  293.     if (!is_two_pair(hand) && !is_triple(hand) && !is_four(hand) && !is_full_house(hand)) {
  294.         if (hand[0][0] == hand[1][0]) {
  295.             return true;
  296.         }
  297.         if (hand[1][0] == hand[2][0]) {
  298.             return true;
  299.         }
  300.         if (hand[2][0] == hand[3][0]) {
  301.             return true;
  302.         }
  303.         if (hand[3][0] == hand[4][0]) {
  304.             return true;
  305.         }
  306.     }
  307.     return false;
  308. }
  309.  
  310. bool is_high_card(VVI& hand){
  311.     return !is_pair(hand) && !is_two_pair(hand) && !is_triple(hand) && !is_straight(hand) && !is_full_house(hand) &&
  312.            !is_flush(hand) && !is_four(hand);
  313. }
  314.  
  315. vector<bool> repetition_array(VVI& hand){
  316.     vector<bool> repeated(hand.size());
  317.     for (int i = 0; i < hand.size(); i++) {
  318.         //cout << "Currently on position " << i << endl;
  319.         for (int j = 0; j < hand.size(); j++) {
  320.             if (j == i){
  321.                 continue;
  322.             }
  323.             if (hand[j][0] == hand[i][0]) {
  324.                 repeated[i] = true;
  325.             }
  326.         }
  327.     }
  328.     //for (int i = 0; i < repeated.size(); i++) {
  329.        // cout << repeated[i] << " ";
  330.     //}
  331.     //cout << endl;
  332.     return repeated;
  333. }
  334. VVI get_unique_cards(VVI& hand){
  335.     VVI unique_elts;
  336.     vector<bool> repeated = repetition_array(hand);
  337.     for (int i = 0; i < repeated.size(); i++){
  338.         if (!repeated[i]){
  339.             unique_elts.push_back(hand[i]);
  340.         }
  341.     }
  342.     //print_hand_names(unique_elts);
  343.     return unique_elts;
  344. }
  345.  
  346. VVI get_repeated_cards(VVI& hand){
  347.     VVI repeated_elts;
  348.     vector<bool> repeated = repetition_array(hand);
  349.     for (int i = 0; i < repeated.size(); i++){
  350.         if (repeated[i]){
  351.             repeated_elts.push_back(hand[i]);
  352.         }
  353.     }
  354.     //print_hand_names(repeated_elts);
  355.     return repeated_elts;
  356. }
  357. VI get_high_unique_card(VVI& hand){
  358.     bool repeated[hand.size()-1];
  359.     insertion_sort_hand(hand);
  360.     //print_hand_names(hand);
  361.     VI highest_unique = hand[0];
  362.     //cout << "Initial: ";
  363.     //print_card_names(highest_unique);
  364.     //cout << endl;
  365.     for (auto i: get_unique_cards(hand)){
  366.         if (i[0] > highest_unique[0]){
  367.             highest_unique = i;
  368.         }
  369.     }
  370.     //cout << "Results: ";
  371.     //print_card_names(highest_unique);
  372.     //cout << endl;
  373.     return highest_unique;
  374. }
  375.  
  376. VI get_high_card(VVI& hand){
  377.     insertion_sort_hand(hand);
  378.     return hand[hand.size()-1];
  379. }
  380.  
  381. int get_high_unique_rank(VVI& hand){
  382.     return get_high_unique_card(hand)[0];
  383. }
  384.  
  385. int get_high_rank(VVI& hand){
  386.     return get_high_card(hand)[0];
  387. }
  388.  
  389. int classify(VVI& hand){
  390.     insertion_sort_hand(hand);
  391.     if(is_straightflush(hand)){
  392.         //cout << "STRAIGHT_FLUSH "; //<< endl;
  393.         return STRAIGHT_FLUSH;
  394.     }
  395.     if(is_four(hand)){
  396.         //cout << "FOUR_KIND "; // << endl;
  397.         return FOUR_KIND;
  398.     }
  399.     if(is_full_house(hand)){
  400.         //cout << "FULL_HOUSE "; // << endl;
  401.         return FULL_HOUSE;
  402.     }
  403.     if(is_flush(hand)){
  404.         //cout << "FLUSH "; // << endl;
  405.         return FLUSH;
  406.     }
  407.     if(is_straight(hand)){
  408.         //cout << "STRAIGHT "; // << endl;
  409.         return STRAIGHT;
  410.     }
  411.     if(is_triple(hand)){
  412.         //cout << "THREE_KIND "; // << endl;
  413.         return THREE_KIND;
  414.     }
  415.     if(is_two_pair(hand)){
  416.        // cout << "TWO_PAIR "; // << endl;
  417.         return TWO_PAIR;
  418.     }
  419.     if(is_pair(hand)){
  420.         //cout << "PAIR "; // << endl;
  421.         return PAIR;
  422.     }
  423.     if(is_high_card(hand)){
  424.         //cout << "HIGH_CARD "; // << endl;
  425.         return HIGH_CARD;
  426.     }
  427.     cout << "ERROR"; // << endl;
  428.     return -1;
  429. }
  430.  
  431. int eval(VVI& hand1, VVI& hand2){
  432.     int eval = classify(hand1) - classify(hand2);
  433.     //cout << endl;
  434.     if (eval == 0) {
  435.         //cout << "Same rank of hand. Proceeding to secondary classification." << endl;
  436.         if (is_high_card(hand1)){
  437.             //cout << "IS HIGH_CARD!" << endl;
  438.             VVI hand1Copy = hand1;
  439.             VVI hand2Copy = hand2;
  440.             while (get_high_unique_rank(hand1Copy) == get_high_unique_rank(hand2Copy)){
  441.                 hand1Copy.erase(hand1Copy.begin()+hand1Copy.size());
  442.                 hand2Copy.erase(hand2Copy.begin()+hand2Copy.size());
  443.             }
  444.             return get_high_unique_rank(hand1Copy) - get_high_unique_rank(hand2Copy);
  445.         }
  446.         if (is_pair(hand1)){
  447.             //cout << "IS PAIR!" << endl;
  448.             VVI repeated_elts_1 = get_repeated_cards(hand1);
  449.             VVI repeated_elts_2 = get_repeated_cards(hand2);
  450.             VVI unique_elts_1 = get_unique_cards(hand1);
  451.             VVI unique_elts_2 = get_unique_cards(hand2);
  452.             if (get_high_rank(repeated_elts_1) == get_high_rank(repeated_elts_2)){
  453.                 return get_high_unique_rank(unique_elts_1) - get_high_unique_rank(unique_elts_2);
  454.             }
  455.             return get_high_unique_rank(repeated_elts_1) - get_high_unique_rank(repeated_elts_2);
  456.         }
  457.         if (is_two_pair(hand1)){
  458.             //cout << "IS TWO_PAIR!" << endl;
  459.             VVI repeated_elts_1 = get_repeated_cards(hand1);
  460.             VVI repeated_elts_2 = get_repeated_cards(hand2);
  461.             VVI unique_elts_1 = get_unique_cards(hand1);
  462.             VVI unique_elts_2 = get_unique_cards(hand2);
  463.             if (get_high_rank(repeated_elts_1) == get_high_rank(repeated_elts_2)){
  464.                 if (repeated_elts_1[0][0] == repeated_elts_2[0][0]) {
  465.                     return get_high_unique_rank(unique_elts_1) - get_high_unique_rank(unique_elts_2);
  466.                 } else {
  467.                     return repeated_elts_1[0][0] - repeated_elts_2[0][0];
  468.                 }
  469.             }
  470.             return get_high_rank(repeated_elts_1) - get_high_rank(repeated_elts_2);
  471.         }
  472.         if (is_triple(hand1)){
  473.             //cout << "IS THREE_KIND!" << endl;
  474.             VVI repeated_elts_1 = get_repeated_cards(hand1);
  475.             VVI repeated_elts_2 = get_repeated_cards(hand2);
  476.             VVI unique_elts_1 = get_unique_cards(hand1);
  477.             VVI unique_elts_2 = get_unique_cards(hand2);
  478.             if (get_high_rank(repeated_elts_1) == get_high_rank(repeated_elts_2)){
  479.                 return get_high_unique_rank(unique_elts_1) - get_high_unique_rank(unique_elts_2);
  480.             }
  481.             return get_high_rank(repeated_elts_1) - get_high_rank(repeated_elts_2);
  482.         }
  483.         if(is_straight(hand1)){
  484.             //cout << "IS STRAIGHT!" << endl;
  485.             return get_high_unique_rank(hand1) - get_high_unique_rank(hand2);
  486.         }
  487.         if (is_flush(hand1)){
  488.             //cout << "IS FLUSH!" << endl;
  489.             VVI hand1Copy = hand1;
  490.             VVI hand2Copy = hand2;
  491.             while (get_high_unique_rank(hand1Copy) == get_high_unique_rank(hand2Copy)){
  492.                 hand1Copy.erase(hand1Copy.begin()+hand1Copy.size());
  493.                 hand2Copy.erase(hand2Copy.begin()+hand2Copy.size());
  494.             }
  495.             return get_high_unique_rank(hand1Copy) - get_high_unique_rank(hand2Copy);
  496.         }
  497.         if (is_full_house(hand1)){
  498.             //cout << "IS FULL HOUSE!" << endl;
  499.             VVI hand1Copy = hand1;
  500.             VVI hand2Copy = hand2;
  501.             int rank_triple = get_high_rank(hand1Copy);
  502.             if (get_high_rank(hand2Copy) == rank_triple){
  503.                 for (int i = 0; i < 5; i++){
  504.                     if (hand1Copy[i][0] == rank_triple){
  505.                         hand1Copy.erase(hand1Copy.begin()+i);
  506.                     }
  507.                     if(hand2Copy[i][0] == rank_triple){
  508.                         hand2Copy.erase(hand2Copy.begin()+i);
  509.                     }
  510.                 }
  511.                 return hand1Copy[0][0] - hand2Copy[0][0];
  512.             }
  513.             return rank_triple - get_high_rank(hand2Copy);
  514.         }
  515.         if (is_four(hand1)){
  516.             //cout << "IS_FOUR!" << endl;
  517.             VVI repeated_elts_1 = get_repeated_cards(hand1);
  518.             VVI repeated_elts_2 = get_repeated_cards(hand2);
  519.             VVI unique_elts_1 = get_unique_cards(hand1);
  520.             VVI unique_elts_2 = get_unique_cards(hand2);
  521.             if (get_high_rank(repeated_elts_1) == get_high_rank(repeated_elts_2)){
  522.                 //cout << "Rank of FOUR_KINDs are equal." << endl;
  523.                 return get_high_unique_rank(unique_elts_1) - get_high_unique_rank(unique_elts_2);
  524.             }
  525.             //cout << "Rank of FOUR_KINDs are different." << endl;
  526.             return get_high_rank(repeated_elts_1) - get_high_rank(repeated_elts_2);
  527.         }
  528.         if (is_straightflush(hand1)) {
  529.             //cout << "IS STRAIGHT FLUSH!" << endl;
  530.             return get_high_unique_rank(hand1) - get_high_unique_rank(hand2);
  531.         }
  532.     }
  533.     return eval;
  534. }
  535.  
  536. int compareTo(int a, int b){
  537.     VVI handA = convert_to_hand(a);
  538.     VVI handB = convert_to_hand(b);
  539.     return eval(handA, handB);
  540. }
  541.  
  542. void test_insertion(int h){
  543.     VVI hand = convert_to_hand(h);
  544.     insertion_sort_hand(hand);
  545.     print_hand_names(hand);
  546. }
  547.  
  548. void test_identify(int a) {
  549.     VVI hand = convert_to_hand(a);
  550.     cout << "HIGH_CARD: " << is_high_card(hand) << " PAIR: " << is_pair(hand) << " TWO_PAIR: " << is_two_pair(hand) <<
  551.     " THREE_KIND: " << is_triple(hand) << " FULL_HOUSE: " << is_full_house(hand) << " FOUR_KIND: " << is_four(hand) << endl;
  552. }
  553. void test_eval(int a, int b){
  554.     VVI handa = convert_to_hand(a);
  555.     VVI handb = convert_to_hand(b);
  556.     print_hand_values(handa);
  557.     print_hand_values(handb);
  558.     print_hand_names(handa);
  559.     print_hand_names(handb);
  560.     cout << eval(handa, handb);
  561. }
  562.  
  563. bool isSorted_poker(VI& a){
  564.     for (int i = 1; i < a.size(); i++){
  565.         if (compareTo(a[i], a[i - 1]) < 0) return false;
  566.     }
  567.     return true;
  568. }
  569.  
  570. bool isSorted_int(VI& a){
  571.     for (int i = 1; i < a.size(); i++){
  572.         if (a[i] < a[i - 1]) return false;
  573.     }
  574.     return true;
  575. }
  576.  
  577.  
  578. void swap(VI& a, int from, int to){
  579.     int temp = a[from];
  580.     a[from] = a[to];
  581.     a[to] = temp;
  582. }
  583.  
  584. int median_of_3_poker(VI& a, int lo, int hi){
  585.     int l = a[lo];
  586.     int h = a[hi];
  587.     int mid = (lo + hi)/2;
  588.     int m = a[mid];
  589.     cout << "Taking median of " << l << " " << h << " " << m << endl;
  590.     if (compareTo(l, m) < 0 && compareTo(m, h) < 0){
  591.         return m;
  592.     }
  593.     if (compareTo(h, m) < 0 && compareTo(m, l) < 0){
  594.         return m;
  595.     }
  596.     if (compareTo(m, l) < 0 && compareTo(l, h) < 0){
  597.         return l;
  598.     }
  599.     if (compareTo(h, l) < 0 && compareTo(l, m) < 0){
  600.         return l;
  601.     }
  602.     return h;
  603. }
  604.  
  605. int qs3_Partition_poker(VI& a, int lo, int hi) {
  606.     int x = median_of_3_poker(a, lo, hi); //Coffee choice of partition
  607.     //cout << endl;
  608.     cout << "Choice of partition element is: " << x  << " and lo is: " << lo << " and hi is: " << hi << endl;
  609.     while (lo < hi) {
  610.         while (compareTo(a[lo], x) < 0){
  611.             cout << "Comparing " << a[lo] << " and " << x << " yielding: " << compareTo(a[lo], x) << endl;
  612.             ++lo;
  613.         }
  614.         while (compareTo(a[hi], x) > 0){
  615.             cout << "Comparing " << a[hi] << " and " << x << " yielding: " << compareTo(a[hi], x) << endl;
  616.             --hi;
  617.         }
  618.         if (lo < hi) {
  619.             cout << "Swapping " << a[lo] << " and " << a[hi] << endl;
  620.             swap(a, lo, hi);
  621.             if (compareTo(a[lo], a[hi] == 0)){
  622.                 lo++;
  623.             }
  624.             print(a);
  625.             cout << endl;
  626.             cout << "lo is: " << lo << " and hi is: " << hi << endl;
  627.         }
  628.     }
  629.     //print(a);
  630.     //cout << endl;
  631.     return lo;
  632. }
  633.  
  634. int THRESHOLD_poker = 4;
  635. void qs4_poker (VI& a, int lo, int hi) {
  636.     while (hi - lo > THRESHOLD_poker) { //THRESHOLD from 30 years ago was 20, experiment!
  637.         while (lo < hi) {
  638.             int m = qs3_Partition_poker(a, lo, hi);
  639.             if (m - lo < hi - m + 1) {
  640.                 qs4_poker(a, lo, m - 1);
  641.                 lo = m;
  642.             } else {
  643.                 qs4_poker(a , m , hi);
  644.                 hi = m - 1;
  645.             }
  646.         }
  647.     }
  648. }
  649.  
  650. void insertion_sort_poker(vector<int>& a){
  651.     for(int j = 1; j < a.size(); ++j){
  652.         int t = a[j];
  653.         //cout << j << ": t = " << t << std::endl;
  654.         for (int i = j; i > 0 && compareTo(a[i-1], t) >= 0; --i){
  655.             //cout << a[i-1] << " >= " << t << std::endl;
  656.             a[i] = a[i - 1];
  657.             a[i - 1] = t;
  658.             //print(a, n);
  659.             //cout << std::endl;
  660.         }
  661.     }
  662. }
  663.  
  664. void insertion_sort_int(vector<int>& a){
  665.     for(int j = 1; j < a.size(); ++j){
  666.         int t = a[j];
  667.         //cout << j << ": t = " << t << std::endl;
  668.         for (int i = j; i > 0 && a[i-1] >= t; --i){
  669.             //cout << a[i-1] << " >= " << t << std::endl;
  670.             a[i] = a[i - 1];
  671.             a[i - 1] = t;
  672.             //print(a, n);
  673.             //cout << std::endl;
  674.         }
  675.     }
  676. }
  677.  
  678. void poker_sort (VI& a, int n) {
  679.     qs4_poker(a, 0, n-1);
  680.     //print(a);
  681.     insertion_sort_poker(a);
  682. }
  683.  
  684. int median_of_3(VI& a, int lo, int hi){
  685.     int l = a[lo];
  686.     int h = a[hi];
  687.     int mid = (lo + hi)/2;
  688.     int m = a[mid];
  689.     //cout << "Taking median of " << l << " " << h << " " << m << endl;
  690.     if (l < m && m < h){
  691.         return m;
  692.     }
  693.     if (h < m && m < l){
  694.         return m;
  695.     }
  696.     if (m < l && l < h){
  697.         return l;
  698.     }
  699.     if (h < l && l < m){
  700.         return l;
  701.     }
  702.     return h;
  703. }
  704.  
  705. int qs3_Partition(VI& a, int lo, int hi) {
  706.     int x = median_of_3(a, lo, hi); //Coffee choice of partition
  707.     //cout << endl;
  708.     //cout << "Choice of partition element is: " << x  << " and lo is: " << lo << " and hi is: " << hi << endl;
  709.     while (lo < hi) {
  710.         while (a[lo] < x){
  711.             //cout << "Comparing " << a[lo] << " and " << x << " yielding: " << compareTo(a[lo], x) << endl;
  712.             ++lo;
  713.         }
  714.         while (a[hi] > x){
  715.             //cout << "Comparing " << a[hi] << " and " << x << " yielding: " << compareTo(a[hi], x) << endl;
  716.             --hi;
  717.         }
  718.         if (lo < hi) {
  719.             //cout << "Swapping " << a[lo] << " and " << a[hi] << endl;
  720.             swap(a, lo, hi);
  721.             /*int temp = a[lo];
  722.             a[lo++] = a[hi];
  723.             a[hi--] = temp;*/
  724.             if (a[lo] == a[hi]){
  725.                 lo++;
  726.             }
  727.             //print(a);
  728.             //cout << endl;
  729.             //cout << "lo is: " << lo << " and hi is: " << hi << endl;
  730.         }
  731.     }
  732.     //print(a);
  733.     //cout << endl;
  734.     return lo;
  735. }
  736.  
  737. int THRESHOLD = 4;
  738. void qs4 (VI& a, int lo, int hi) {
  739.     while (hi - lo > THRESHOLD) { //THRESHOLD from 30 years ago was 20, experiment!
  740.         while (lo < hi) {
  741.             int m = qs3_Partition(a, lo, hi);
  742.             if (m - lo < hi - m + 1) {
  743.                 qs4(a, lo, m - 1);
  744.                 lo = m;
  745.             } else {
  746.                 qs4(a , m , hi);
  747.                 hi = m - 1;
  748.             }
  749.         }
  750.     }
  751. }
  752.  
  753. void quick_sortCh (VI& a, int n) {
  754.     qs4(a, 0, n-1);
  755.     //print(a);
  756.     insertion_sort_int(a);
  757. }
  758.  
  759. void test_compare(int a, int b){
  760.     VVI hand1 = convert_to_hand(a);
  761.     VVI hand2 = convert_to_hand(b);
  762.     insertion_sort_hand(hand1);
  763.     insertion_sort_hand(hand2);
  764.     print_hand_names(hand1);
  765.     print_hand_names(hand2);
  766.     cout << compareTo(a, b) << endl;
  767. }
  768.  
  769. void test_quickSort(){
  770.     srand(47);
  771.     VI arr(10);
  772.     //for (int & i : arr){
  773.         //i = rand();
  774.    // }
  775.     arr = {228196026, 131205167, 368581579, 364747487, 179217708, 210864963, 240869247, 245896757, 331464223, 31677864,
  776.            4962899, 188558391, 70622447, 241845383, 40471450, 279904260, 83904058, 227541576, 241955757, 341082141,
  777.            112304018, 338619531, 352453177, 264113193, 53734509, 200145464, 316825830, 127852582, 187686961, 286780086};
  778.     print(arr);
  779.     cout << endl;
  780.     for (int i = 0; i < arr.size(); i++){
  781.         test_compare(arr[i], arr[i+1]);
  782.     }
  783.     cout << endl;
  784.     cout << isSorted_poker(arr) << std::endl;
  785.     //cout << median_of_3_poker(arr, 0, arr.size()-1) << endl;
  786.     //cout << qs3_Partition(arr, 0, arr.size()-1)  << " Partitioning complete." << std::endl;
  787.     poker_sort(arr, arr.size());
  788.     cout << isSorted_poker(arr) << endl;
  789.     //print(arr);
  790. }
  791.  
  792. void time_Sort(){
  793.     vector<int> v;
  794.     srand(47);
  795.     for (int i = 0; i < 50; ++i) {
  796.         int x = rand();
  797.         v.push_back(x);
  798.     }
  799.     auto start = high_resolution_clock::now();
  800.     poker_sort (v, v.size());
  801.     auto stop = high_resolution_clock::now();
  802.     auto duration = duration_cast<microseconds>(stop-start);
  803.     cout << "time: " << duration.count() << "\n";
  804. }
  805. int main() {
  806.     time_Sort();
  807.     //VVI hand = convert_to_hand(38132284);
  808.     //test_quickSort();
  809.     //test_cards();
  810.     //print_hand_names(hand);
  811.     //print_hand_values(hand);
  812.     //test_insertion(96611262);
  813.     //test_eval(38132284, 29673748);
  814.     //cout << endl;
  815.     //VI high_card = get_high_card(hand);
  816.     //print_card_names(high_card);
  817.     //test_compare( 245896757, 331464223);
  818.  
  819.  
  820. };
Add Comment
Please, Sign In to add comment