Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
0 / 0 / 0
Регистрация: 20.11.2015
Сообщений: 60
1

Где правильно ставить счетчики сравнений и перестановок, и как считать сложность этих алгоритмов?

15.03.2017, 23:54. Показов 547. Ответов 1
Метки нет (Все метки)

написал код двух сортировок, но не уверен, что правильно проставлены счетчики.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <ctime>
#include <conio.h>
using namespace std;
void vstavki(double*, int);
void vibor(double*, int);
 
int main() {
    srand(time(0));
    const int size = 60; 
    double mass[size];
     cout << "extended array: \n";
        for (int i = 0; i < size; i++)
            {
                mass[i] = (rand()%500) / 10.0;
                cout << mass[i] << " ";
            }
        cout << endl;
        vstavki(mass, size);
        cout << endl;
        cout << endl;
        vibor(mass, size);
        _getch();
    return 0;
}
 
void vstavki(double *array, int count)
{
    double temp;
    int iter,p;
    int perestanovki=0, looks=0;
    cout << "sorted array: \n";
    for ( p = 0; p < count; p++)
    {
        temp = array[p];
        iter = p - 1;
        looks++;
        while (iter >= 0 && array[iter] > temp)
        {
            array[iter + 1] = array[iter];
            array[iter] = temp;
            iter--;
            perestanovki++;
        }
    }
    for (p = 0; p < count; p++)
    {
        cout << array[p] << " ";
    }
    cout << "\n" << "perestanovki: " << perestanovki << "\n";
    cout << "prosmotri: " << looks << "\n";
}
 
void vibor(double *array, int count)
{
    int perestanovki = 0, looks = 0;
    cout << "sorted viborom array: \n";
    for (int repeat_counter = 0; repeat_counter < count; repeat_counter++)
    {
        double temp = array[0]; 
        for (int element_counter = repeat_counter + 1; element_counter < count; element_counter++)
        {
            looks++;
            if (array[repeat_counter] > array[element_counter])
            {
                temp = array[repeat_counter];
                array[repeat_counter] = array[element_counter];
                array[element_counter] = temp;
                perestanovki++;
            }
        }
    }
 
    for (int repeat_counter = 0; repeat_counter < count; repeat_counter++)
    {
        cout << array[repeat_counter] << " ";
    }
 
    cout << "\n" << "perestanovki viborom: " << perestanovki << "\n";
    cout << "prosmotri viborom: " << looks << "\n";
}
+ как считать их сложность? то что нам рассказали на парах весьма туманно. из того что есть в интернете, их сложность О(n2) или О(n2/2)
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.03.2017, 23:54
Ответы с готовыми решениями:

Счетчики количества перестановок и сравнений Шейкерной сортировки
Помогите ввести счетчики перестановок и сравнений Закоментированный код по идее верен но c ним...

График зависимость количества перестановок и сравнений от размерности массива для алгоритмов сортировки
имеются массивы с размерностью от 1 до 20 с данными не отсортированными,частично...

Правильно подсчитать количество перестановок и сравнений в сортировках
Здравствуйте, помогите, пожалуйста, правильно расставить Changes (Перестановки) и Compares...

Как вычислить количество сравнений и перестановок?
Здравствуйте. У меня есть 2 сортировки &quot;Вставкой&quot; и Шейкером, как мне посчитать кол-во сравнений и...

1
7158 / 6133 / 2801
Регистрация: 14.04.2014
Сообщений: 26,455
16.03.2017, 00:00 2
Вроде правильно.
Сложность - это из математической теории.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.03.2017, 00:00

Как определить количество перестановок и сравнений
У меня есть алгоритм Quicksort как определить количество перестановок и сравнений?? #include...

Как найти в данной сортировке количество перестановок и сравнений?
void quicksort(int *mas, int first, int last) { int mid, count, m=0; int f=first, l=last;...

Как определить количество перестановок и сравнений в выборочной сортировке
void choicesSort(int* Array, int length_array) { for (int repeat_counter(0); repeat_counter...

Как найти в этой сортировке количество перестановок и сравнений?
Как найти в этой сортировке количество перестановок и сравнений? void InsertSort(int *mas, int...

Как определить количество сравнений и перестановок в быстрой сортировке массива
Пробовал сделать счётчики, но они выводили кол-ва для сортировке всех подмассивов, а как вывести...

Стоит ли ставить счетчики
Скажите обязательно при регистрации в HotLog,Openstat ставить на сайт обратные кнопки?


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru