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

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

Восстановить пароль Регистрация
 
 
NEvOl
12 / 11 / 0
Регистрация: 13.08.2012
Сообщений: 616
09.04.2014, 23:04     Переполнение стека в рекурсивной функции сортировки большого массива #1
Написал рекурсивную функцию сортировки массива, с массивами небольших размеров все работает как надо, а вот если сортирую побоьлше (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);
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
DrOffset
6425 / 3799 / 880
Регистрация: 30.01.2014
Сообщений: 6,592
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
96 / 94 / 20
Регистрация: 06.03.2014
Сообщений: 342
10.04.2014, 17:40     Переполнение стека в рекурсивной функции сортировки большого массива #23
Скорее всего уже говорили, но в таких случаях лучше передавать указатели на массив.
NEvOl
12 / 11 / 0
Регистрация: 13.08.2012
Сообщений: 616
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
580 / 256 / 12
Регистрация: 31.03.2013
Сообщений: 1,284
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++

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

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

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