Advertisement
Guest User

Untitled

a guest
Sep 29th, 2016
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.29 KB | None | 0 0
  1. //****************************************************//
  2. //                 Лабораторная работа №1             //
  3. //      по курсу "Модели и структуры данных"          //
  4. //                                                    //                  
  5. //       Исследование простых алгоритмов сортировки   //
  6. //                   Вариант 24                       //
  7. //                                                    //
  8. //              группа 525a Даниил Артемьев           //
  9. //****************************************************//
  10.  
  11. #include<stdio.h>
  12. #include<stdlib.h>
  13. #include<time.h>
  14. #include <iostream>
  15. #include <cassert>
  16. #include <vector>
  17. #include <iostream>
  18. using namespace std;
  19.  
  20. int Number_of_Elements, num_of_sr = 0, num_of_pr = 0;
  21. int mas[100];
  22. double mas_1[100];
  23.  
  24.  
  25. void show(double mas_1[100]) {
  26.     for (int i = 0; i<Number_of_Elements; i++)
  27.         printf(" %f ", mas_1[i]);
  28.     printf("\n");
  29. }
  30. static void BucketSort(int* data, int count) {
  31.     int minValue = data[0];
  32.     int maxValue = data[0];
  33.  
  34.     for (int i = 1; i < count; i++)
  35.     {
  36.         num_of_pr++;
  37.         num_of_sr++;
  38.         if (data[i] > maxValue)
  39.             maxValue = data[i];
  40.         if (data[i] < minValue)
  41.             minValue = data[i];
  42.     }
  43.  
  44.     int bucketLength = maxValue - minValue + 1;
  45.     num_of_pr++;
  46.     vector<int>* bucket = new vector<int>[bucketLength];
  47.  
  48.     for (int i = 0; i < bucketLength; i++)
  49.     {
  50.         num_of_pr++;
  51.         bucket[i] = vector<int>();
  52.     }
  53.  
  54.     for (int i = 0; i < count; i++)
  55.     {
  56.         num_of_pr++;
  57.         bucket[data[i] - minValue].push_back(data[i]);
  58.     }
  59.  
  60.     int k = 0;
  61.     for (int i = 0; i < bucketLength; i++)
  62.     {
  63.         int bucketSize = bucket[i].size();
  64.         num_of_pr++;
  65.         if (bucketSize > 0)
  66.         {
  67.             num_of_sr++;
  68.             for (int j = 0; j < bucketSize; j++)
  69.             {
  70.                 num_of_pr++;
  71.                 data[k] = bucket[i][j];
  72.                 k++;
  73.             }
  74.         }
  75.     }
  76. }
  77. void counting_sort(int* vec, int len, int min, int max)
  78. {
  79.     int * cnt = new int[max - min + 1];
  80.  
  81.     for (int i = min; i <= max; ++i) {
  82.         cnt[i - min] = 0;
  83.         num_of_pr ++ ;
  84.  
  85.     }
  86.  
  87.     for (int i = 0; i < len; ++i) {
  88.         ++cnt[vec[i] - min];
  89.         num_of_pr++;
  90.     }
  91.  
  92.     for (int i = min; i <= max; ++i) {
  93.         for (int j = cnt[i - min]; j--;) {
  94.             num_of_sr++;
  95.             *vec++ = i;
  96.             num_of_pr++;
  97.         }
  98.  
  99.     }
  100.     delete[] cnt;
  101. }
  102.  
  103. int main()
  104. {
  105.     int  key, min_value = 0, max_value = 0;
  106.     for (;;) {
  107.         int  key, min_value = 0, max_value = 0;
  108.         printf("Enter the number of elements (<100): "); //вводколичестваэлементовмассива
  109.         scanf_s("%i", &Number_of_Elements);
  110.         min_value = 0;
  111.         max_value = 100;
  112.  
  113.         //менювыборатипаупорядоченостимассива
  114.         printf("Choose the type of mas:\n1.min-max\n2.max-min\n3.not sort\n");
  115.         scanf_s("%i", &key);
  116.         srand(time_t(0));
  117.         //массив с равноменро распределенными случайными числами
  118.         if (key == 3)
  119.             for (int i = 0; i<Number_of_Elements; i++)
  120.                 mas[i] = min_value + rand() % (max_value - min_value);
  121.         //массив упорядочен по убыванию
  122.         if (key == 2) {
  123.             mas[0] = max_value;
  124.             for (int i = 1; i<Number_of_Elements; i++)
  125.                 mas[i] = mas[i - 1] - 1;
  126.         }
  127.         //массив упорядочен по возрастанию
  128.         if (key == 1) {
  129.             mas[0] = min_value;
  130.             for (int i = 1; i<Number_of_Elements; i++)
  131.                 mas[i] = mas[i - 1] + 1;
  132.         }
  133.         for (int i = 0; i < Number_of_Elements; i++) {
  134.             mas_1[i] = static_cast<double>(mas[i]) / 1;
  135.         }
  136.  
  137.         show(mas_1);
  138.  
  139.         //менявыборатипасортировки
  140.         printf("Choose the way for sorting:\n 1 counting sort\n 2 bucket sort \n");
  141.         scanf_s("%i", &key);
  142.         //выбор сортировки методом пузырька
  143.         if (key == 1) {
  144.             counting_sort(mas, Number_of_Elements, min_value, max_value);
  145.             //выбор сортировки простым выбором
  146.         }
  147.         if (key == 2) {
  148.             BucketSort(mas, Number_of_Elements);
  149.         }
  150.         for (int i = 0; i < Number_of_Elements; i++) {
  151.             mas_1[i] = static_cast<double>(mas[i]) / 1;
  152.         }
  153.         show(mas_1);
  154.         printf("Number of comparison  == %i\n______________________________\n", num_of_sr);
  155.         printf("Number of assignment  == %i\n______________________________\n", num_of_pr);
  156.         printf("                 Sum == %i\n\n\n", num_of_pr+num_of_sr);
  157.     }
  158. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement