Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //****************************************************//
- // Лабораторная работа №1 //
- // по курсу "Модели и структуры данных" //
- // //
- // Исследование простых алгоритмов сортировки //
- // Вариант 24 //
- // //
- // группа 525a Даниил Артемьев //
- //****************************************************//
- #include<stdio.h>
- #include<stdlib.h>
- #include<time.h>
- #include <iostream>
- #include <cassert>
- #include <vector>
- #include <iostream>
- using namespace std;
- int Number_of_Elements, num_of_sr = 0, num_of_pr = 0;
- int mas[100];
- double mas_1[100];
- void show(double mas_1[100]) {
- for (int i = 0; i<Number_of_Elements; i++)
- printf(" %f ", mas_1[i]);
- printf("\n");
- }
- static void BucketSort(int* data, int count) {
- int minValue = data[0];
- int maxValue = data[0];
- for (int i = 1; i < count; i++)
- {
- num_of_pr++;
- num_of_sr++;
- if (data[i] > maxValue)
- maxValue = data[i];
- if (data[i] < minValue)
- minValue = data[i];
- }
- int bucketLength = maxValue - minValue + 1;
- num_of_pr++;
- vector<int>* bucket = new vector<int>[bucketLength];
- for (int i = 0; i < bucketLength; i++)
- {
- num_of_pr++;
- bucket[i] = vector<int>();
- }
- for (int i = 0; i < count; i++)
- {
- num_of_pr++;
- bucket[data[i] - minValue].push_back(data[i]);
- }
- int k = 0;
- for (int i = 0; i < bucketLength; i++)
- {
- int bucketSize = bucket[i].size();
- num_of_pr++;
- if (bucketSize > 0)
- {
- num_of_sr++;
- for (int j = 0; j < bucketSize; j++)
- {
- num_of_pr++;
- data[k] = bucket[i][j];
- k++;
- }
- }
- }
- }
- void counting_sort(int* vec, int len, int min, int max)
- {
- int * cnt = new int[max - min + 1];
- for (int i = min; i <= max; ++i) {
- cnt[i - min] = 0;
- num_of_pr ++ ;
- }
- for (int i = 0; i < len; ++i) {
- ++cnt[vec[i] - min];
- num_of_pr++;
- }
- for (int i = min; i <= max; ++i) {
- for (int j = cnt[i - min]; j--;) {
- num_of_sr++;
- *vec++ = i;
- num_of_pr++;
- }
- }
- delete[] cnt;
- }
- int main()
- {
- int key, min_value = 0, max_value = 0;
- for (;;) {
- int key, min_value = 0, max_value = 0;
- printf("Enter the number of elements (<100): "); //вводколичестваэлементовмассива
- scanf_s("%i", &Number_of_Elements);
- min_value = 0;
- max_value = 100;
- //менювыборатипаупорядоченостимассива
- printf("Choose the type of mas:\n1.min-max\n2.max-min\n3.not sort\n");
- scanf_s("%i", &key);
- srand(time_t(0));
- //массив с равноменро распределенными случайными числами
- if (key == 3)
- for (int i = 0; i<Number_of_Elements; i++)
- mas[i] = min_value + rand() % (max_value - min_value);
- //массив упорядочен по убыванию
- if (key == 2) {
- mas[0] = max_value;
- for (int i = 1; i<Number_of_Elements; i++)
- mas[i] = mas[i - 1] - 1;
- }
- //массив упорядочен по возрастанию
- if (key == 1) {
- mas[0] = min_value;
- for (int i = 1; i<Number_of_Elements; i++)
- mas[i] = mas[i - 1] + 1;
- }
- for (int i = 0; i < Number_of_Elements; i++) {
- mas_1[i] = static_cast<double>(mas[i]) / 1;
- }
- show(mas_1);
- //менявыборатипасортировки
- printf("Choose the way for sorting:\n 1 counting sort\n 2 bucket sort \n");
- scanf_s("%i", &key);
- //выбор сортировки методом пузырька
- if (key == 1) {
- counting_sort(mas, Number_of_Elements, min_value, max_value);
- //выбор сортировки простым выбором
- }
- if (key == 2) {
- BucketSort(mas, Number_of_Elements);
- }
- for (int i = 0; i < Number_of_Elements; i++) {
- mas_1[i] = static_cast<double>(mas[i]) / 1;
- }
- show(mas_1);
- printf("Number of comparison == %i\n______________________________\n", num_of_sr);
- printf("Number of assignment == %i\n______________________________\n", num_of_pr);
- printf(" Sum == %i\n\n\n", num_of_pr+num_of_sr);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement