Advertisement
O_Egor

Задание два (сортировки простые)

Sep 29th, 2022
683
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.53 KB | None | 0 0
  1. #include <vector>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <string>
  6. #include <set>
  7. #include <map>
  8. #include <iomanip>
  9. #include <time.h>
  10. #include <stdlib.h>
  11. using namespace std;
  12.  
  13. int ks = 0, kd = 0;
  14.  
  15. void selectionSort(vector <int> v, int sz)//Сортировка выбором
  16. {
  17.     cout << "Start array: "; //Здесь выводим исходный массив
  18.     for (int i = 0; i < sz; ++i)
  19.         cout << v[i] << ' ';
  20.     cout << '\n';
  21.     int last = sz - 1; //Индекс последнего элемента
  22.     kd = 0; ks = 0; //обнуляем кол-во действий и сравнений
  23.     while (last != 0)//пока последний элемент не является превым
  24.     {
  25.         int mx = 0; // позиция для поиска максимума (инзначально считаем, что макс - это первый элем)
  26.         for (int i = 1; i <= last; ++i)//бежим от начала массива до последнего элемента, который не на месте
  27.         {
  28.             ks++;//увеличиваем кол-во сравнений
  29.             if (v[i] > v[mx])//поиск максимума в последовательности (вернее индекс максимального)
  30.             {
  31.                 mx = i;
  32.             }
  33.         }
  34.         if (mx != last)//если максимальный элемент в конце, то не меняем
  35.         {
  36.             swap(v[mx], v[last]);//меняем наш максимальный и последний элемент, который не на своём месте
  37.             kd++;
  38.         }
  39.         last--;//уменьшаем кол-во элементов, которые не на своём месте
  40.         //Для массива : 3 2 7 10 12 4 при первой итерации у нас 12 встанет в конец (на своё место), тогда уменьшаем last, так как
  41.         //12 уже на своём месте и так далее, я хуёво объясняю, лучше в инете глянуть
  42.     }
  43.  
  44.     cout << "Result: ";
  45.     for (int i = 0; i < sz; ++i)
  46.         cout << v[i] << ' ';
  47.     cout << "\nSravnenii : " << ks << "\nDeistvii : " << kd << "\n\n";
  48.  
  49.     return;
  50. }
  51.  
  52. void puzirkSort(vector <int> v, int sz)//Пузырёк
  53. {
  54.     cout << "Start array: ";
  55.     for (int i = 0; i < sz; ++i)
  56.         cout << v[i] << ' ';
  57.     cout << '\n';
  58.     kd = 0; ks = 0;
  59.  
  60.     for (int i = 0; i < sz; ++i)//В этом цикле i - кол-во элементов на своём месте, то есть сколько элементов отсорчено
  61.     {
  62.         for (int j = 1; j < sz - i; ++j)//здесь мы бежим по массиву от начала и до конца - i, то есть не смотрим те элементы, которые на своём месте
  63.         {
  64.             ks++;//считаем кол-во сравнений
  65.             if (v[j - 1] > v[j])//условие обмена (максимальный из двух идёт дальше)
  66.             {
  67.                 swap(v[j - 1], v[j]);
  68.                 kd++;//считаем действия
  69.             }
  70.         }
  71.     }
  72.     cout << "Result: ";
  73.     for (int i = 0; i < sz; ++i)
  74.         cout << v[i] << ' ';
  75.     cout << "\nSravnenii : " << ks << "\nDeistvii : " << kd << "\n\n";
  76.  
  77.     return;
  78. }
  79.  
  80. void updatedPuzirkSort(vector <int> v, int sz)//такой же как пузырёк, только с одним улучшением, опишу дальше
  81. {
  82.     cout << "Start array: ";
  83.     for (int i = 0; i < sz; ++i)
  84.         cout << v[i] << ' ';
  85.     cout << '\n';
  86.     kd = 0; ks = 0;
  87.  
  88.     for (int i = 0; i < sz; ++i)
  89.     {
  90.         bool swapped(0);//вот! Это флаг, который указывает, был ли совершён обмен, если при каком-то проходе обмен не был совершён,
  91.                         //то последовательность уже отсортирована
  92.         for (int j = 1; j < sz - i; ++j)
  93.         {
  94.             ks++;//считаем сравнения
  95.             if (v[j - 1] > v[j])
  96.             {
  97.                 swapped = 1;//поднимаем флаг обмена
  98.                 swap(v[j - 1], v[j]);//меняем
  99.                 kd++;//считаем действия
  100.             }
  101.         }
  102.         if (!swapped)//проверка на то, был ли совершён обмен
  103.             break;
  104.     }
  105.     cout << "Result: ";
  106.     for (int i = 0; i < sz; ++i)
  107.         cout << v[i] << ' ';
  108.     cout << "\nSravnenii : " << ks << "\nDeistvii : " << kd << "\n\n";
  109.  
  110.     //P.S. эта сортировка лучше только в том случае, когда последовательность частично отсорчена
  111.  
  112.     return;
  113. }
  114.  
  115. void shakerSort(vector <int> v, int sz)// Это та же сортировка, что и улучшенный пузырь, только после того, как переместили максимальный элемент
  116. {                                      // движемся обратно и ставим на своё место минимальный
  117.     cout << "Start array: ";
  118.     for (int i = 0; i < sz; ++i)
  119.         cout << v[i] << ' ';
  120.     cout << '\n';
  121.     kd = 0; ks = 0;
  122.  
  123.     int left(0), right(sz - 1); // тут границы, до которых все стоит на своих местах, изначально 0 и конец
  124.  
  125.     while (true)//Бесконечный цикл, условие выхода ниже
  126.     {
  127.         bool swapped(false);//флаг как в улучшенном пузырьке
  128.  
  129.         for (int i = left; i < right; ++i)//в этом цикле как и выше ставим на место максимальный
  130.         {
  131.             ks++;
  132.             if (v[i] > v[i + 1])
  133.             {
  134.                 swapped = 1;
  135.                 kd++;
  136.                 swap(v[i], v[i + 1]);
  137.             }
  138.         }
  139.         right--;//уменьшаем это, так как у нас ещё один элемент встаёт на место
  140.  
  141.         if (left < right && swapped) //далее смотрим, если у нас правая и левая граница не пересеклись и мы свапались (то есть последовательность неотсорчена)
  142.         {                            // то движемся влево, чтобы поставить минимум на место
  143.             swapped = 0;//обнуляем флаг
  144.             for (int i = right; i > left; --i)//движемся от последнего неотсорченного до первого отсорченного (справа налево)
  145.             {
  146.                 ks++;
  147.                 if (v[i] < v[i - 1])
  148.                 {
  149.                     swapped = 1;
  150.                     kd++;
  151.                     swap(v[i], v[i - 1]);
  152.                 }
  153.             }
  154.             left++;//увеличиваем левую границу, так как ещё одно число встало на место
  155.             if (!swapped || right == left) // если не свапали (то есть ничего не надо было менять), то последовательность отсорчена или правая и левая граница
  156.                 break;                     //пересеклись то мы прошли по все элементам, значит всё отсортировали
  157.         }
  158.         else //141 строчка, если она не выполняется, то последовательность отсорчена
  159.             break;
  160.     }
  161.  
  162.     cout << "Result: ";
  163.     for (int i = 0; i < sz; ++i)
  164.         cout << v[i] << ' ';
  165.     cout << "\nSravnenii : " << ks << "\nDeistvii : " << kd << "\n\n";
  166.  
  167.     return;
  168. }
  169.  
  170. void sortvst(vector <int> v, int sz) //Сортировка вставкой
  171. {
  172.     cout << "Start array: ";
  173.     for (int i = 0; i < sz; ++i)
  174.         cout << v[i] << ' ';
  175.     cout << '\n';
  176.     ks = 0; kd = 0;
  177.     for (int i = 1; i < sz; ++i)
  178.     {
  179.         int zn = v[i], j = i - 1;
  180.         while (j >= 0 && zn < v[j])
  181.         {
  182.             ks++;
  183.             v[j + 1] = v[j];
  184.             kd++;
  185.             j--;
  186.         }
  187.         v[j + 1] = zn;
  188.         kd++;
  189.     }
  190.     cout << "Result: ";
  191.     for (int i = 0; i < sz; ++i)
  192.         cout << v[i] << ' ';
  193.     cout << "\nSravnenii : " << ks << "\nDeistvii : " << kd << "\n\n";
  194.    
  195.     return;
  196. }
  197.  
  198. int main()
  199. {
  200.     setlocale(LC_ALL, "Russian");
  201.     int sz;
  202.     cout << "Input size of array: ";
  203.     cin >> sz;
  204.     vector <int> v(sz);
  205.     srand(time(NULL));
  206.     for (int i = 0; i < sz; ++i)
  207.     {
  208.         v[i] = rand() % 100;
  209.         cout << v[i] << ' ';
  210.     }
  211.     int type;
  212.     cout << "\nSelect type of sort:\n\t(1)Viborom\n\t(2)Puzirkom\n\t(3)Uluchshenim puzirkom\n\t(4)Shekernya\n\t(5)Vstavkoi\n";
  213.     cin >> type;
  214.     while (type)
  215.     {
  216.         switch (type)
  217.         {
  218.         case 1: selectionSort(v, sz); break;
  219.         case 2: puzirkSort(v, sz); break;
  220.         case 3: updatedPuzirkSort(v, sz); break;
  221.         case 4: shakerSort(v, sz); break;
  222.         case 5: sortvst(v, sz); break;
  223.         }
  224.         cout << "Select type of sort again(if you need):\n\t(0)Exit\n\t(1)Viborom\n\t(2)Puzirkom\n\t(3)Uluchshenim puzirkom\n\t(4)Shekernya\n\t(5)Vstavkoi\n";
  225.         cin >> type;
  226.     }
  227.     return 0;
  228. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement