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

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

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

Переполнение стека при вызове рекурсивной функции
Вообщем есть у меня рекурсивный вызов функции, и как я понял у меня...

Использование рекурсивной функции для сортировки массива по возрастанию
Описать рекурсивную функцию сортировки по возрастанию массива с n целых чисел....

Переполнение стека
Привет народ. Такой вопрос: Если в общем виде: if (условие) double d else...

Переполнение стека
Добрый вечер! Я пытался решить следующую задачку: Петя и Вася часто играют...

Переполнение стека
Всем привет. Помогите, пожалуйста с решением одной проблемы. Мне нужно в...

Переполнение стека
Всем добрый вечер. Я создаю вектор, который имеет большой размер: порядка...

28
DrOffset
7518 / 4514 / 1097
Регистрация: 30.01.2014
Сообщений: 7,362
10.04.2014, 17:34 #21
taras atavin, то есть ты отрицаешь факт того, что быстрая сортировка может быть реализована через рекурсию?
0
d1skort
20 / 20 / 8
Регистрация: 10.02.2013
Сообщений: 75
10.04.2014, 17:37 #22
Цитата Сообщение от taras atavin Посмотреть сообщение
Там массив делится на подмассивы, но задача не делится на аналогичные для подмассивов и вообще вся сортировка построена на перестановках элементов только между подмассивами, а не внутри.
А сортировка слиянием?
0
TenGen
Будущее рядом
99 / 97 / 48
Регистрация: 06.03.2014
Сообщений: 342
10.04.2014, 17:40 #23
Скорее всего уже говорили, но в таких случаях лучше передавать указатели на массив.
0
NEvOl
19 / 18 / 1
Регистрация: 13.08.2012
Сообщений: 734
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);
 
}
0
taras atavin
4204 / 1763 / 212
Регистрация: 24.11.2009
Сообщений: 27,565
11.04.2014, 05:36 #25
Большой массив нельзя отсортировать быстро, в худшем случае он сортируется очень медленно, в лучшем просто медленно. Это неизбежно от ресурсоёмкости самой задачи и любой рост быстродействия только только отодвинет планку размера массива.
0
d1skort
20 / 20 / 8
Регистрация: 10.02.2013
Сообщений: 75
11.04.2014, 09:35 #26
Цитата Сообщение от NEvOl Посмотреть сообщение
переделал алгоритм в итеративный вариант, но все равно медленно как-то, может кто-нибудь подскажет что не так ?
А какое у тебя максимальное значение в массиве? Если оно достаточно мало (относительно количеству элементов массива), то можно отсортировать за линейное время сортировкой подсчетом.
0
Voivoid
708 / 280 / 15
Регистрация: 31.03.2013
Сообщений: 1,339
11.04.2014, 10:24 #27
А разве сортировка вообще рекурсивна?
Лол, а как по-твоему пишутся сортировки в функциональных языках?

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

Добавлено через 5 минут
Кроме того, простота разработки - вообще не фактор качества оси. Как раз с позиции разработчика приложений я и предпочитаю винду, но ось должна быть простой не для разработчика чего бы то ни было, а для пользователя, тем более если она не позиционируется на рынке, подобно фотону, как ось только для профессионалов.
0
NEvOl
19 / 18 / 1
Регистрация: 13.08.2012
Сообщений: 734
11.04.2014, 14:30  [ТС] #29
d1skort, значения в массиве произвольные, ну в разумных приделах к примеру [-1000; 1000]
0
11.04.2014, 14:30
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.04.2014, 14:30
Привет! Вот еще темы с решениями:

Переполнение стека
Доброго времени суток, форумчане! Начинаю плюсы осваивать, подскажите,...

Переполнение стека
Есть функция f(): void f() { //... std::make_pair&lt;size_t, size_t&gt;...

Переполнение стека
Хочу полюбопытствовать. Вычитал недавно, что на стек выделяется ограниченная...

Написать функции рекурсивной и не рекурсивной реализации алгоритма Евклида нахождения наибольшего общего делителя (НОД) двух натуральных чисел
Написать функции рекурсивной и не рекурсивной реализации алгоритма Евклида ...


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

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

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