SHARE
TWEET

Untitled

a guest Dec 3rd, 2019 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //ALGO2 IS1 220b LAB04
  2. //Sebastian Ratanczuk
  3. //sebastian-ratanczuk@zut.edu.pl
  4. #include <iostream>
  5. #include <string>
  6. #include <time.h>
  7. #include <algorithm>
  8.  
  9. template <typename T>
  10. class Heap;
  11.  
  12. template <typename T>
  13. class Array {
  14.     friend class Heap<T>;
  15. private:
  16.     void increase()
  17.     {
  18.         this->MAX_CAP *= this->multip;
  19.         T* new_array = new T[MAX_CAP];
  20.  
  21.         for (unsigned int i = 0; i < this->counter; i++)
  22.             new_array[i] = this->array[i];
  23.  
  24.         delete[] this->array;
  25.         array = new_array;
  26.     }
  27.  
  28.     void set(unsigned int number, T data)
  29.     {
  30.         if (number < this->MAX_CAP)
  31.             this->array[number] = data;
  32.     }
  33.  
  34. public:
  35.     T* array;
  36.     unsigned int counter;
  37.     unsigned int MAX_CAP;
  38.     const int multip = 2;
  39.  
  40.     Array()
  41.     {
  42.         this->MAX_CAP = 1;
  43.         this->counter = 0;
  44.         this->array = new T[MAX_CAP];
  45.     }
  46.  
  47.     Array(Array* data)
  48.     {
  49.         this->MAX_CAP = data->MAX_CAP;     
  50.         this->counter = data->counter;
  51.         this->array = new T[this->MAX_CAP];
  52.         for (int i = 0; i < this->counter; i++)    
  53.             this->array[i] = data->array[i];       
  54.     }
  55.  
  56.     virtual ~Array()
  57.     {
  58.         //for (unsigned int i = 0; i < this->counter; i++)
  59.             //delete array[i];
  60.         delete[] array;
  61.     }
  62.  
  63.     void add_(T data)
  64.     {
  65.         if (this->counter < this->MAX_CAP)
  66.         {
  67.             this->array[this->counter] = data;
  68.             counter++;
  69.         }
  70.         else
  71.         {
  72.             this->increase();
  73.             this->array[this->counter] = data;
  74.             counter++;
  75.         }
  76.     }
  77.  
  78.     T return_(unsigned int number)
  79.     {
  80.         if (number < this->counter)
  81.             return this->array[number];
  82.         else
  83.             return NULL;
  84.     }
  85.  
  86.     std::string to_string(int a)
  87.     {
  88.         std::string str;
  89.         for (unsigned int i = 0; i < a; i++)
  90.             str = str + std::to_string(array[i]) + " ";
  91.         return str;
  92.     }
  93.  
  94.     void reset_()
  95.     {
  96.         this->MAX_CAP = 1;
  97.         this->counter = 0;
  98.  
  99.         T* new_array = new T[MAX_CAP];
  100.  
  101.         delete[] this->array;
  102.         this->array = new_array;
  103.     }  
  104. };
  105.  
  106. template <typename T>
  107. class Heap : private Array<T>
  108. {
  109. public:
  110.  
  111.     Heap() {}
  112.  
  113.     Heap(Array<T>* a)
  114.     {
  115.         this->array = a->array;
  116.         this->counter = a->counter;
  117.         this->MAX_CAP = a->MAX_CAP;
  118.     }
  119.  
  120.     void reset()
  121.     {
  122.         this->reset_();
  123.     }
  124.  
  125.     void heapUp()
  126.     {
  127.         for (int x = 0; x < this->counter; x++)
  128.         {
  129.             for (int i = (this->counter - 1); i >= x; i--)
  130.             {
  131.                 int parent = (i - 1) / 2;
  132.                 int a = this->array[i];
  133.                 int b = this->array[parent];
  134.                 if (this->array[i] > this->array[parent])
  135.                 {
  136.                     T tmp = this->array[i];
  137.                     this->array[i] = this->array[parent];
  138.                     this->array[parent] = tmp;
  139.                 }              
  140.             }          
  141.         }      
  142.     }
  143.  
  144.     void heapDown(int value)
  145.     {      
  146.         unsigned int current = value;
  147.         unsigned int left = value * 2 + 1;
  148.         unsigned int right = value * 2 + 2;
  149.  
  150.         if (left <= this->counter && right >= this->counter)
  151.         {
  152.             if (this->array[current] < this->array[left])
  153.             {
  154.                 T tmp = this->array[current];
  155.                 this->array[current] = this->array[left];
  156.                 this->array[left] = tmp;
  157.                 current = left;
  158.             }
  159.             return;
  160.         }
  161.  
  162.         if (left >= this->counter && right >= this->counter)
  163.             return;
  164.  
  165.         while ((this->array[current] < this->array[left]) || (this->array[current] < this->array[right]))
  166.         {
  167.             if ((this->array[left] - this->array[current]) > (this->array[right] - this->array[current]))
  168.             {
  169.                 T tmp = this->array[current];
  170.                 this->array[current] = this->array[left];
  171.                 this->array[left] = tmp;
  172.                 current = left;
  173.             }
  174.             else
  175.             {
  176.                 T tmp = this->array[current];
  177.                 this->array[current] = this->array[right];
  178.                 this->array[right] = tmp;
  179.                 current = right;
  180.             }
  181.  
  182.             left = current * 2 + 1;
  183.             right = current * 2 + 2;
  184.  
  185.             if (left <= this->counter && right >= this->counter)
  186.             {
  187.                 if (this->array[current] < this->array[left])
  188.                 {
  189.                     T tmp = this->array[current];
  190.                     this->array[current] = this->array[left];
  191.                     this->array[left] = tmp;
  192.                     current = left;
  193.                 }
  194.                 break;
  195.             }
  196.  
  197.             if (left >= this->counter && right >= this->counter)
  198.                 break;
  199.         }
  200.     }      
  201.  
  202.     void add(T data)
  203.     {
  204.         if (this->counter == 0)
  205.             this->add_(data);
  206.         else
  207.         {
  208.             unsigned int current = this->counter;
  209.             this->add_(data);
  210.             unsigned int parrent = (current - 1) / 2;
  211.             while (this->array[parrent] < this->array[current])
  212.             {
  213.                 T tmp = this->array[current];
  214.                 this->array[current] = this->array[parrent];
  215.                 this->array[parrent] = tmp;
  216.                 current = parrent;
  217.                 parrent = (current - 1) / 2;
  218.                 if (current == 0)
  219.                     break;
  220.             }
  221.         }
  222.     }
  223.  
  224.     T pop()
  225.     {
  226.         if (this->counter == 0)
  227.         {
  228.             const T to_ret = this->array[0];
  229.             this->reset_();
  230.             return to_ret;
  231.         }
  232.         else if (this->counter > 0)
  233.         {
  234.             const T to_ret = this->array[0];
  235.  
  236.             this->array[0] = this->array[--this->counter];
  237.             this->array[this->counter] = 0;
  238.             unsigned int current = 0;
  239.             unsigned int left = 1;
  240.             unsigned int right = 2;
  241.  
  242.             if (left >= this->counter && right >= this->counter)
  243.                 return to_ret;
  244.  
  245.             if (left <= this->counter && right > this->counter)
  246.             {
  247.                 if (this->array[current] > this->array[left])
  248.                 {
  249.                     T tmp = this->array[current];
  250.                     this->array[current] = this->array[left];
  251.                     this->array[left] = tmp;
  252.                     current = left;
  253.                 }
  254.                 return to_ret;
  255.             }      
  256.  
  257.             while ((this->array[current] < this->array[left]) || (this->array[current] < this->array[right]))
  258.             {  
  259.                 if ((this->array[left] - this->array[current]) > (this->array[right] - this->array[current]))
  260.                 {
  261.                     T tmp = this->array[current];
  262.                     this->array[current] = this->array[left];
  263.                     this->array[left] = tmp;
  264.                     current = left;
  265.                 }
  266.                 else
  267.                 {
  268.                     T tmp = this->array[current];
  269.                     this->array[current] = this->array[right];
  270.                     this->array[right] = tmp;
  271.                     current = right;
  272.                 }
  273.                 left = current * 2 + 1;
  274.                 right = current * 2 + 2;
  275.                 if (right > this->counter || left > this->counter)
  276.                     break;
  277.             }
  278.             return to_ret;
  279.         }
  280.         else
  281.             std::cout << "tablica pusta";
  282.     }
  283.  
  284.     std::string to_string()
  285.     {
  286.         std::string str;
  287.  
  288.         for (int i = 0; i < 10; i++)
  289.             str = str + std::to_string(this->array[i]) + " ";
  290.         return str;
  291.     }
  292.  
  293.     void createHeap()
  294.     {
  295.         for (int x = this->counter; x >= 0; x--)
  296.         {
  297.             this->heapDown(x);
  298.         }
  299.     }
  300.  
  301.     void sortHeap()
  302.     {
  303.         this->createHeap();    
  304.         //std::cout << this->to_string() << std::endl;
  305.         const unsigned int length = this->counter;
  306.         for (int i = 0; i < length; i++)
  307.         {
  308.             unsigned int index = this->counter-1;
  309.             T tmp = this->pop();
  310.             this->set(index, tmp);
  311.             //std::cout << this->to_string() <<", "<<this->counter <<", "<<tmp<<std::endl;         
  312.         }
  313.         this->counter = length;
  314.     }
  315. };
  316.  
  317. template <typename T>
  318. void sortCount(Array<T>* a)
  319. {
  320.     //std::cout << a->to_string() << std::endl;
  321.     int mine = min(a);
  322.     //std::cout << mine << std::endl;
  323.    
  324.  
  325.     for (int i = 0; i < a->counter; i++)
  326.         a->array[i] = a->array[i] - mine;
  327.    
  328.     //std::cout << a->to_string() << std::endl;
  329.  
  330.     int maxe = max(a);
  331.     //std::cout << maxe << std::endl;  
  332.  
  333.     int size = a->counter-1;
  334.     T* tablicaelementow = new T[(maxe+2)]; 
  335.  
  336.     for (int i = 0; i < maxe+1; i++)
  337.         ++tablicaelementow[i]=0;   
  338.  
  339.     for (int i = 0; i <= size; i++)
  340.         ++tablicaelementow[a->array[i]];   
  341.  
  342.     for (int i = maxe; i >= 0; i--)
  343.         for (int j = tablicaelementow[i];j>0;j--)
  344.             a->array[size--] = i;
  345.  
  346.     for (int i = 0; i < a->counter; i++)
  347.         a->array[i] = a->array[i] + mine;
  348.  
  349.     delete[] tablicaelementow;
  350. }
  351.  
  352. template <typename T>
  353. void sortBucket(Array<T>* a, const int n)
  354. {
  355.     using namespace std;
  356.     T mine = min(a);
  357.     T maxe = max(a);
  358.     int ilosc = maxe - mine;
  359.  
  360.     Array<T>** buckets = new Array<T>*[(ilosc+1)]; 
  361.     for (int i = 0; i < ilosc + 1; i++)
  362.     {
  363.         buckets[i] = new Array<T>;
  364.     }
  365.  
  366.     for (int i = 0; i < a->counter; i++)
  367.     {
  368.         //cout << a->array[i] - mine << endl;
  369.         buckets[a->array[i] - mine]->add_(a->array[i]);
  370.     }
  371.  
  372.     for (int i = 0; i < ilosc+1; i++)
  373.     {      
  374.         sortHeap(buckets[i]);
  375.     }
  376.  
  377.     int id = 0;
  378.     for (int i = 0; i < ilosc + 1; i++)
  379.     {
  380.         for (int j = 0; j < buckets[i]->counter; j++)
  381.             a->array[id++] = buckets[i]->array[j];
  382.     }  
  383.  
  384.     for (int i = 0; i < ilosc + 1; i++)
  385.     {
  386.         delete buckets[i];
  387.     }
  388.     delete[] buckets;  
  389. }
  390.  
  391. template<typename T>
  392. bool isSorted(Array<T>* a){
  393.    
  394.     for (int i = 0; i < a->counter-1; i++)
  395.     {
  396.         if (a->array[i] > a->array[i + 1])
  397.             return false;
  398.     }
  399.     return true;
  400. }
  401.  
  402. template<typename T>
  403. T min(Array<T>* a)
  404. {
  405.     T min = a->array[0];   
  406.  
  407.     for (int i = 0; i < a->counter; i++)   
  408.         if (min > a->array[i])
  409.             min = a->array[i]; 
  410.     return min;
  411. }
  412.  
  413. template<typename T>
  414. T max(Array<T>* a)
  415. {  
  416.     T max = a->array[0];
  417.  
  418.     for (int i = 0; i < a->counter; i++)           
  419.         if (max < a->array[i])
  420.             max = a->array[i];
  421.    
  422.     return max;
  423. }
  424.  
  425. template <typename T>
  426. void sortHeap(Array<T>* a)
  427. {
  428.     Heap<T>* heap = new Heap<T>(a);
  429.     heap->sortHeap();
  430. }
  431.  
  432. int porownaj_int(const void* a, const void* b) {  // funkcja porównująca
  433.     int* arg1 = (int*)a;
  434.     int* arg2 = (int*)b;
  435.     if (*arg1 < *arg2) return -1;
  436.     else if (*arg1 == *arg2) return 0;
  437.     else return 1;
  438. }
  439.  
  440. template<typename T>
  441. void sortQuick(Array<T>*a)
  442. {
  443.     std::qsort(a->array, a->counter, sizeof(int), porownaj_int);
  444. }
  445.  
  446. int main()
  447. {
  448.     //srand(time(NULL));
  449.     srand(0);
  450.     const int MAX_ORDER = 8;
  451.     for (int o = 1; o < MAX_ORDER; o++)
  452.     {
  453.         std::cout << "Przebieg " << o << std::endl;
  454.         Array<int>* tablica1 = new Array<int>;
  455.         const int MAXIMUM = pow(10,5);
  456.         const int n = pow(10, o);      
  457.  
  458.         for (int i = 0; i < n; i++)
  459.             tablica1->add_(((rand() << 15) + rand()) % MAXIMUM);
  460.  
  461.         Array<int>* tablica2 = new Array<int>(tablica1);
  462.         Array<int>* tablica3 = new Array<int>(tablica1);
  463.         Array<int>* tablica4 = new Array<int>(tablica1);
  464.  
  465.         //heap sort
  466.         Heap<int>* kopiec = new Heap<int>(tablica1);   
  467.  
  468.         clock_t t1 = clock();
  469.         kopiec->sortHeap();
  470.         clock_t t2 = clock();
  471.        
  472.         double time1 = (t2 - t1) / (double)CLOCKS_PER_SEC;
  473.         std::cout << "Heap sort: " << "Czas ogolny: " << time1 * 1000 << " milisekund. " << "Czas na element: " << (time1 / n) * 1000000 << " mikrosekund. "  << "Is sorted? " << isSorted(tablica1) << std::endl;
  474.         //std::cout << tablica1->to_string() << std::endl;     
  475.        
  476.         //count sort       
  477.         t1 = clock();
  478.         sortCount(tablica2);
  479.         t2 = clock();
  480.         time1 = (t2 - t1) / (double)CLOCKS_PER_SEC;
  481.         std::cout << "Count sort: " << "Czas ogolny: " << time1 * 1000 << " milisekund. " << "Czas na element: " << (time1 / n) * 1000000 << " mikrosekund. " << "Is sorted? " << isSorted(tablica2) << std::endl;
  482.         //std::cout << tablica2->to_string() << std::endl;
  483.        
  484.         //bucket sort
  485.         t1 = clock();
  486.         sortBucket(tablica3, 1);
  487.         t2 = clock();
  488.         time1 = (t2 - t1) / (double)CLOCKS_PER_SEC;
  489.         std::cout << "Bucket sort: " << "Czas ogolny: " << time1 * 1000 << " milisekund. " << "Czas na element: " << (time1 / n) * 1000000 << " mikrosekund. " << "Is sorted? " << isSorted(tablica3) << std::endl;
  490.         //std::cout << tablica3->to_string() << std::endl;
  491.  
  492.         //quick sort
  493.         t1 = clock();
  494.         sortQuick(tablica4);
  495.         t2 = clock();
  496.         time1 = (t2 - t1) / (double)CLOCKS_PER_SEC;
  497.         std::cout << "Quick sort: " << "Czas ogolny: " << time1 * 1000 << " milisekund. " << "Czas na element: " << (time1 / n) * 1000000 << " mikrosekund. " << "Is sorted? " << isSorted(tablica4) << std::endl << std::endl;
  498.         //std::cout << tablica3->to_string() << std::endl;
  499.        
  500.         delete tablica1;
  501.         delete tablica2;
  502.         delete tablica3;
  503.         delete tablica4;
  504.     }
  505.    
  506.     return 0;
  507. }
  508.  
  509. class Osoba
  510. {
  511. public:
  512.     int losowepole1;
  513.     int losowepole2;
  514.  
  515.     Osoba()
  516.     {
  517.         losowepole1 = rand();  
  518.         losowepole2 = rand();
  519.     }
  520.  
  521.     void operator = (int z)
  522.     {
  523.         this->losowepole1 = z;     
  524.     }
  525.  
  526.     bool operator < (Osoba x)
  527.     {
  528.         if (this->losowepole1 < x.losowepole1)
  529.         {
  530.             return true;
  531.         }
  532.         return false;
  533.     }
  534.  
  535.     bool operator > (Osoba x)
  536.     {
  537.         if (this->losowepole1 > x.losowepole1)
  538.         {
  539.             return true;
  540.         }
  541.         return false;
  542.     }
  543.  
  544.     int operator - (Osoba x)
  545.     {
  546.         return (this->losowepole1 - x.losowepole1);
  547.     }
  548. };
  549.  
  550. //int main()//obiekty
  551. //{
  552. //  srand(time(NULL));
  553. //  srand(0);
  554. //  const int MAX_ORDER = 8;
  555. //  for (int o = 1; o < MAX_ORDER; o++)
  556. //  {
  557. //      std::cout << "Przebieg " << o << std::endl;
  558. //      Array<Osoba>* tablica1 = new Array<Osoba>;
  559. //      const int MAXIMUM = pow(10,5);
  560. //      const int n = pow(10, o);
  561. //     
  562. //      for (int i = 0; i < n; i++)
  563. //      {
  564. //          Osoba os;
  565. //          tablica1->add_(os);
  566. //      }          
  567. //     
  568. //      Array<Osoba>* tablica2 = new Array<Osoba>(tablica1);       
  569. //     
  570. //
  571. //      //heap sort
  572. //      Heap<Osoba>* kopiec = new Heap<Osoba>(tablica1);   
  573. //
  574. //      clock_t t1 = clock();
  575. //      kopiec->sortHeap();
  576. //      clock_t t2 = clock();
  577. //     
  578. //      double time1 = (t2 - t1) / (double)CLOCKS_PER_SEC;
  579. //      std::cout << "Heap sort: " << "Czas ogolny: " << time1 * 1000 << " milisekund. " << "Czas na element: " << (time1 / n) * 1000000 << " mikrosekund. "  << "Is sorted? " << isSorted(tablica1) << std::endl;
  580. //      //std::cout << tablica1->to_string() << std::endl;     
  581. //     
  582. //     
  583. //     
  584. //      //bucket sort
  585. //      t1 = clock();
  586. //      sortBucket(tablica2, 1);
  587. //      t2 = clock();
  588. //      time1 = (t2 - t1) / (double)CLOCKS_PER_SEC;
  589. //      std::cout << "Bucket sort: " << "Czas ogolny: " << time1 * 1000 << " milisekund. " << "Czas na element: " << (time1 / n) * 1000000 << " mikrosekund. " << "Is sorted? " << isSorted(tablica2) << std::endl;
  590. //      //std::cout << tablica3->to_string() << std::endl;
  591. //     
  592. //      delete tablica1;
  593. //      delete tablica2;       
  594. //  }
  595. // 
  596. //  return 0;
  597. //}
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top