Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <vector>
- using namespace std;
- /*
- bool less(int i, int j) {
- return i<j;
- // return pq[i].compareTo(pq[j]) < 0;
- }
- */
- void exch(vector<int>& v, int i, int N) {
- int t = v.at(i-1);
- v.at(i-1) = v.at(N-1);
- v.at(N-1) = t;
- }
- void sink(vector<int>& v, int i, int N) {
- while (2*i <= N) {
- int j = 2*i;
- if ((j < N) && (v.at(j)<v.at(j+1))) {
- j++;
- }
- if (!(v.at(i) < v.at(j))) {
- break;
- }
- exch(v, i, j);
- i = j;
- }
- }
- void heapsort(vector<int>& v) {
- int N = v.size();
- for (int k=N/2; k>=1; k--) {
- // cout << "Er að fara að sinka gildinu " << v.at(k) << endl;
- sink(v, v.at(k), N);
- }
- while (N>1) {
- N = N-1;
- exch(v, 1, N);
- sink(v, 1, N+1);
- }
- }
- bool issorted(vector<int>& v) {
- /*
- * Athugar hvort vigurinn v sé í stígandi röð
- */
- cout << endl;
- for (int i = 1; i < v.size(); i++) {
- if (v[i] < v[i - 1]) {
- return false;
- }
- }
- return true;
- }
- int main() {
- // Prófum sort á vigrum af lengdunum 0, 101, og 1000:
- vector<int> sizes = {0, 101};
- for (int n : sizes) {
- // Upphafstillum v með tölunum 0 upp í n-1 í slembinni röð
- vector<int> v(n);
- for (int i = 0; i < n; i++) {
- v[i] = i;
- }
- random_shuffle(v.begin(), v.end());
- // JÖS PRÓFUN
- for (int i = 0; i < n; i++) {
- cout << i << ": " << v[i] << endl;
- }
- // Röðum v aftur
- heapsort(v);
- //JÖS PRÓFUN
- cout << "Kallað á heapsort" << endl;
- for (int i = 0; i < n; i++) {
- cout << i << ": " << v[i] << endl;
- }
- // Athugum hvort röðunin tókst
- if (issorted(v)) {
- cout << "Röðun á " << v.size() << " staka vigri tókst" << endl;
- } else {
- cout << "Röðun á " << v.size() << " staka vigri mistókst" << endl;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement