Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Untitled

a guest Mar 13th, 2018 58 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. using namespace std;
  6. /*
  7. bool less(int i, int j) {
  8.     return i<j;
  9. //  return pq[i].compareTo(pq[j]) < 0;
  10. }
  11. */
  12. void exch(vector<int>& v, int i, int N) {
  13.     int t = v.at(i-1);
  14.     v.at(i-1) = v.at(N-1);
  15.     v.at(N-1) = t;
  16. }
  17.  
  18. void sink(vector<int>& v, int i, int N) {
  19.     while (2*i <= N) {
  20.         int j = 2*i;
  21.         if ((j < N) && (v.at(j)<v.at(j+1))) {
  22.             j++;
  23.         }
  24.         if (!(v.at(i) < v.at(j))) {
  25.             break;
  26.         }
  27.         exch(v, i, j);
  28.         i = j;
  29.     }
  30. }
  31.  
  32. void heapsort(vector<int>& v) {
  33.     int N = v.size();
  34.     for (int k=N/2; k>=1; k--) {
  35. //      cout << "Er að fara að sinka gildinu " << v.at(k) << endl;
  36.         sink(v, v.at(k), N);
  37.     }
  38.     while (N>1) {
  39.         N = N-1;
  40.         exch(v, 1, N);
  41.         sink(v, 1, N+1);
  42.     }
  43. }
  44.  
  45. bool issorted(vector<int>& v) {
  46.     /*
  47.      * Athugar hvort vigurinn v sé í stígandi röð
  48.      */
  49.     cout << endl;
  50.     for (int i = 1; i < v.size(); i++) {
  51.         if (v[i] < v[i - 1]) {
  52.             return false;
  53.         }
  54.     }
  55.     return true;
  56. }
  57.  
  58. int main() {
  59.     // Prófum sort á vigrum af lengdunum 0, 101, og 1000:
  60.     vector<int> sizes = {0, 101};
  61.     for (int n : sizes) {
  62.         // Upphafstillum v með tölunum 0 upp í n-1 í slembinni röð
  63.         vector<int> v(n);
  64.         for (int i = 0; i < n; i++) {
  65.             v[i] = i;
  66.         }
  67.         random_shuffle(v.begin(), v.end());
  68.  
  69.         // JÖS PRÓFUN
  70.         for (int i = 0; i < n; i++) {
  71.             cout << i << ": " << v[i] << endl;
  72.         }
  73.  
  74.         // Röðum v aftur
  75.         heapsort(v);
  76.        
  77.         //JÖS PRÓFUN
  78.         cout << "Kallað á heapsort" << endl;
  79.         for (int i = 0; i < n; i++) {
  80.             cout << i << ": " << v[i] << endl;
  81.         }
  82.        
  83.         // Athugum hvort röðunin tókst
  84.         if (issorted(v)) {
  85.             cout << "Röðun á " << v.size() << " staka vigri tókst" << endl;
  86.         } else {
  87.             cout << "Röðun á " << v.size() << " staka vigri mistókst" << endl;
  88.         }
  89.     }
  90. }
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