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

Как исправить данный код сортировки? - C++

Восстановить пароль Регистрация
 
OVERPOWER8
 Аватар для OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 12:25     Как исправить данный код сортировки? #1
Вот только не надо никаких анализов, вопросов, и т. д.
Конкретно мой пример.

Программа на некоторых компиляторах не компилируется. Причем проблема вовсе не в переполнении стека - присвойте SIZE любое другое значение.
Если знаете, как исправить, то, пожалуйста, предложите свое решение.

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
#include <iostream>
#include <stdlib.h>
using namespace std;
 
const int SIZE=2000000;
 
void sort(int arr[])
{
        int max=arr[0];
        
        int i;
        
        for(i=0; i<SIZE; i++)
                if(arr[i] > max)
                        max = arr[i];
        
        int* Sorted = new int[max+1];
        
        for(i=0; i<SIZE; i++)
                Sorted[arr[i]]+=1;
        
        int counter=0;
        
        for(i=0; i<=max; i++)
                while(Sorted[i])
                {
                        arr[counter++]=i;
                        Sorted[i]--;
                }
                
        delete [] Sorted;
}
 
int main()
{
        srand(time(0));
 
        int Max=2000000;
        
        int i, j;
        
        int array[SIZE];
        
        for(i=0; i<SIZE; i++)
                array[i]=rand()%Max+1;
                
        sort(array);
        
        cout << "Sorted!\n";
        
        /*
        for(i=0; i<SIZE; i++)
                cout << array[i] << " ";
        */
        
        return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.01.2010, 12:25     Как исправить данный код сортировки?
Посмотрите здесь:

C++ Обьясните пожайлуста как и что делает данный оператор в этом выражении fState [x][y] ^= 1;. Неполный код привожу ниже.
C++ Как отправлять данный файл на данный адрес электронной почты?
не могу разобраться как написать функцию сортировки и исправить функцию добавления в стек C++
Исправить код, реализующий алгоритм сортировки C++
C++ Исправить код для сортировки двумерного массива
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zim22
depict1
 Аватар для zim22
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
22.01.2010, 12:58     Как исправить данный код сортировки? #2
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
int array[SIZE];
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
const int SIZE=2000000;
как-то неправильно на стеке создавать такую громадину.
лучше динамическую память используй ну или std::vector
OVERPOWER8
 Аватар для OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 13:38  [ТС]     Как исправить данный код сортировки? #3
>> zim22

Спасибо, использование динамического массива исправило некоторые проблемы.
Если не сложно, то проверьте этот код на вашем компиляторе. А то мой G++ компилирует, и потом работает; а codepad.org выдает segmentation fault.

И почему-то мой компилятор при использовании элементов больше 1 000 000 000 тоже пишет ахинею какую-то:
Bash
1
2
3
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
Aborted
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
#include <iostream>
#include <stdlib.h>
#include <limits>
using namespace std;
 
const int SIZE=100000000;
 
void sort(int* arr)
{
    int max=arr[0];
    
    int i;
    
    for(i=0; i<SIZE; i++)
        if(arr[i] > max)
            max = arr[i];
    
    int* Sorted = new int[max+1];
    
    for(i=0; i<SIZE; i++)
        Sorted[arr[i]]+=1;
    
    int counter=0;
    
    for(i=0; i<=max; i++)
        while(Sorted[i])
        {
            arr[counter++]=i;
            Sorted[i]--;
        }
        
    delete [] Sorted;
}
 
int main()
{
        srand(time(0));
 
        int Max=2000000;
        
        int i, j;
        
        int* array = new int[SIZE];
        
        for(i=0; i<SIZE; i++)
                array[i]=rand()%Max+1;
                
        sort(array);
        
        cout << "Sorted!\n";
        
        /*
        for(i=0; i<SIZE; i++)
                cout << array[i] << " ";
        */
        
        delete [] array;
 
        return 0;
}
zim22
depict1
 Аватар для zim22
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
22.01.2010, 13:42     Как исправить данный код сортировки? #4
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
Если не сложно, то проверьте этот код на вашем компиляторе.
не вижу смысла проверять. код глючный и может работать на одном наборе данных и крэшиться на другом. напиши для него юнит-тесты.

Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
const int SIZE=100000000;
int i;
for(i=0; i<SIZE; i++)
для индексации массивов используй тип size_t вместо int. а то в int может не влезть такое гигантское значение.
***
в прочем, как и в size_t
OVERPOWER8
 Аватар для OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 14:26  [ТС]     Как исправить данный код сортировки? #5
>> zim22

Это почему же код глючный? У меня работает исправно.
Не вижу смысла использовать size_t, т. к:

numeric_limits<size_t>::max() = numeric_limits<unsigned int>::max();
zim22
depict1
 Аватар для zim22
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
22.01.2010, 14:35     Как исправить данный код сортировки? #6
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
И почему-то мой компилятор при использовании элементов больше 1 000 000 000 тоже пишет ахинею какую-то:
это иксэпшн. система не смогла выделить столько-то памяти.
OVERPOWER8
 Аватар для OVERPOWER8
19 / 19 / 1
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 15:51  [ТС]     Как исправить данный код сортировки? #7
>> zim22

это иксэпшн. система не смогла выделить столько-то памяти.
Да, я неправильно память рассчитал.

При 300 000 000 элементах используется 1.0 ... 1.1 Гб оперативки.

надо nothrow добавить.
zim22
depict1
 Аватар для zim22
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
22.01.2010, 16:42     Как исправить данный код сортировки? #8
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
надо nothrow добавить.
не надо. надо просто ловить исключение.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.01.2010, 17:10     Как исправить данный код сортировки?
Еще ссылки по теме:

C++ Как оптимизировать данный код игры крестики нолики?
Как правильно прописать данный код программы? C++

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

Или воспользуйтесь поиском по форуму:
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16824 / 5245 / 320
Регистрация: 30.03.2009
Сообщений: 14,125
Записей в блоге: 26
22.01.2010, 17:10     Как исправить данный код сортировки? #9
Я же писал причину
http://www.cyberforum.ru/cpp/thread8...tml#post496717
Yandex
Объявления
22.01.2010, 17:10     Как исправить данный код сортировки?
Ответ Создать тему
Опции темы

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