Facebook
From Matyo, 1 Week ago, written in C++.
Embed
Download Paste or View Raw
Hits: 147
  1. #include <iostream>
  2. #include <chrono>
  3. #include <algorithm>
  4. using namespace std;
  5. using namespace std::chrono;
  6.  
  7. int Line_Search(int arr[], int n, int k)
  8. {
  9.     for (int i = 0; i < n; i++)
  10.         if (arr[i] == k)
  11.             return i;
  12.     return -1;
  13. }
  14.  
  15. int Line_Search_Order(int arr[], int n, int k)
  16. {
  17.     int i;
  18.     for (i = 0; i < n; i++)
  19.         if (arr[i] >= k)
  20.             break;
  21.     if (arr[i] == k)
  22.         return i;
  23.     else
  24.         return -1;
  25. }
  26.  
  27. int seq_search(int arr[], unsigned lf, unsigned rt, int key)
  28. {
  29.     for (int i = lf; i < rt; i++)
  30.     {
  31.         if (arr[i] == key)
  32.             return i;
  33.     }
  34.     /*while (lf <= rt)
  35.          if (arr[lf++] == key)
  36.              return lf - 1;
  37.      */
  38.     return -1;
  39. }
  40.  
  41. int jmp_search(int arr[], int n, int key, unsigned step)
  42. {
  43.     int i, rt, lf;
  44.     for (i = 0; i < n && arr[i] < key; i += step);
  45.     if (i < step)
  46.         lf = 0;
  47.     else
  48.         lf = i + 1 - step;
  49.     if (n < i)
  50.         rt = n - 1;
  51.     else
  52.         rt = i;
  53.     return seq_search(arr, lf, rt, key);
  54. }
  55.  
  56. int inter_search(int a[], int key, int lf, int rt, int num)
  57. {
  58.     unsigned m;
  59.     float k;
  60.     while (lf <= rt)
  61.     {
  62.         if (a[rt] == a[lf])
  63.             if (a[lf] == key)
  64.                 return lf; //елементът е намерен
  65.             else
  66.                 return 0;
  67.         k = (float)(key - a[lf]) / (a[rt] - a[lf]); //коефициент на позицията
  68.         if (k < 0 || k>1)
  69.             return 0;
  70.         m = (unsigned)(lf + k * (rt - lf) + 0.5);
  71.         if (key < a[m])
  72.             rt = m - 1;
  73.         else
  74.             if (key > a[m])
  75.                 lf = m + 1;
  76.             else
  77.                 return m;
  78.     }
  79.     return 0;
  80. }
  81.  
  82. int Bin_search(int a[], int lf, int rt, int k)
  83. // a[] - подредена последователност от num цели числа
  84. // k - търсената стойност
  85. // lf - left - лявата граница на индекса
  86. // rt - right - дясната граница на индекса
  87. // Обръщението към функцията изглежда така:
  88. // Bin_search(a,0,num,k)
  89. {//5 10 15 18 20 23 24 25
  90.     if (lf > rt)
  91.         return -1;
  92.     int m = (lf + rt) / 2;
  93.     if (a[m] == k)
  94.         return m;
  95.     if (a[m] > k)
  96.         return Bin_search(a, lf, m - 1, k);
  97.     else
  98.         return Bin_search(a, m + 1, rt, k);
  99. }
  100.  
  101. void Print(int a[], int n)
  102. {
  103.     cout << "Elementite na masiva sa: {";
  104.     for (int i = 0; i < n; i++)
  105.     {
  106.         cout << " " << a[i];
  107.     }
  108.     cout << " }";
  109.  
  110. }
  111.  
  112. void Bubblesort(int a[], int n)
  113. {
  114.     int r, i, j;
  115.     for (i = n - 1; i >= 0; i--)
  116.         for (j = 0; j <= i; j++)
  117.             if (a[j - 1] > a[j])
  118.             {
  119.                 r = a[j]; a[j] = a[j - 1]; a[j - 1] = r;
  120.             }
  121. }
  122.  
  123. int main()
  124. {
  125.     int arr[1000];
  126.     int step, k, n = sizeof(arr) / sizeof(arr[0]);
  127.     //srand(time(0));
  128.     for (int i = 0; i < n; i++)
  129.     {
  130.         arr[i] = rand() % 5001;
  131.     }
  132.     cout << "\n-------------Nesortiran masiv-------------" << endl;;
  133.     Print(arr, n);
  134.     //auto start = high_resolution_clock::now();
  135.    // Bubblesort(arr, n);
  136.     sort(arr, arr + n);
  137.     //auto stop = high_resolution_clock::now();
  138.      //auto durati>(stop - start);
  139.    // cout << "\nVremeto za izpalnenie na sort e: " << duration.count() << "microseconds" << endl;
  140.     //Bubblesort(arr, n);
  141.     cout << "\n-------------Sortiran masiv-------------" << endl;
  142.     Print(arr, n);
  143.     cout << "\nVavedi tarsenata stojnost k=";
  144.     cin &gt;&gt; k;
  145.     cout &lt;&lt; "Vavedi stapkata na tarsene step=";
  146.     cin &gt;&gt; step;
  147.     /*
  148.     auto start = high_resolution_clock::now();
  149.     int pos = Bin_search(arr, 0, n-1, k);
  150.     //int pos = inter_search(arr, k, 0, n-1, n);
  151.     auto stop = high_resolution_clock::now();
  152.      auto durati - start);
  153.     */
  154.     auto start1 = high_resolution_clock::now();
  155.     //int pos1 = Line_Search_Order(arr, n, k);
  156.     int pos1 = jmp_search(arr, n, k, step);
  157.     auto stop1 = high_resolution_clock::now();
  158.      auto durati - start1);
  159.  
  160.     if (pos1 != -1)
  161.         cout &lt;&lt; "Elementa e nameren na poziciq: " << pos1;
  162.     else
  163.         cout << "Elementa ne e nameren " << endl;
  164.     cout << "\nVremeto za izpalnenie na jmp_search e: " << duration1.count() << " microseconds" << endl;
  165.     //cout << "\nVremeto za izpalnenie e: line_search e: " << duration1.count() << " nanoseconds" << endl;
  166. }