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

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

Войти
Регистрация
Восстановить пароль
 
 
NEvOl
13 / 12 / 0
Регистрация: 13.08.2012
Сообщений: 667
#1

Переполнение стека в рекурсивной функции сортировки большого массива - C++

09.04.2014, 23:04. Просмотров 816. Ответов 28
Метки нет (Все метки)

Написал рекурсивную функцию сортировки массива, с массивами небольших размеров все работает как надо, а вот если сортирую побоьлше (60000 элементов) то выскакиевает исключение
Unhandled exception at 0x01017A2A in Filtering.exe: 0xC00000FD: Stack overflow (parameters: 0x00000001, 0x00292FFC).
подскажите пожалуйста что не так, а то первый раз сталкиваюсь с этим, вот код функции:
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
void Sort(photon *p, int b, int e)
{
    int ind = p[e].pos.x;
    int sI = e;
    int j = e-1;
    bool s(0);
 
    for(int i = b; i < e; i++)
    {
        if(p[i].pos.x >= ind)
        {
            while(p[j].pos.x >= ind && j > i)
            {
                j--;
            }
            if(j > i)
            {
                photon a = p[i];
                p[i] = p[j];
                p[j] = a;
                sI = i+1;
            }
        }
    }
 
    for(int i = b; i < e; i++)
    {
        if(p[i].pos.x >= ind)
        {
            photon a = p[i];
            p[i] = p[e];
            p[e] = a;
            sI = i;
            break;
        }
    }
 
    if(abs(b-(sI-1)) > 1)
        Sort(p, b, sI-1);
 
    if(abs((sI+1)-e) > 1)
            Sort(p, sI+1, e);
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.04.2014, 23:04     Переполнение стека в рекурсивной функции сортировки большого массива
Посмотрите здесь:

Переполнение стека C++
C++ Написать функции рекурсивной и не рекурсивной реализации алгоритма Евклида нахождения наибольшего общего делителя (НОД) двух натуральных чисел
Рекурсия - переполнение стека C++
Переполнение стека C++
C++ Переполнение стека
Использование рекурсивной функции для сортировки массива по возрастанию C++
C++ Произведение элементов одномерного массива с использованием рекурсивной функции
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
DrOffset
6820 / 4031 / 924
Регистрация: 30.01.2014
Сообщений: 6,847
10.04.2014, 17:34     Переполнение стека в рекурсивной функции сортировки большого массива #21
taras atavin, то есть ты отрицаешь факт того, что быстрая сортировка может быть реализована через рекурсию?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
d1skort
20 / 20 / 0
Регистрация: 10.02.2013
Сообщений: 75
10.04.2014, 17:37     Переполнение стека в рекурсивной функции сортировки большого массива #22
Цитата Сообщение от taras atavin Посмотреть сообщение
Там массив делится на подмассивы, но задача не делится на аналогичные для подмассивов и вообще вся сортировка построена на перестановках элементов только между подмассивами, а не внутри.
А сортировка слиянием?
TenGen
Будущее рядом
 Аватар для TenGen
97 / 95 / 20
Регистрация: 06.03.2014
Сообщений: 342
10.04.2014, 17:40     Переполнение стека в рекурсивной функции сортировки большого массива #23
Скорее всего уже говорили, но в таких случаях лучше передавать указатели на массив.
NEvOl
13 / 12 / 0
Регистрация: 13.08.2012
Сообщений: 667
11.04.2014, 00:32  [ТС]     Переполнение стека в рекурсивной функции сортировки большого массива #24
переделал алгоритм в итеративный вариант, но все равно медленно как-то, может кто-нибудь подскажет что не так ?
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
void Sort(photon *p, int b, int e)
{
    vector<XMFLOAT2> stack;
    int ind = p[e].pos.z;
    int sI = e;
    int j = e-1;
    bool s(0);
 
    do
    {
        for(int i = b; i < e; i++)
        {
            j = e-1;
            ind = p[e].pos.z;
            if(p[i].pos.z >= ind)
            {
                while(p[j].pos.z >= ind && j > i)
                {
                    j--;
                }
                if(j > i)
                {
                    photon a = p[i];
                    p[i] = p[j];
                    p[j] = a;
                    sI = i+1;
                }
                else
                    break;
            }
        }
        for(int i = b; i <= e; i++)
        {
            if(p[i].pos.z >= ind)
            {
                photon a = p[i];
                p[i] = p[e];
                p[e] = a;
                sI = i;
                if(e - i > 1)
                    stack.push_back(XMFLOAT2(sI+1, e));
                break;
            }
        }
 
        if(sI-b <= 1 && stack.size() > 0)
        {
            b = stack[stack.size()-1].x;
            e = stack[stack.size()-1].y;
            stack.pop_back();
            continue;
        }
 
        e = sI - 1;
 
 
    }while(e-b >= 1 || stack.size() != 0);
 
}
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
11.04.2014, 05:36     Переполнение стека в рекурсивной функции сортировки большого массива #25
Большой массив нельзя отсортировать быстро, в худшем случае он сортируется очень медленно, в лучшем просто медленно. Это неизбежно от ресурсоёмкости самой задачи и любой рост быстродействия только только отодвинет планку размера массива.
d1skort
20 / 20 / 0
Регистрация: 10.02.2013
Сообщений: 75
11.04.2014, 09:35     Переполнение стека в рекурсивной функции сортировки большого массива #26
Цитата Сообщение от NEvOl Посмотреть сообщение
переделал алгоритм в итеративный вариант, но все равно медленно как-то, может кто-нибудь подскажет что не так ?
А какое у тебя максимальное значение в массиве? Если оно достаточно мало (относительно количеству элементов массива), то можно отсортировать за линейное время сортировкой подсчетом.
Voivoid
 Аватар для Voivoid
667 / 270 / 12
Регистрация: 31.03.2013
Сообщений: 1,331
11.04.2014, 10:24     Переполнение стека в рекурсивной функции сортировки большого массива #27
А разве сортировка вообще рекурсивна?
Лол, а как по-твоему пишутся сортировки в функциональных языках?

А топикстартеру же можно дать совет использовать оптимизацию хвостовой рекурсии, современные компиляторы её поддерживают
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
11.04.2014, 12:01     Переполнение стека в рекурсивной функции сортировки большого массива #28
Цитата Сообщение от d1skort Посмотреть сообщение
А сортировка слиянием?
Ога. Вместо деления большого массива на маленькие рост подмассива, пока он не станет тождествен всему массиву. Ну очень рекурсивно. Ещё внешнюю сортировку вспомни, отчётливо воняющую итерациями через буфер.

Добавлено через 5 минут
Кроме того, простота разработки - вообще не фактор качества оси. Как раз с позиции разработчика приложений я и предпочитаю винду, но ось должна быть простой не для разработчика чего бы то ни было, а для пользователя, тем более если она не позиционируется на рынке, подобно фотону, как ось только для профессионалов.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.04.2014, 14:30     Переполнение стека в рекурсивной функции сортировки большого массива
Еще ссылки по теме:

Переполнение стека C++
C++ Переполнение стека
C++ Переполнение стека при вызове рекурсивной функции
Реализовать переполнение стека C++
C++ Переполнение стека

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

Или воспользуйтесь поиском по форуму:
NEvOl
13 / 12 / 0
Регистрация: 13.08.2012
Сообщений: 667
11.04.2014, 14:30  [ТС]     Переполнение стека в рекурсивной функции сортировки большого массива #29
d1skort, значения в массиве произвольные, ну в разумных приделах к примеру [-1000; 1000]
Yandex
Объявления
11.04.2014, 14:30     Переполнение стека в рекурсивной функции сортировки большого массива
Ответ Создать тему
Опции темы

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