SHARE
TWEET

lab1 (version 2.0)

allekco Oct 18th, 2019 92 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <ctime>
  3. #include <conio.h>
  4. #include <cstdlib>
  5. using namespace std;
  6. #define N 100000
  7.  
  8. int randomazer (int min, int max) {
  9.     float random;
  10.     random = rand();
  11.     random = (random / RAND_MAX) * (max - min) + min;
  12.     return((int)random);
  13. }
  14.  
  15. void insertion(int* A) {
  16.     int j, i, ii;
  17.     for (j = 0; j <= N; j++) {
  18.         i = 1;
  19.         while (i < N) {
  20.             if (A[i] >= A[i - 1]) {
  21.                 i++;
  22.             }
  23.             else {
  24.                 while (A[i] < A[i - 1]) {
  25.                     ii = A[i - 1];
  26.                     A[i - 1] = A[i];
  27.                     A[i] = ii;
  28.                     i--;
  29.                 }
  30.                 i = N;
  31.             }
  32.         }
  33.     }
  34. }
  35.  
  36. void swap(int* a1, int* a2) {
  37.     int tmp = *a1;
  38.     *a1 = *a2;
  39.     *a2 = tmp;
  40. }
  41.  
  42. void Max_Heapify(int* A, int i, int n) {
  43.     int l, r, largest = i;
  44.     l = 2 * i + 1;
  45.     r = 2 * i + 2;
  46.  
  47.     if ((l < n) && (A[l] > A[largest])) {
  48.         largest = l;
  49.     }
  50.     else {
  51.         largest = i;
  52.     }
  53.     if ((r < n) && (A[r] > A[largest])) {
  54.         largest = r;
  55.     }
  56.  
  57.     if (largest != i) {
  58.         swap(&A[i], &A[largest]);
  59.         Max_Heapify(A, largest, n);
  60.     }
  61. }
  62.  
  63. void Build_Max_Heap(int* A, int n) {
  64.     int i;
  65.     for (i = N / 2 - 1; i >= 0; i--) {
  66.         Max_Heapify(A, i, n);
  67.     }
  68. }
  69.  
  70. void Heapsort(int* A, int n) {
  71.     int i;
  72.     Build_Max_Heap(A, n);
  73.     for (i = N - 1; i >= 0; i--) {
  74.         swap(&A[0], &A[i]);
  75.         Max_Heapify(A, 0, i);
  76.     }
  77. }
  78.  
  79. void input_console (int* A) {
  80.     int i;
  81.     if (N < 100) {
  82.         for (i = 0; i < N; i++) {
  83.             cout << A[i] << " ";
  84.         }
  85.         cout << "\n";
  86.     }
  87. }
  88.  
  89.  
  90. int main() {
  91.     int key1, key2;
  92.     int i;
  93.     int A[N+1];
  94.     int B[N+1]; //because we change array A in 1 sort
  95.     cout << "Please input 0 if you want input numbers by yourself, and smth else number if not \n";
  96.     cin >> key1;
  97.     if (key1 == 0) {
  98.         cout << "input numbers: ";
  99.         for (i = 0; i < N; i++) {
  100.             cin >> A[i];
  101.             B[i] = A[i];
  102.         }
  103.     } else {
  104.         for (i = 0; i < N; i++) {
  105.             A[i] = randomazer(1, 10);
  106.             B[i] = A[i];
  107.         }
  108.     }  
  109.     input_console(A);
  110.     int marker = 1;
  111.     while (marker) {
  112.         cout << "Which algoritm do you want?\n";
  113.         cout << "1.Insertion sorting\n";
  114.         cout << "2.Pyramidal sorting\n";
  115.         cout << "0.Exit\n";
  116.         cout << "Please choose number: ";
  117.         cin >> key2;
  118.         clock_t start = clock();
  119.         if (key2 == 0) {
  120.             marker = 0;
  121.         }
  122.         if (key2 == 1) {
  123.             insertion(A);
  124.         }
  125.         else {
  126.             Heapsort(B, N);
  127.         }
  128.         if (marker != 0){
  129.             clock_t end = clock();
  130.             double total_time = (double(end) - double(start)) / CLOCKS_PER_SEC;
  131.             input_console(A);
  132.             cout << "Time of work: ";
  133.             cout << total_time << "\n";
  134.         }
  135.     }
  136.     return 0;
  137. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top