StoneHaos

m_mod_2

Mar 27th, 2021
298
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <functional>
  4. #include <algorithm>
  5. #include <time.h>
  6. #include <stdlib.h>
  7.  
  8. using namespace std;
  9.  
  10. void print(vector<int> v) {
  11.     for (int i = 0; i < v.size(); ++i)
  12.         cout << v[i] << " ";
  13.     cout << endl;
  14. }
  15.  
  16. int LinearSearch(vector<int> v, int elem) {
  17.     v.push_back(elem);
  18.     int i = 0;
  19.     while (v[i] != elem) i++;
  20.     return (i == v.size() - 1) ? -1 : i;
  21. }
  22.  
  23. void Heapify(vector<int>&v, int n, int a) {
  24.     int l = a * 2 + 1;
  25.     int r = a * 2 + 2;
  26.     int m = a;
  27.     if (l < n && v[l] > v[m]) m = l;
  28.     if (r < n && v[r] > v[m]) m = r;
  29.     if (m != a) {
  30.         swap(v[m], v[a]);
  31.         Heapify(v, n, m);
  32.     }
  33. }
  34.  
  35. vector<int> PyramidSort(vector<int> v) {
  36.     for (int i = v.size() - 1; i >= 0; --i) {
  37.         Heapify(v, v.size(), i);
  38.     }
  39.     int r = v.size() - 1;
  40.     for (; r > 0; --r) {
  41.         Heapify(v, r + 1, 0);
  42.         swap(v[0], v[r]);
  43.     }
  44.     return v;
  45. }
  46.  
  47. int InterpolationSearch(vector<int> v, int key) {
  48.     int m = 0, l = 0, r = v.size() - 1;
  49.     while (v[l] <= key && v[r] >= key) {
  50.         m = l + ((key - v[l]) * (r - l)) / (v[r] - v[l]);
  51.         if (v[m] < key) l = m + 1;
  52.         else if (v[m] > key) r = m - 1;
  53.         else return m;
  54.     }
  55.     return (v[l] == key) ? l : -1;
  56.  
  57. }
  58.  
  59. int main(void) {
  60.     time_t t = time(NULL);
  61.     cout << "t = " << t << endl;
  62.     srand(t);
  63.  
  64.     int n, e;
  65.     cout << "Length>";
  66.     cin >> n;
  67.     vector<int> v;
  68.     for (int i = 0; i < n; ++i) v.push_back(rand() % 100 - 50);
  69.     print(v);
  70.     cout << "Element>";
  71.     cin >> e;
  72.     cout << LinearSearch(v, e) << endl << endl;
  73.     v = PyramidSort(v);
  74.     print(v);
  75.     cout << "Element>";
  76.     cin >> e;
  77.     cout << InterpolationSearch(v, e) << endl;
  78.     return 0;
  79. }
RAW Paste Data