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

@NEvOl · Регистрация: 13.08.2012

Студворк — интернет-сервис помощи студентам

Написал рекурсивную функцию сортировки массива, с массивами небольших размеров все работает как надо, а вот если сортирую побоьлше (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);
}

KOPOJI · 09.04.2014, 23:06

У любой рекурсии есть максимальная глубина... Вы просто заполнили стэк рекурсивными вызовами функций, вот и плюется исключениями

@NEvOl · 09.04.2014, 23:07 **[ТС]**

и что делать тогда ?)

@mustimur · 09.04.2014, 23:08

Проблема у вас с выделением памяти, пробуйте выделять динамически и проблем не будет...

KOPOJI · 09.04.2014, 23:08

Лучше всего - имхо, не скармливать такие массивы (или разбить его на несколько поменьше). Можно, вроде, через опции компилятора увеличить размер стэка, но, как мне кажется, это не есть гуд - программа должна быть рассчитана на разные компиляторы, а не только на один ваш

@mustimur · 09.04.2014, 23:10

Ха точно не понял я сначала KOPOJI

@NEvOl · 09.04.2014, 23:11 **[ТС]**

Сообщение от mustimur

пробуйте выделять динамически и проблем не будет...

это как ? создавать новые массивы ?
или про что вы ?

KOPOJI · 09.04.2014, 23:12

Не по теме:

Сообщение от NEvOl

это как ? создавать новые массивы ?

ага, а то вашей рекурсивной функции в стэке (почти) одной так одиноко и скучно... :D

@NEvOl · 09.04.2014, 23:39 **[ТС]**

я просто не понял о чем идет речь.

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

Добавлено через 11 минут
передаваемый в функцию массив и так создается динамически.

@DrOffset · 09.04.2014, 23:56

Сообщение от NEvOl

что делать тогда ?

Найти итеративный алгоритм взамен рекурсивного. Можно здесь посмотреть варианты.

@NEvOl · 09.04.2014, 23:59 **[ТС]**

может кто-нибудь посоветует, нужен быстрый очень метод ?

@mustimur · 10.04.2014, 13:23

Нужна сортировка, реализованная обязательно с помощью пользовательской рекурсивной функцией? Или можно предлагать другие варианты?

@NEvOl · 10.04.2014, 13:32 **[ТС]**

любые варианты, главное быстрые, и что бы программа не ломалась) размер массива от 250 000 до 1000 000 элементов, а диапозон значений произвольный

@DrOffset · 10.04.2014, 13:35

NEvOl, я же дал тебе ссылку на предыдущей странице. Там есть в том числе и твой алгоритм, но без рекурсии...

@NEvOl · 10.04.2014, 13:37 **[ТС]**

