Поразрядная цифровая сортировка

@Alex Gor · Регистрация: 03.11.2017

Студворк — интернет-сервис помощи студентам

Не пойму, как правильно исправить ошибки (С++ учу недавно, толком не разобралась)
Подскажите, пожалуйста
Срочно!

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <locale.h>
using namespace std;
 
int StatMas();
int DinMas ();
int Sort(int mas);
int Digit(int v, int n);
 
int main()
{
    system("cls");
    setlocale (LC_ALL, "Russian");
    int num;
    cout<<"Выберите вид массива:\n";
    cout<<"1. Статический массив\n";
    cout<<"2. Динамический массив\n";
    cout<<"3. Закрыть программу\n";
    cin>>num;
    switch (num)
    {
    case 1:
        
        StatMas();
        
        
        break;
    case 2:
        
        DinMas();
        
        break;
    case 3:
        exit (0);
    default:
        cout<<"Некорректный символ!\n";
        main();
    }
    main();
    return 0;
}
 
int StatMas()
{
    system("cls");
    unsigned int start_time1 = clock();
    int const N=10;
    int a[N];
    srand(time(NULL));
    cout<<"Элементы масива сгенерируем случайным образом:\n";
    for (int i = 0; i < N; i++)
    {
        a[i]=rand()%50;
        cout<<a[i]<<" ";
    }
    cout<<endl<<endl;
    cout<<"Выполним поразрядную цифровую сортировку массива:\n";
    Sort(a[N]);
    unsigned int end_time1 = clock();
    unsigned int time1 = end_time1 - start_time1;
    cout << "Время выполнения: " << time1 << "млс\n";
    system("pause");
    return 0;
}
 
int DinMas()
{
    system ("cls");
    unsigned int start_time2 = clock();
    int s;
    srand(time(NULL));
    cout<<"Введите размер массива: ";
    cin>>s;
    int *array=new int[s];
    cout<<"Элементы массива сгенерируем случайным образом:\n";
    for (int i = 0; i < s; i++)
    {
        array[i]=rand()%50;
        cout<<array[i]<<" ";
    }
    cout<<endl<<endl;
    cout<<"Выполним поразрядную цифровую сортировку массива:\n";
    Sort(array[s]);
    unsigned int end_time2 = clock();
    unsigned int time2 = end_time2 - start_time2;
    cout << "Время выполнения: " << time2 << "млс\n";
    system("pause");
    return 0;
}
 
int Sort(int a[])
{
    int D = 2;
    int P = 10;
    int b[] = new int[P];
    int i, j, k, m, x;
    int N;
    for (m = 0; m < D; m++)
    {
        for (i = 0; i < P; i++)
        {
            b[i] = 0;
        }
        for (i = 0; i < N; i++)
        {
            k = Digit(a[i], m);
            x = a[i];
            for (j = i; j > b[k] + 1; j--)
            {
                a[j] = a[j - 1];
            }
            a[b[k]] = x;
            for (j = k; j < P; j++)
            {
                b[j] = b[j] + 1;
            }
        }
    }
    return 0;
}
 
 
int Digit(int v, int n)
{
    int D = 2;
    int P = 10;
    for (; n > 0; n--)
    {
        v = v / P;
    }
    return (v%P);
}

Добавлено через 1 минуту
1>------ Сборка начата: проект: Задание 3, Конфигурация: Debug Win32 ------
1>Задание 3.cpp
1>d:\2 курс\алгоритмы проги\задание 3\задание 3\задание 3.cpp(52): warning C4244: аргумент: преобразование "time_t" в "unsigned int", возможна потеря данных
1>d:\2 курс\алгоритмы проги\задание 3\задание 3\задание 3.cpp(74): warning C4244: аргумент: преобразование "time_t" в "unsigned int", возможна потеря данных
1>d:\2 курс\алгоритмы проги\задание 3\задание 3\задание 3.cpp(98): error C2440: инициализация: невозможно преобразовать "int *" в "int []"
1>d:\2 курс\алгоритмы проги\задание 3\задание 3\задание 3.cpp(98): note: Не существует преобразований в типы массивов, хотя существуют преобразования в ссылки или указатели на массивы
1>Сборка проекта "Задание 3.vcxproj" завершена с ошибкой.
========== Сборка: успешно: 0, с ошибками: 1, без изменений: 0, пропущено: 0 ==========

@Alex Gor · 26.10.2018, 12:09 **[ТС]**

Кто- Кто-нибудь поможет хотябы алгоритм сортировки исправить? С остальным я разобралась

@nmcf · 26.10.2018, 15:21

C++
1
int b* = new int[P];

И в конце удалить.

@Alex Gor · 26.10.2018, 15:32 **[ТС]**

Вот что у меня сейчас:

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <locale.h>
using namespace std;
 
int StatMas();
int DinMas ();
int Sort(int a[], int N);
int Digit(int v, int n);
 
int main()
{
    system("cls");
    setlocale (LC_ALL, "Russian");
    int num;
    cout<<"Выберите вид массива:\n";
    cout<<"1. Статический массив\n";
    cout<<"2. Динамический массив\n";
    cout<<"3. Закрыть программу\n";
    cin>>num;
    switch (num)
    {
    case 1:
        
        StatMas();
        
        
        break;
    case 2:
        
        DinMas();
        
        break;
    case 3:
        exit (0);
    default:
        cout<<"Некорректный символ!\n";
        main();
    }
    main();
    return 0;
}
 
int StatMas()
{
    system("cls");
    unsigned int start_time1 = clock();
    int const m=10;
    int arr[m];
    srand(time(NULL));
    cout<<"Элементы масива сгенерируем случайным образом:\n";
    for (int i = 0; i < m; i++)
    {
        arr[i]=rand()%50;
        cout<<arr[i]<<" ";
    }
    cout<<endl<<endl;
    cout<<"Выполним поразрядную цифровую сортировку массива:\n";
    Sort(arr, m);
    for (int i = 0; i < m; i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl<<endl;
    unsigned int end_time1 = clock();
    unsigned int time1 = end_time1 - start_time1;
    cout << "Время выполнения: " << time1 << "млс\n";
    system("pause");
    return 0;
}
 
int DinMas()
{
    system("cls");
    unsigned int start_time2 = clock();
    int s;
    srand(time(NULL));
    cout << "Введите размер массива: ";
    cin >> s;
    int *array = new int[s];
    cout << "Элементы массива сгенерируем случайным образом:\n";
    for (int i = 0; i < s; i++)
    {
        array[i] = rand() % 50;
        cout << array[i] << " ";
    }
    cout << endl << endl;
    cout << "Выполним поразрядную цифровую сортировку массива:\n";
    Sort(array, s);
    for (int i = 0; i < s; i++)
    {
        cout<<array[i]<<" ";
    }
    cout<<endl<<endl;
    unsigned int end_time2 = clock();
    unsigned int time2 = end_time2 - start_time2;
    cout << "Время выполнения: " << time2 << "млс\n";
    system("pause");
    return 0;
}
 
int Sort(int a[], int N)
{
    int D = 2;
    int P = 10;
    int *b = new int[P];
    int i, j, k, m, x;
    for (m = 0; m < D; m++)
    {
        for (i = 0; i < P; i++)
        {
            b[i] = 0;
        }
            for (i = 0; i < N; i++)
            {
                k = Digit(a[i], i);
                x = a[i];
                for (j = i; j > b[k] + 1; j--)
                {
                    a[j] = a[j - 1];
                }
                a[b[k]] = x;
                for (j = k; j < P; j++)
                {
                    b[j] = b[j] + 1;
                }
            }
        }
    return b[P];
}
 
 
int Digit(int v, int n)
{
    int D = 2;
    int P = 10;
    for (; n <0; n--)
    {
        v = v / P;
    }
    return (v%P);
}

Но выводит типа:
5 3 78 45 96 10 43 58- исходник
10 43 43 45 45 96 78 78 - отсортированный

Добавлено через 3 минуты
Вот что у меня сейчас:

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <locale.h>
using namespace std;
 
int StatMas();
int DinMas ();
int Sort(int a[], int N);
int Digit(int v, int n);
 
int main()
{
    system("cls");
    setlocale (LC_ALL, "Russian");
    int num;
    cout<<"Выберите вид массива:\n";
    cout<<"1. Статический массив\n";
    cout<<"2. Динамический массив\n";
    cout<<"3. Закрыть программу\n";
    cin>>num;
    switch (num)
    {
    case 1:
        
        StatMas();
        
        
        break;
    case 2:
        
        DinMas();
        
        break;
    case 3:
        exit (0);
    default:
        cout<<"Некорректный символ!\n";
        main();
    }
    main();
    return 0;
}
 
int StatMas()
{
    system("cls");
    unsigned int start_time1 = clock();
    int const m=10;
    int arr[m];
    srand(time(NULL));
    cout<<"Элементы масива сгенерируем случайным образом:\n";
    for (int i = 0; i < m; i++)
    {
        arr[i]=rand()%50;
        cout<<arr[i]<<" ";
    }
    cout<<endl<<endl;
    cout<<"Выполним поразрядную цифровую сортировку массива:\n";
    Sort(arr, m);
    for (int i = 0; i < m; i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl<<endl;
    unsigned int end_time1 = clock();
    unsigned int time1 = end_time1 - start_time1;
    cout << "Время выполнения: " << time1 << "млс\n";
    system("pause");
    return 0;
}
 
int DinMas()
{
    system("cls");
    unsigned int start_time2 = clock();
    int s;
    srand(time(NULL));
    cout << "Введите размер массива: ";
    cin >> s;
    int *array = new int[s];
    cout << "Элементы массива сгенерируем случайным образом:\n";
    for (int i = 0; i < s; i++)
    {
        array[i] = rand() % 50;
        cout << array[i] << " ";
    }
    cout << endl << endl;
    cout << "Выполним поразрядную цифровую сортировку массива:\n";
    Sort(array, s);
    for (int i = 0; i < s; i++)
    {
        cout<<array[i]<<" ";
    }
    cout<<endl<<endl;
    unsigned int end_time2 = clock();
    unsigned int time2 = end_time2 - start_time2;
    cout << "Время выполнения: " << time2 << "млс\n";
    system("pause");
    return 0;
}
 
int Sort(int a[], int N)
{
    int D = 2;
    int P = 10;
    int *b = new int[P];
    int i, j, k, m, x;
    for (m = 0; m < D; m++)
    {
        for (i = 0; i < P; i++)
        {
            b[i] = 0;
        }
            for (i = 0; i < N; i++)
            {
                k = Digit(a[i], i);
                x = a[i];
                for (j = i; j > b[k] + 1; j--)
                {
                    a[j] = a[j - 1];
                }
                a[b[k]] = x;
                for (j = k; j < P; j++)
                {
                    b[j] = b[j] + 1;
                }
            }
        }
    return b[P];
}
 
 
int Digit(int v, int n)
{
    int D = 2;
    int P = 10;
    for (; n <0; n--)
    {
        v = v / P;
    }
    return (v%P);
}

Но выводит типа:
5 3 78 45 96 10 43 58- исходник
10 43 43 45 45 96 78 78 - отсортированный

@sty4ent · 26.10.2018, 17:32

Сообщение от Alex Gor

Но выводит типа:
5 3 78 45 96 10 43 58- исходник
10 43 43 45 45 96 78 78 - отсортированный

А причём тут C++? Предполагаю, что причина в непонимании алгоритма.

@Alex Gor · 26.10.2018, 17:34 **[ТС]**

Есть немного. Может объясните, если не сложно или подправить код?
Скоро сдача, уже мозг закипает

@sty4ent · 26.10.2018, 17:42

В интернете может поискать? Вот пример:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// взято отсюда https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Сортировка/Поразрядная и немного изменено
void Sort(int* begin, int size, unsigned bit = 0x80000000)
{
    if (!bit)
        return;
 
    if (size < 2)
        return;
 
    int last = 0;
    for (int i = 0; i < size; i++)
    {
        if ((begin[i] & bit) == 0)
            swap(begin[last++], begin[i]);
    }
 
    Sort(begin,      last,      bit >> 1);
    Sort(begin+last, size-last, bit >> 1);
}

Проверку функции поручаю вам

.

@Alex Gor · 26.10.2018, 18:41 **[ТС]**

Мне нужна сортировка именно с вызовом функции Digital
Весь инет облазила, все не то, все не так)

Добавлено через 13 минут
Я не могу понять, какое значение в функции Sort нужно возвращать. По логике, мне нужно вернуть новый отсортированный массив, а все равно получается непонятно что

@sty4ent · 26.10.2018, 18:48

Не надо массив возвращать, в исходном массиве после выполнения функции будет результат.

@Alex Gor · 26.10.2018, 18:50 **[ТС]**

Ф. Sort в любом случае должна возвращать какое-то значение. Только вот КАКОЕ..

@sty4ent · 26.10.2018, 19:15

Сообщение от Alex Gor

Ф. Sort в любом случае должна возвращать какое-то значение.

Зачем? Сделай массив, вызови Sort и посмотри потом на начальный массив.

@Alex Gor · 26.10.2018, 19:24 **[ТС]**

" error C4716: Sort: должна возвращать значение"

@sty4ent · 26.10.2018, 20:39

Сообщение от Alex Gor

" error C4716: Sort: должна возвращать значение"

напиши void и не будет должна (смотреть пример выше)

@Alex Gor · 26.10.2018, 20:48 **[ТС]**

Все равно фигня
Что-то неправильно с ф-ми Sort и Digital, но не могу понять, чтоо

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@Alex Gor 0 / 0 / 0 Регистрация: 03.11.2017 Сообщений: 39
	26.10.2018, 12:09 [ТС]
	Кто- Кто-нибудь поможет хотябы алгоритм сортировки исправить? С остальным я разобралась 0

@Alex Gor 0 / 0 / 0 Регистрация: 03.11.2017 Сообщений: 39
	26.10.2018, 17:34 [ТС]
	Есть немного. Может объясните, если не сложно или подправить код? Скоро сдача, уже мозг закипает 0

@Alex Gor 0 / 0 / 0 Регистрация: 03.11.2017 Сообщений: 39
	26.10.2018, 18:41 [ТС]
	Мне нужна сортировка именно с вызовом функции Digital Весь инет облазила, все не то, все не так) Добавлено через 13 минут Я не могу понять, какое значение в функции Sort нужно возвращать. По логике, мне нужно вернуть новый отсортированный массив, а все равно получается непонятно что 0

@sty4ent 44 / 20 / 14 Регистрация: 23.10.2018 Сообщений: 103
	26.10.2018, 18:48
	Не надо массив возвращать, в исходном массиве после выполнения функции будет результат. 0

@Alex Gor 0 / 0 / 0 Регистрация: 03.11.2017 Сообщений: 39
	26.10.2018, 18:50 [ТС]
	Ф. Sort в любом случае должна возвращать какое-то значение. Только вот КАКОЕ.. 0

@Alex Gor 0 / 0 / 0 Регистрация: 03.11.2017 Сообщений: 39
	26.10.2018, 19:24 [ТС]
	" error C4716: Sort: должна возвращать значение" 0

@Alex Gor 0 / 0 / 0 Регистрация: 03.11.2017 Сообщений: 39
	26.10.2018, 20:48 [ТС]
	Все равно фигня Что-то неправильно с ф-ми Sort и Digital, но не могу понять, чтоо 0