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

Сортировка подсчетом - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.83
gogaby
1 / 1 / 0
Регистрация: 15.11.2011
Сообщений: 28
21.11.2011, 19:35     Сортировка подсчетом #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
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
#include "head.h"
void main()
{  
    setlocale(LC_ALL,".1251");
    int *x,in,i,n=0,max,min,temp;
    char c[256];
    double sign;
    cout<<"\tЭта программа сортирует массив с помощью метода подсчета\n";
    srand((unsigned int)time(NULL));
    cout<<"Выберите тип ввода:\n1.Из файла\n2.С консоли\nТип: ";
    cin>>in;
    while ((in!=1)&&(in!=2))
    {
        cout<<"Неверное значение! Введите тип ещё раз: ";
        cin>>in;
    }
    if (in==1)
    {  
        char* fileName = new char[10];
        char* buf_x = new char [50];
        x=new int [200];
        {
 
            ifstream* inp = new ifstream("input.txt");  
            if (!inp)
                cout << "Ошибка" << endl;
            else
            {
                while (!inp->eof())
                {
                    inp->getline(buf_x, 50, ' ');
                    x[n]=atoi(buf_x);
                    n++;
                }
            }
        }
    }
    else
    {
        cout<<"Введите размер массива:\t";
        cin>>c;                     
        n=atoi(c);
        for (i=0; i<strlen(c); i++)
        {
            if (c[i]<'0' || c[i]>'9' || c[0]=='0')
            {
                cout<<"Неверный размер массива! Введите еще раз:\n";
                cin>>c;
                n=atoi(c);
                i=0;
            }
        }
        x=(int*)malloc(n*sizeof(int));   
        char pol;
        cout<<"Использовать генератор случайных чисел [y/n]? ";
        cin>>pol;
        switch(pol)
        {
        case 'n':
            {
                cout<<"\nВведите элементы:\n";
                for(i=0; i<n; i++)
                    cin>>x[i];
                break;
            }
        case 'y':
            {       
                cout<<"Введите интервал [a,b]: ";
                cin>>min>>max;
                if (min>max)
                {
                    temp=min;
                    min=max;
                    max=temp;
                }
                cout<<"\nИсходная матрица:\n";
                for (i=0;i<n;i++) 
                {
                    x[i]=min+(rand()%(max-min+1));
                    cout<<x[i]<<" ";
                } 
                cout<<endl;
                break;
            }
        }
    }
    cout<<"Выберите тип сортировки:\n1. По убыванию\n2. По возрастанию\nТип: ";
    cin>>c;
    sign=atof(c);
    while ((sign!=1 && sign!=2) || strlen(c)!=1)          
    {
        cout<<"\nНеверный ввод! Выбирите тип сортировки ещё раз: ";
        cin>>c;
        sign=atof(c);
    }
    sign=(sign-1.5)*2;
    csort(x,n,sign);
    cout<<"Выберите тип вывода:\n1.В файл\n2.На экран\nТип: ";
    cin>>in;
    while ((in!=1)&&(in!=2))
    {
        cout<<"Неверное значение! Введите тип ещё раз: ";
        cin>>in;
    }
    if (in==2)
    { 
        cout<<"Результат:\n";
        for(i=0;i<n;i++)
            cout<<x[i]<<" ";
        cout<<endl;
    }
    else
    {
        ofstream of("output.txt");  
        for(i=0;i<n;i++)
            of<<x[i]<<" ";
        of.close();
    }
    delete []x;
}



Сама функция:
CSS
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
#include "head.h"
int csort (int mas[], int n, double sign) 
{
    int i,min, max,k,*c,*b,xn;
    min = max = mas[0];
    for(i = 1; i < n; i++) 
    {
        if (mas[i] < min) min = mas[i];
        if (mas[i] > max) max = mas[i];
    }
    k=max-min+1;
    c=(int*)malloc(k*sizeof(int));
    b=(int*)malloc(n*sizeof(int));
    for(i=0; i<k; i++) 
        c[i]=0;
    for(i=0; i<n; i++) 
        b[i]=0;
    for(i=0; i<n; i++) 
    {
        c[ mas[i] - min ]++;
    }
    for(i=1; i<k; i++) 
    {
        c[i]=c[i]+c[i-1];
    }
    for(i=0; i<n; i++) 
    {
        b[c[mas[i]-min]-1]=mas[i];
        c[mas[i]-min]--;
    }
    xn=n;
    if (sign==1) 
    {
        for(i = 0; i < n; i++) 
            mas[i]=b[i];
    }
    else 
    {
        for(i=0; i<n; i++) 
        {
            xn-=1;
            mas[i]=b[xn];
        }
    }
    free(b);
    free(c);
    return 0;
}

Нужно сделать пошаговый вывод результатов сортировки. Что вообще можно выводить при сортировке подсчетом?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.11.2011, 19:35     Сортировка подсчетом
Посмотрите здесь:

C++ Сортировка распределяющим подсчетом
C++ Сортировка подсчетом и LSD сортировка
C++ помогите с подсчетом букв.
сортировка подсчетом! C++
C++ Сортировка подсчетом
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
LEQADA
Мастер кустарных методов
 Аватар для LEQADA
227 / 222 / 9
Регистрация: 09.11.2010
Сообщений: 680
21.11.2011, 19:42     Сортировка подсчетом #2
Цитата Сообщение от gogaby Посмотреть сообщение
Что вообще можно выводить при сортировке подсчетом?
Сортируемый массив наверно?
gogaby
1 / 1 / 0
Регистрация: 15.11.2011
Сообщений: 28
21.11.2011, 19:46  [ТС]     Сортировка подсчетом #3
я понимаю, что массив. Просто сортировка подсчетом массив не изменяет вроде(
LEQADA
Мастер кустарных методов
 Аватар для LEQADA
227 / 222 / 9
Регистрация: 09.11.2010
Сообщений: 680
21.11.2011, 19:49     Сортировка подсчетом #4
gogaby, вас наверное просят выводить массив при каждом изменении. Т.е. поменяли два элемента местами - выводите на экран. И так при каждой итерации.
gogaby
1 / 1 / 0
Регистрация: 15.11.2011
Сообщений: 28
21.11.2011, 19:55  [ТС]     Сортировка подсчетом #5
Все дело в том, что сам массив не изменяется, а создается дополнительный, в который заносятся элементы первого. Вот описание сортировки:

Создать вспомогательный массив C[0..k - 1], состоящий из нулей, затем последовательно прочитать элементы входного массива A, для каждого A[i] увеличить C[A[i]] на единицу. Теперь достаточно пройти по массиву C, для каждого j \in \{0, ..., k - 1\} в массив A последовательно записать число j C[j] раз.

Я не знаю что с кодом делать, чтобы оно второй массив пошагово выводило((
LEQADA
Мастер кустарных методов
 Аватар для LEQADA
227 / 222 / 9
Регистрация: 09.11.2010
Сообщений: 680
21.11.2011, 20:08     Сортировка подсчетом #6
Цитата Сообщение от gogaby Посмотреть сообщение
Я не знаю что с кодом делать, чтобы оно второй массив пошагово выводило((
После ряда действий (прошёлся один раз по массиву) выводи массив на экран. Всё также как и с массивом А. Только массив А выводится один раз, а С будет выводится при каждой итерации.

Добавлено через 6 минут
Понапихай в каждый for вывод на экран. А там видно будет ))
Yandex
Объявления
21.11.2011, 20:08     Сортировка подсчетом
Ответ Создать тему
Опции темы

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