С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

09.04.2014, 23:04. Просмотров 957. Ответов 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++):

Переполнение стека при вызове рекурсивной функции - C++
Вообщем есть у меня рекурсивный вызов функции, и как я понял у меня переполняется некий &quot;стек вызовов&quot; ( там рандом, так что иногда ошибки...

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

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

Переполнение стека - C++
Хочу полюбопытствовать. Вычитал недавно, что на стек выделяется ограниченная область памяти, и в языке Си это 4 Кб. Вопрос: Если мне...

Переполнение стека - C++
Всем привет. Помогите, пожалуйста с решением одной проблемы. Мне нужно в программе обрабатывать большие объемы текста. 10 000 000 символов....

Переполнение стека - C++
Всем добрый вечер. Я создаю вектор, который имеет большой размер: порядка 256000000. Этот вектор имеет тип float, т.к. функция, куда я...

28
DrOffset
7377 / 4454 / 1009
Регистрация: 30.01.2014
Сообщений: 7,304
10.04.2014, 14:03 #16
Цитата Сообщение от NEvOl Посмотреть сообщение
в то время как быстрая сортировка занимает 10-15 секунд, но стек переполняется(
Там есть быстрая сортировка без рекурсии. Открой же уже ссылку
0
taras atavin
3570 / 1754 / 91
Регистрация: 24.11.2009
Сообщений: 27,567
10.04.2014, 14:20 #17
А разве сортировка вообще рекурсивна? Рекурсивно обработать массив можно в том случае, если можно разделить задачу его обработки на подзадачи обработки подмассивов, а сортировка так не распадается. Ведь как бы ты не разделил, на половины ли, на трети ли, или ещё как, сортировка этих фрагментов не имеет ничего общего с сортировкой всего массива. 0 12 3 15 1 6 5 4, делим на половины, получи 03 12 15 1 4 5 6, а надо 0 1 3 4 5 6 12 15, то есть 1, 4 и 5 должны перейти в левую половину, а 12 и 15 в правую, но при сортировке каждой из половин об этом во-первых не известно, а во-вторых не возможно. Можно надеться, что другое деление даст качественный результат, но из-за того, что при обработке подмассива не известно, что должно перейти в другой подмассив, это не решение.
0
DrOffset
7377 / 4454 / 1009
Регистрация: 30.01.2014
Сообщений: 7,304
10.04.2014, 14:36 #18
Цитата Сообщение от taras atavin Посмотреть сообщение
А разве сортировка вообще рекурсивна?
В алгортме быстрой сортировки используется деление на подмассивы на основе опорного элемента.
0
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
10.04.2014, 15:09 #19
А почему все Вы откинули идею использовать контейнер (vector например), и его сортировку?
0
taras atavin
3570 / 1754 / 91
Регистрация: 24.11.2009
Сообщений: 27,567
10.04.2014, 16:20 #20
Цитата Сообщение от DrOffset Посмотреть сообщение
В алгортме быстрой сортировки используется деление на подмассивы на основе опорного элемента.
Там массив делится на подмассивы, но задача не делится на аналогичные для подмассивов и вообще вся сортировка построена на перестановках элементов только между подмассивами, а не внутри.
0
DrOffset
7377 / 4454 / 1009
Регистрация: 30.01.2014
Сообщений: 7,304
10.04.2014, 17:34 #21
taras atavin, то есть ты отрицаешь факт того, что быстрая сортировка может быть реализована через рекурсию?
0
d1skort
20 / 20 / 0
Регистрация: 10.02.2013
Сообщений: 75
10.04.2014, 17:37 #22
Цитата Сообщение от taras atavin Посмотреть сообщение
Там массив делится на подмассивы, но задача не делится на аналогичные для подмассивов и вообще вся сортировка построена на перестановках элементов только между подмассивами, а не внутри.
А сортировка слиянием?
0
TenGen
Будущее рядом
98 / 96 / 20
Регистрация: 06.03.2014
Сообщений: 342
10.04.2014, 17:40 #23
Скорее всего уже говорили, но в таких случаях лучше передавать указатели на массив.
0
NEvOl
19 / 18 / 0
Регистрация: 13.08.2012
Сообщений: 729
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
3570 / 1754 / 91
Регистрация: 24.11.2009
Сообщений: 27,567
11.04.2014, 05:36 #25
Большой массив нельзя отсортировать быстро, в худшем случае он сортируется очень медленно, в лучшем просто медленно. Это неизбежно от ресурсоёмкости самой задачи и любой рост быстродействия только только отодвинет планку размера массива.
0
d1skort
20 / 20 / 0
Регистрация: 10.02.2013
Сообщений: 75
11.04.2014, 09:35 #26
Цитата Сообщение от NEvOl Посмотреть сообщение
переделал алгоритм в итеративный вариант, но все равно медленно как-то, может кто-нибудь подскажет что не так ?
А какое у тебя максимальное значение в массиве? Если оно достаточно мало (относительно количеству элементов массива), то можно отсортировать за линейное время сортировкой подсчетом.
0
Voivoid
675 / 278 / 12
Регистрация: 31.03.2013
Сообщений: 1,339
11.04.2014, 10:24 #27
А разве сортировка вообще рекурсивна?
Лол, а как по-твоему пишутся сортировки в функциональных языках?

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

Добавлено через 5 минут
Кроме того, простота разработки - вообще не фактор качества оси. Как раз с позиции разработчика приложений я и предпочитаю винду, но ось должна быть простой не для разработчика чего бы то ни было, а для пользователя, тем более если она не позиционируется на рынке, подобно фотону, как ось только для профессионалов.
0
NEvOl
19 / 18 / 0
Регистрация: 13.08.2012
Сообщений: 729
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
Привет! Вот еще темы с ответами:

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

Переполнение стека - C++
Привет народ. Такой вопрос: Если в общем виде: if (условие) double d else double d почему компилятор отказывается выполнять такое с...

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

Рекурсия - переполнение стека - C++
Помогите написать,задание ниже#include &quot;stdafx.h&quot; #include &quot;stdafx.h&quot; #include &lt;stdio.h&gt; #include &lt;conio.h&gt; #include &lt;math.h&gt; ...


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

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

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