пробовал сортировку методом пузырька, на сортировку 250 000 элементов уходит около полутора минут, в то время как быстрая сортировка занимает 10-15 секунд, но стек переполняется(

Добавлено через 40 секунд
точно, сейчас попробую разобраться

@DrOffset · 10.04.2014, 14:03

Сообщение от NEvOl

в то время как быстрая сортировка занимает 10-15 секунд, но стек переполняется(

Там есть быстрая сортировка без рекурсии. Открой же уже ссылку

@taras atavin · 10.04.2014, 14:20

А разве сортировка вообще рекурсивна? Рекурсивно обработать массив можно в том случае, если можно разделить задачу его обработки на подзадачи обработки подмассивов, а сортировка так не распадается. Ведь как бы ты не разделил, на половины ли, на трети ли, или ещё как, сортировка этих фрагментов не имеет ничего общего с сортировкой всего массива. 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 · 10.04.2014, 14:36

Сообщение от taras atavin

А разве сортировка вообще рекурсивна?

В алгортме быстрой сортировки используется деление на подмассивы на основе опорного элемента.

@mustimur · 10.04.2014, 15:09

А почему все Вы откинули идею использовать контейнер (vector например), и его сортировку?

@taras atavin · 10.04.2014, 16:20

Сообщение от DrOffset

В алгортме быстрой сортировки используется деление на подмассивы на основе опорного элемента.

Там массив делится на подмассивы, но задача не делится на аналогичные для подмассивов и вообще вся сортировка построена на перестановках элементов только между подмассивами, а не внутри.

Новые блоги и статьи Все статьи Все блоги /
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025	Расскажи мне о Мире, бродяга kumehtar 12.11.2025 — Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .

KOPOJI Почетный модератор 16844 / 6724 / 880 Регистрация: 12.06.2012 Сообщений: 19,967
	09.04.2014, 23:06
	У любой рекурсии есть максимальная глубина... Вы просто заполнили стэк рекурсивными вызовами функций, вот и плюется исключениями 0

@NEvOl 20 / 19 / 1 Регистрация: 13.08.2012 Сообщений: 779
	09.04.2014, 23:07 [ТС]
	и что делать тогда ?) 0

@mustimur 320 / 225 / 74 Регистрация: 22.11.2013 Сообщений: 867 Записей в блоге: 1
	09.04.2014, 23:08
	Проблема у вас с выделением памяти, пробуйте выделять динамически и проблем не будет... 0

@mustimur 320 / 225 / 74 Регистрация: 22.11.2013 Сообщений: 867 Записей в блоге: 1
	09.04.2014, 23:10
	Ха точно не понял я сначала KOPOJI 0

@NEvOl 20 / 19 / 1 Регистрация: 13.08.2012 Сообщений: 779
	09.04.2014, 23:39 [ТС]
	я просто не понял о чем идет речь. Добавлено через 14 минут а как быть, ребят подскажите пожалуйста, мне нужно сортировать массив размеров около 260000 элементов, методом пузырька это делается дико долго, нашел в интернет такой способ, но тут с размером обламывается, что делать тогда ? Добавлено через 11 минут передаваемый в функцию массив и так создается динамически. 0

@NEvOl 20 / 19 / 1 Регистрация: 13.08.2012 Сообщений: 779
	09.04.2014, 23:59 [ТС]
	может кто-нибудь посоветует, нужен быстрый очень метод ? 0

@mustimur 320 / 225 / 74 Регистрация: 22.11.2013 Сообщений: 867 Записей в блоге: 1
	10.04.2014, 13:23
	Нужна сортировка, реализованная обязательно с помощью пользовательской рекурсивной функцией? Или можно предлагать другие варианты? 0

@NEvOl 20 / 19 / 1 Регистрация: 13.08.2012 Сообщений: 779
	10.04.2014, 13:32 [ТС]
	любые варианты, главное быстрые, и что бы программа не ломалась) размер массива от 250 000 до 1000 000 элементов, а диапозон значений произвольный 0

@DrOffset 19491 / 10097 / 2460 Регистрация: 30.01.2014 Сообщений: 17,805
	10.04.2014, 13:35
	NEvOl, я же дал тебе ссылку на предыдущей странице. Там есть в том числе и твой алгоритм, но без рекурсии... 0

@NEvOl 20 / 19 / 1 Регистрация: 13.08.2012 Сообщений: 779
	10.04.2014, 13:37 [ТС]
	пробовал сортировку методом пузырька, на сортировку 250 000 элементов уходит около полутора минут, в то время как быстрая сортировка занимает 10-15 секунд, но стек переполняется( Добавлено через 40 секунд точно, сейчас попробую разобраться 0

@taras atavin 4226 / 1796 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	10.04.2014, 14:20
	А разве сортировка вообще рекурсивна? Рекурсивно обработать массив можно в том случае, если можно разделить задачу его обработки на подзадачи обработки подмассивов, а сортировка так не распадается. Ведь как бы ты не разделил, на половины ли, на трети ли, или ещё как, сортировка этих фрагментов не имеет ничего общего с сортировкой всего массива. 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

@mustimur 320 / 225 / 74 Регистрация: 22.11.2013 Сообщений: 867 Записей в блоге: 1
	10.04.2014, 15:09
	А почему все Вы откинули идею использовать контейнер (vector например), и его сортировку? 0