Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <iomanip>
- #include <algorithm>
- #include <random>
- #include <ctime>
- using namespace std;
- #include <algorithm>
- #include <iomanip>
- #include <iostream>
- #include <nmmintrin.h>
- #include <vector>
- using namespace std;
- void FillInc(int n, int* a);
- void FillDec(int n, int* a);
- void FillRand(int n, int* a);
- void swap(int* xp, int* yp);
- void PrintMas(int n, int* a);
- void heapify(int* a, int l, int r, int& c, int& m);
- int HeapSort(int n, int* a);
- void PrintTabl();
- int main() {
- srand(time(nullptr));
- int n;
- int* a;
- cin >> n;
- a = new int[n+1];
- FillRand(n, a);
- PrintMas(n, a);
- cout << endl;
- HeapSort(n, a);
- PrintMas(n, a);
- PrintTabl();
- }
- void heapify(int* a, int l, int r, int& c, int& m) {
- int x = a[l], j;
- int i = l;
- ++m;
- while (i <= r / 2) {
- j = 2 * i;
- ++c;
- if ((j < r) && (a[j + 1] <= a[j]))
- j++;
- ++c;
- if (x <= a[j]) {
- break;
- }
- ++m;
- a[i] = a[j];
- i = j;
- }
- ++m;
- a[i] = x;
- }
- int HeapSort(int n, int* a) {
- int l = n / 2, c = 0, m = 0;
- while (l > 0) {
- heapify(a, l, n, c, m);
- --l;
- }
- int r = n;
- while (r > 1) {
- m += 3;
- swap(a[1], a[r]);
- r--;
- heapify(a, 1, r, c, m);
- }
- int T = c + m;
- return T;
- }
- void FillInc(int n, int* a) {
- for (int i = 1; i <= n; ++i) {
- a[i] = i;
- }
- }
- void FillDec(int n, int* a) {
- for (int i = n; i >= 1; i--) {
- a[n - i] = i;
- }
- }
- void FillRand(int n, int* a) {
- for (int i = 1; i <= n; ++i) {
- a[i] = rand() % n;
- }
- }
- void swap(int* xp, int* yp) {
- int temp = *xp;
- *xp = *yp;
- *yp = temp;
- }
- void PrintMas(int n, int* a) {
- for (int i = 1; i <= n; ++i) {
- cout << a[i] << " ";
- }
- }
- void PrintTabl() {
- int n = 1, FR = 0, FD = 0, FI = 0;
- int* a = new int[n+1];
- cout << endl << "| HeapSort |" << endl;
- cout << "| n | FillInc | FillDec | FillRand |" << endl;
- for (int n = 100; n <= 500; n += 100)
- {
- FillRand(n, a);
- FR = HeapSort(n, a);
- FillInc(n, a);
- FI = HeapSort(n, a);
- FillDec(n, a);
- FD = HeapSort(n, a);
- cout << "|" << n << "|" << setw(11) << FI << "|" << setw(11) << FD << "|"
- << setw(12) << FR << "|" << endl;
- }
- delete[] a }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement