Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 74, средняя оценка - 4.81
Shevva
17 / 17 / 0
Регистрация: 13.09.2009
Сообщений: 140
#1

Поразрядная сортировка - C++

09.01.2010, 17:37. Просмотров 9790. Ответов 3
Метки нет (Все метки)

Необходимо реализовать метод поразрядной сортировки. Нужно отсортировать последовательность так, что бы она была отсортирована в порядке спадания величины. Вот в чём эта сортировка заключается: Пусть у нас есть есть последовательность двоцифровых натуральных чисел. Заведём 10 очередей, в которые будем складывать наши числа независимо от того, какая в них последняя цифра. Дальше соберём все со всех очередей в одну последовательность . Полученную таким образом последовательность ещё раз раскладываем по очередям, но теперь уже зависимо от того, какая у них предпоследняя цифра. Если теперь собрать все числа с очередей на выход, то последовательность окажется отсортированной в порядке возрастания.

Добавлено через 20 часов 18 минут
Отзовитесь кто-то!!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.01.2010, 17:37     Поразрядная сортировка
Посмотрите здесь:

C++ Поразрядная сортировка MSD
Трехпутевая поразрядная быстрая сортировка C++
C++ Поразрядная сортировка символьных массивов
Поразрядная сортировка и его недостатки C++
Поразрядная сортировка массива C++
Поразрядная операция & C++
C++ Поразрядная конъюнкция / Дизъюнкция / Исключающие, (&), (|), (^)
C++ Поразрядная сортировка
Поразрядная сортировка C++
C++ Поразрядная сортировка
C++ Сортировка Шелла. Написал программу, не могу понять, почему сортировка не выполняется
Обменная поразрядная сортировка масива C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
13.01.2010, 16:29     Поразрядная сортировка #2
Вариант:
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
#include "iostream"
using namespace std;
const int n=10, col_razr=3;
int velich_razr(int chislo,int razr)
{
    while(razr>1)
    {
        chislo/=10;
        razr--;
    }
    return chislo%10;
}
 
void sort_razr(int dop_mas[n][n], int mas[n], int razr)
{
    int mas_col[n], i,j, temp=0;
    for(i=0; i<n; i++)
        mas_col[i]=0;
    for(i=0; i<n; i++)
    {
        int a=velich_razr(mas[i], razr);
        dop_mas[mas_col[a]][a]=mas[i];
        mas_col[a]++;
    }
    for(i=0; i<n; i++)
    {
        for(j=0; j<mas_col[i]; j++)
        {
            mas[temp]=dop_mas[j][i];
            temp++;
        }
    }
}
 
int main()
{
    
    int razr, i;
    int mas[n]={623, 543, 120, 935, 423, 610, 732, 126, 784, 648};
    int dop_mas[n][n];
    for(razr=1; razr<4; razr++)
        sort_razr(dop_mas, mas, razr);
    for(i=0; i<n; i++)
        cout<<mas[i]<<endl;
    return 0;
}
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.01.2010, 10:26     Поразрядная сортировка #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
#include "iostream"
#include "windows.h"
using namespace std;
int n, col_razr=0;
int max_razr(int chislo)
{
    int max=0;
    while(chislo>1)
        {
                chislo/=10;
                max++;
        }
    return max;
}
 
int velich_razr(int chislo,int razr)
{
        while(razr>1)
        {
                chislo/=10;
                razr--;
        }
        return chislo%10;
}
 
void sort_razr(int **dop_mas, int *mas, int razr)
{
        int *mas_col, i,j, temp=0;
        mas_col=new int[n];
        for(i=0; i<n; i++)
                mas_col[i]=0;
        for(i=0; i<n; i++)
        {
                int a=velich_razr(mas[i], razr);
                dop_mas[mas_col[a]][a]=mas[i];
                mas_col[a]++;
        }
        for(i=0; i<n; i++)
        {
                for(j=0; j<mas_col[i]; j++)
                {
                        mas[temp]=dop_mas[j][i];
                        temp++;
                }
        }
}
 
int main()
{
        SetConsoleCP(1251);
        SetConsoleOutputCP(1251);
        int razr, i, *mas, **dop_mas;
        cout<<"Введите размер последовательности: "<< endl;
        cin>>n;
        mas=new int[n];
        cout<<"Введите элементы последовательности: "<< endl;
        for(i=0; i<n; i++)
        {
            cout<<"["<<i+1<<"]= ";
            cin>>mas[i];
        }
        dop_mas=new int*[n];
        for(i=0; i<n; i++)
        dop_mas[i]=new int[n];
        for(i=0; i<n; i++)
            if(col_razr<max_razr(mas[i]))
                col_razr=max_razr(mas[i]);
        for(razr=1; razr<=col_razr; razr++)
                sort_razr(dop_mas, mas, razr);
        for(i=0; i<n; i++)
                cout<<mas[i]<<endl;
        return 0;
}
sanyaok
0 / 0 / 0
Регистрация: 18.12.2011
Сообщений: 21
03.12.2012, 21:04     Поразрядная сортировка #4
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Кликните здесь для просмотра всего текста
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
#include "iostream"
#include "windows.h"
using namespace std;
int n, col_razr=0;
int max_razr(int chislo)
{
    int max=0;
    while(chislo>1)
        {
                chislo/=10;
                max++;
        }
    return max;
}
 
int velich_razr(int chislo,int razr)
{
        while(razr>1)
        {
                chislo/=10;
                razr--;
        }
        return chislo%10;
}
 
void sort_razr(int **dop_mas, int *mas, int razr)
{
        int *mas_col, i,j, temp=0;
        mas_col=new int[n];
        for(i=0; i<n; i++)
                mas_col[i]=0;
        for(i=0; i<n; i++)
        {
                int a=velich_razr(mas[i], razr);
                dop_mas[mas_col[a]][a]=mas[i];
                mas_col[a]++;
        }
        for(i=0; i<n; i++)
        {
                for(j=0; j<mas_col[i]; j++)
                {
                        mas[temp]=dop_mas[j][i];
                        temp++;
                }
        }
}
 
int main()
{
        SetConsoleCP(1251);
        SetConsoleOutputCP(1251);
        int razr, i, *mas, **dop_mas;
        cout<<"Введите размер последовательности: "<< endl;
        cin>>n;
        mas=new int[n];
        cout<<"Введите элементы последовательности: "<< endl;
        for(i=0; i<n; i++)
        {
            cout<<"["<<i+1<<"]= ";
            cin>>mas[i];
        }
        dop_mas=new int*[n];
        for(i=0; i<n; i++)
        dop_mas[i]=new int[n];
        for(i=0; i<n; i++)
            if(col_razr<max_razr(mas[i]))
                col_razr=max_razr(mas[i]);
        for(razr=1; razr<=col_razr; razr++)
                sort_razr(dop_mas, mas, razr);
        for(i=0; i<n; i++)
                cout<<mas[i]<<endl;
        return 0;
}
В вашем варианте сортировка не реализуется, если элементов меньше 10. Не могу найти это в коде.. Подскажите?
Yandex
Объявления
03.12.2012, 21:04     Поразрядная сортировка
Ответ Создать тему
Опции темы

Текущее время: 10:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru