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

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

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

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

09.04.2014, 23:04. Просмотров 883. Ответов 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++
Вообщем есть у меня рекурсивный вызов функции, и как я понял у меня переполняется некий &quot;стек вызовов&quot; ( там рандом, так что иногда ошибки...

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

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

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

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

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
KOPOJI
Модератор
Эксперт HTML/CSSЭксперт PHP
16694 / 6620 / 431
Регистрация: 12.06.2012
Сообщений: 19,875
Завершенные тесты: 1
09.04.2014, 23:06     Переполнение стека в рекурсивной функции сортировки большого массива #2
У любой рекурсии есть максимальная глубина... Вы просто заполнили стэк рекурсивными вызовами функций, вот и плюется исключениями
NEvOl
19 / 18 / 0
Регистрация: 13.08.2012
Сообщений: 726
09.04.2014, 23:07  [ТС]     Переполнение стека в рекурсивной функции сортировки большого массива #3
и что делать тогда ?)
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
09.04.2014, 23:08     Переполнение стека в рекурсивной функции сортировки большого массива #4
Проблема у вас с выделением памяти, пробуйте выделять динамически и проблем не будет...
KOPOJI
Модератор
Эксперт HTML/CSSЭксперт PHP
16694 / 6620 / 431
Регистрация: 12.06.2012
Сообщений: 19,875
Завершенные тесты: 1
09.04.2014, 23:08     Переполнение стека в рекурсивной функции сортировки большого массива #5
Лучше всего - имхо, не скармливать такие массивы (или разбить его на несколько поменьше). Можно, вроде, через опции компилятора увеличить размер стэка, но, как мне кажется, это не есть гуд - программа должна быть рассчитана на разные компиляторы, а не только на один ваш
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
09.04.2014, 23:10     Переполнение стека в рекурсивной функции сортировки большого массива #6
Ха точно не понял я сначала KOPOJI
NEvOl
19 / 18 / 0
Регистрация: 13.08.2012
Сообщений: 726
09.04.2014, 23:11  [ТС]     Переполнение стека в рекурсивной функции сортировки большого массива #7
Цитата Сообщение от mustimur Посмотреть сообщение
пробуйте выделять динамически и проблем не будет...
это как ? создавать новые массивы ?
или про что вы ?
KOPOJI
09.04.2014, 23:12
  #8

Не по теме:

Цитата Сообщение от NEvOl Посмотреть сообщение
это как ? создавать новые массивы ?
ага, а то вашей рекурсивной функции в стэке (почти) одной так одиноко и скучно...

NEvOl
19 / 18 / 0
Регистрация: 13.08.2012
Сообщений: 726
09.04.2014, 23:39  [ТС]     Переполнение стека в рекурсивной функции сортировки большого массива #9
я просто не понял о чем идет речь.

Добавлено через 14 минут
а как быть, ребят подскажите пожалуйста, мне нужно сортировать массив размеров около 260000 элементов, методом пузырька это делается дико долго, нашел в интернет такой способ, но тут с размером обламывается, что делать тогда ?

Добавлено через 11 минут
передаваемый в функцию массив и так создается динамически.
DrOffset
7058 / 4199 / 949
Регистрация: 30.01.2014
Сообщений: 6,965
09.04.2014, 23:56     Переполнение стека в рекурсивной функции сортировки большого массива #10
Цитата Сообщение от NEvOl Посмотреть сообщение
что делать тогда ?
Найти итеративный алгоритм взамен рекурсивного. Можно здесь посмотреть варианты.
NEvOl
19 / 18 / 0
Регистрация: 13.08.2012
Сообщений: 726
09.04.2014, 23:59  [ТС]     Переполнение стека в рекурсивной функции сортировки большого массива #11
может кто-нибудь посоветует, нужен быстрый очень метод ?
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
10.04.2014, 13:23     Переполнение стека в рекурсивной функции сортировки большого массива #12
Нужна сортировка, реализованная обязательно с помощью пользовательской рекурсивной функцией? Или можно предлагать другие варианты?
NEvOl
19 / 18 / 0
Регистрация: 13.08.2012
Сообщений: 726
10.04.2014, 13:32  [ТС]     Переполнение стека в рекурсивной функции сортировки большого массива #13
любые варианты, главное быстрые, и что бы программа не ломалась) размер массива от 250 000 до 1000 000 элементов, а диапозон значений произвольный
DrOffset
7058 / 4199 / 949
Регистрация: 30.01.2014
Сообщений: 6,965
10.04.2014, 13:35     Переполнение стека в рекурсивной функции сортировки большого массива #14
NEvOl, я же дал тебе ссылку на предыдущей странице. Там есть в том числе и твой алгоритм, но без рекурсии...
NEvOl
19 / 18 / 0
Регистрация: 13.08.2012
Сообщений: 726
10.04.2014, 13:37  [ТС]     Переполнение стека в рекурсивной функции сортировки большого массива #15
пробовал сортировку методом пузырька, на сортировку 250 000 элементов уходит около полутора минут, в то время как быстрая сортировка занимает 10-15 секунд, но стек переполняется(

Добавлено через 40 секунд
точно, сейчас попробую разобраться
DrOffset
7058 / 4199 / 949
Регистрация: 30.01.2014
Сообщений: 6,965
10.04.2014, 14:03     Переполнение стека в рекурсивной функции сортировки большого массива #16
Цитата Сообщение от NEvOl Посмотреть сообщение
в то время как быстрая сортировка занимает 10-15 секунд, но стек переполняется(
Там есть быстрая сортировка без рекурсии. Открой же уже ссылку
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
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 в правую, но при сортировке каждой из половин об этом во-первых не известно, а во-вторых не возможно. Можно надеться, что другое деление даст качественный результат, но из-за того, что при обработке подмассива не известно, что должно перейти в другой подмассив, это не решение.
DrOffset
7058 / 4199 / 949
Регистрация: 30.01.2014
Сообщений: 6,965
10.04.2014, 14:36     Переполнение стека в рекурсивной функции сортировки большого массива #18
Цитата Сообщение от taras atavin Посмотреть сообщение
А разве сортировка вообще рекурсивна?
В алгортме быстрой сортировки используется деление на подмассивы на основе опорного элемента.
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
10.04.2014, 15:09     Переполнение стека в рекурсивной функции сортировки большого массива #19
А почему все Вы откинули идею использовать контейнер (vector например), и его сортировку?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.04.2014, 16:20     Переполнение стека в рекурсивной функции сортировки большого массива
Еще ссылки по теме:

Реализовать переполнение стека - 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; ...

Произведение элементов одномерного массива с использованием рекурсивной функции - C++
Пожалуйста помогите решите задачу: Произведение элементов одномерного массива с помощью рекурсивной функции.

Почему возникает переполнение стека??? - C++
У меня есть программа которая выводит все возможные перестановки заданного слова(числа) в данном случае числа 123, но почему то возникает...

Переполнение стека из-за передачи струтуры - C++
у меня происходит переполнение стека из-за передачи большой структуры. и не только из-за структуры пытался передать большую строку тоже...


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

Или воспользуйтесь поиском по форуму:
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
10.04.2014, 16:20     Переполнение стека в рекурсивной функции сортировки большого массива #20
Цитата Сообщение от DrOffset Посмотреть сообщение
В алгортме быстрой сортировки используется деление на подмассивы на основе опорного элемента.
Там массив делится на подмассивы, но задача не делится на аналогичные для подмассивов и вообще вся сортировка построена на перестановках элементов только между подмассивами, а не внутри.
Yandex
Объявления
10.04.2014, 16:20     Переполнение стека в рекурсивной функции сортировки большого массива
Ответ Создать тему
Опции темы

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