• API
• FAQ
• Tools
• Archive
A Pastebin account makes a great Christmas gift
SHARE
TWEET

# Untitled

a guest Mar 13th, 2018 58 Never
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.

Top