Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
OVERPOWER8
19 / 19 / 2
Регистрация: 29.11.2009
Сообщений: 224
#1

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

22.01.2010, 12:25. Просмотров 680. Ответов 8
Метки нет (Все метки)

Вот только не надо никаких анализов, вопросов, и т. д.
Конкретно мой пример.

Программа на некоторых компиляторах не компилируется. Причем проблема вовсе не в переполнении стека - присвойте 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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.01.2010, 12:25
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Как исправить данный код сортировки? (C++):

Исправить код сортировки выбором
Реализуйте алгоритм на языке Си, добавив в программу подсчет количества...

Исправить код сортировки массива
Добрый вечер) Обращаюсь к вам за помощью. Есть программа, которая должна...

Исправить код, реализующий алгоритм сортировки
Доброе утро. Сделал попытку реализовать функцию сортировки простым двухпутевым...

Исправить код для сортировки двумерного массива
Здравствуйте! Укажите пожалуйста на мою ошибку. Нужно через быструю сортировку...

Как можно оптимизировать данный код?
И... Ещё один вопрос: Дан участок кода С++: #include &lt;iostream&gt;...

Как еще короче записать данный код?
#include &lt;ios&gt; main() { system(&quot;for /f \&quot;tokens=1,2,3\&quot; %a in (input.txt)...

8
zim22
depict1
276 / 141 / 4
Регистрация: 11.07.2009
Сообщений: 606
22.01.2010, 12:58 #2
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
int array[SIZE];
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
const int SIZE=2000000;
как-то неправильно на стеке создавать такую громадину.
лучше динамическую память используй ну или std::vector
1
OVERPOWER8
19 / 19 / 2
Регистрация: 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;
}
0
zim22
depict1
276 / 141 / 4
Регистрация: 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
0
OVERPOWER8
19 / 19 / 2
Регистрация: 29.11.2009
Сообщений: 224
22.01.2010, 14:26  [ТС] #5
>> zim22

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

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

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

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

надо nothrow добавить.
0
zim22
depict1
276 / 141 / 4
Регистрация: 11.07.2009
Сообщений: 606
22.01.2010, 16:42 #8
Цитата Сообщение от OVERPOWER8 Посмотреть сообщение
надо nothrow добавить.
не надо. надо просто ловить исключение.
0
Evg
Эксперт CАвтор FAQ
18938 / 6899 / 513
Регистрация: 30.03.2009
Сообщений: 19,437
Записей в блоге: 30
22.01.2010, 17:10 #9
Я же писал причину
http://www.cyberforum.ru/cpp/thread88396-page2.html#post496717
0
22.01.2010, 17:10
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.01.2010, 17:10
Привет! Вот еще темы с решениями:

Как правильно прописать данный код программы?
#include &lt;iostream&gt; #include &lt;clocale&gt; #include &lt;cmath&gt; #include &lt;cstdlib&gt;...

Как написать данный код средствами ООП?
Всем привет! Недавно начал изучать с++ и написал простенькую задачу: ...

Как работает данный код? И почему не компилируется?
Обьясните пожалуйста как работает данный код, и скажите почему он не...

Как работает данный код и почему такой вывод?
Написал какой-то код, выводит в дебаге 5 в релизе 0 #include &lt;iostream&gt;...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru